CF994A - Fingerprints

题目描述

You are locked in a room with a door that has a keypad with 10 keys corresponding to digits from 0 to 9. To escape from the room, you need to enter a correct code. You also have a sequence of digits.

Some keys on the keypad have fingerprints. You believe the correct code is the longest not necessarily contiguous subsequence of the sequence you have that only contains digits with fingerprints on the corresponding keys. Find such code.

输入

The first line contains two integers n and m (1≤n,m≤10) representing the number of digits in the sequence you have and the number of keys on the keypad that have fingerprints.

The next line contains n distinct space-separated integers x1,x2,…,xn (0≤xi≤9) representing the sequence.

The next line contains mm distinct space-separated integers y1,y2,…,ym (0≤yi≤9) — the keys with fingerprints.

输出

In a single line print a space-separated sequence of integers representing the code. If the resulting sequence is empty, both printing nothing and printing a single line break is acceptable.

样例

Input

1
2
3
7 3
3 5 7 1 6 2 8
1 2 7

Output

1
7 1 2

Input

1
2
3
4 4
3 4 1 0
0 1 7 9

Output

1
1 0

注意

In the first example, the only digits with fingerprints are 1, 2 and 7. All three of them appear in the sequence you know, 7 first, then 1 and then 2. Therefore the output is 7 1 2. Note that the order is important, and shall be the same as the order in the original sequence.

In the second example digits 0, 1, 7 and 9 have fingerprints, however only 0 and 1 appear in the original sequence. 1 appears earlier, so the output is 1 0. Again, the order is important.

解题思路

送分水题，根据题意可以知道，已知一个原序列和带指纹的数字序列，密码是原序列的一个最长子序列（子序列的数都带指纹）。

这道题目给出三行数据，第一行m和n。第二行m个数字为已知序列，第三行n个数字为带指纹的数字。

我们只需要依次判断m中的数是否在n中出现，若出现则输出。（顺序需要按照原序列的顺序）

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int m, n;
	int arr_m[10] = { 0 };	//原序列
	int arr_n[10] = { 0 };	//子序列

	cin >> m >> n;

	for (int i = 0; i < m; i++)	//读入原序列
	{
		cin >> arr_m[i];
	}

	for (int i = 0; i < n; i++)	//读入子序列
	{
		cin >> arr_n[i];
	}

	for (int i = 0; i < m; i++)	//遍历原序列
	{
		for (int j = 0; j < n; j++)	//遍历子序列，判断原序列的数是否在子序列出现
		{
			if (arr_m[i] == arr_n[j])
			{
			    cout << ' ' << arr_m[i];
			}
		}
	}

	return 0;
}

English单词积累

keypad—键盘

subsequence—子序列

CF994B - Knights of a Polygonal Table

题目描述

Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than k other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim’s coins.

Now each knight ponders: how many coins he can have if only he kills other knights?

You should answer this question for each knight.

输入

The first line contains two integers n and k (1 ≤ n ≤10^5^, 0 ≤ k ≤ min(n−1, 10) ) — the number of knights and the number k from the statement.

The second line contains n integers p1,p2,…,p (1≤pi≤10^9^) — powers of the knights. All pi are distinct.

The third line contains n integers c1,c2,…,cn (0≤ci≤10^9^) — the number of coins each knight has.

输出

Print n integers — the maximum number of coins each knight can have it only he kills other knights.

样例

Input

1
2
3
4 2
4 5 9 7
1 2 11 33

Output

1
1 3 46 36

Input

1
2
3
5 1
1 2 3 4 5
1 2 3 4 5

Output

1
1 3 5 7 9

Input

1
2
3
1 0
2
3

Output

1
3

注意

Consider the first example.

  • The first knight is the weakest, so he can’t kill anyone. That leaves him with the only coin he initially has.
  • The second knight can kill the first knight and add his coin to his own two.
  • The third knight is the strongest, but he can’t kill more than k=2 other knights. It is optimal to kill the second and the fourth knights: 2+11+33=46.
  • The fourth knight should kill the first and the second knights: 33+1+2=36.

In the second example the first knight can’t kill anyone, while all the others should kill the one with the index less by one than their own.

In the third example there is only one knight, so he can’t kill anyone.

解题思路

题目说有n个骑士，它们杀人不超过k个，每个人都有power和金币。

只能击杀power比自己小的人，杀掉其他人可以捡别人的金币。求击杀后拥有的金币的最大数量。

这题也不算很难，模拟也能过。起初的思路在第九个测试点超时了，优化了一下sort使用的次数后一直在后面的测试点WA。

反复检查没发现问题，最后才发现没开long long，超出int的范围了。

int在32和64位机器人中占4个字节，表示的范围 -231— 2^31^-1 数量级大概在10^9^。

模拟的思路：给每个骑士一个id，这个id用于最后按照输入的顺序输出答案。

首先给骑士按power由小到大排序。

遍历骑士的数组（关键，一定分情况，否则超时）：

如果前面的人的数量小于k，把前面人的金币数量加入coin数组，然后全部杀。

如果前面的人的数量大于k。把coin数组排序，数组中最小的金币数量和最新一个骑士的金币数量比较。取最大的。然后杀k个人。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>

using namespace std;

struct Knights	//骑士数据结构
{
	int id;		//用于最后按输入的顺序输出答案
	int power;	//骑士的power
	int coin;		//骑士拥有的金币
	long long ans;		//杀掉其它骑士获得的金币
};

bool cmp1(Knights a, Knights b)		//按照power，由小到大排序
{
	return a.power < b.power;
}

bool cmp2(Knights a, Knights b)		//按照id从小到大排序（即恢复到输入的顺序）
{
	return a.id < b.id;
}

bool cmp3(int a, int b)		//给金币数组排序，按从大到小
{
	return a > b;
}

Knights knights[100000] = { 0 };	//骑士数组
int coin[10] = { 0 };			//金币数组（题意说最多杀10人）

int main()
{
	int n, k;

	cin >> n >> k;
	for (int i = 0; i < n; i++)		//读入id和power
	{
		knights[i].id = i;
		cin >> knights[i].power;
	}

	for (int i = 0; i < n; i++)		//读入金币
	{
		cin >> knights[i].coin;
	}

	//开始计算
	int coin_index = 0;	//金币数组的下标

	sort(knights, knights + n, cmp1);	//首先，按照power给骑士由小到大排序

	for (int i = 1; i < n; i++)		//从第二个骑士开始（最弱的骑士不杀人）计算
	{
		int max = 0;
		max = i > k ? k : i;	//杀掉max个人

		//前面有i个人
		if (coin_index >= k) //前面的人超过k人
		{
			sort(coin, coin + k, cmp3);	//按照金币数量从大到小排序（这是关键，如果写在if外面会超时）
			coin[coin_index - 1] = knights[i - 1].coin > coin[coin_index - 1] ? knights[i - 1].coin : coin[coin_index - 1];	//让coin数组中最少的coin数量和后面的人金币数量比较。取最大的金币数
		}
		else
		{
			coin[coin_index] = knights[i - 1].coin;		//保存到coin数组
			coin_index++;
		}

		for (int j = 0; j < max; j++)	//开始杀人，获得金币
		{
			knights[i].ans += coin[j];
		}
	}

	//输出答案
	sort(knights, knights + n, cmp2);		//按照序号排序，即输入顺序

	for (int i = 0; i < n; i++)
	{
		cout << " " << knights[i].ans + knights[i].coin;
	}

	return 0;
}

English单词积累

Knights—骑士

Polygonal—多边形

deprived of—剥夺

nobility—贵族

torment—折磨

conscience—良心

ponders—思考

optimal—最优的

CF994C - Two Squares

题目描述

You are given two squares, one with sides parallel to the coordinate axes, and another one with sides at 45 degrees to the coordinate axes. Find whether the two squares intersect.

The interior of the square is considered to be part of the square, i.e. if one square is completely inside another, they intersect. If the two squares only share one common point, they are also considered to intersect.

输入

The input data consists of two lines, one for each square, both containing 4 pairs of integers. Each pair represents coordinates of one vertex of the square.

The first line contains the coordinates of the square with sides parallel to the coordinate axes, the second line contains the coordinates of the square at 45 degrees.

All the values are integer and between −100 and 100.

输出

Print “Yes” if squares intersect, otherwise print “No”.

You can print each letter in any case (upper or lower).

样例

Input

1
2
0 0 6 0 6 6 0 6
1 3 3 5 5 3 3 1

Output

1
YES

Input

1
2
0 0 6 0 6 6 0 6
7 3 9 5 11 3 9 1

Output

1
NO

Input

1
2
6 0 6 6 0 6 0 0
7 4 4 7 7 10 10 7

Output

1
YES

注意

In the first example the second square lies entirely within the first square, so they do intersect.

In the second sample squares do not have any points in common.

Here are images corresponding to the samples:

Rating1

Rating2

Rating3

解题思路

题目给的数据范围很小，因此可以之间暴力枚举图中所有的点。

如果点即在s1又在s2，则证明这两个正方形相交。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <algorithm>

using namespace std;

struct Point	//坐标点结构体
{
	int x;
	int y;
};

bool cmp(Point a, Point b)		//按x和y由小到大排序
{
	if (a.x == b.x)
	{
		return a.y < b.y;
	}
	else
	{
		return a.x < b.x;
	}
}

int main()
{
	Point p1[4] = { 0 };	//s1的坐标
	Point p2[4] = { 0 };	//s2的坐标
	int arr[201][201] = { 0 };	//保存暴力枚举的坐标点

	for (int i = 0; i < 4; i++)
	{
		cin >> p1[i].x >> p1[i].y;
	}

	for (int i = 0; i < 4; i++)
	{
		cin >> p2[i].x >> p2[i].y;
	}

	sort(p1, p1 + 4, cmp);
	sort(p2, p2 + 4, cmp);

	for (int i = p1[0].x; i <= p1[3].x; i++)	//枚举s1
	{
		for (int j = p1[0].y; j <= p1[3].y; j++)
		{
			arr[i + 100][j + 100] = 1;		//范围 -100 — 100
		}
	}

	int flag = 0;
	//左半部分枚举
	for (int i = p2[0].x; i <= p2[1].x; i++)	//枚举s2
	{
		if (flag == 1)	break;

		for (int j = p2[0].y; j <= p2[0].y + i - p2[0].x; j++)	//向上枚举
		{
			if (arr[i + 100][j + 100])
			{
				cout << "YES" << endl;
				flag = 1;
				break;
			}
		}

		if (flag == 1)	break;

		for (int j = p2[0].y; j >= (p2[0].y - (i - p2[0].x)); j--)	//向下枚举
		{
			if (arr[i + 100][j + 100])
			{
				cout << "YES" << endl;
				flag = 1;
				break;
			}
		}
	}

	//右半部分枚举
	for (int i = p2[3].x; i >= p2[1].x; i--)	//枚举s2
	{
		if (flag == 1)	break;

		for (int j = p2[3].y; j <= p2[3].y + p2[3].x - i; j++)	//向上枚举
		{
			if (arr[i + 100][j + 100])
			{
				cout << "YES" << endl;
				flag = 1;
				break;
			}
		}

		if (flag == 1)	break;

		for (int j = p2[3].y; j >= (p2[3].y - (p2[3].x - i)); j--)	//向下枚举
		{
			if (arr[i + 100][j + 100])
			{
				cout << "YES" << endl;
				flag = 1;
				break;
			}
		}
	}

	if (flag == 0)	cout << "NO" << endl;

	return 0;
}

English单词积累

sides—边

parallel—平行

coordinate axes—坐标轴

intersect—相交

interior—内部

vertex—顶点

CF994D - Open Communication

CF994E - Careful Maneuvering

CF994F - Compute Power