Codeforces Round #699 (Div. 2)
题目很有意思，整套题目是一个系列的
原本可以做出3道的，都是C题这种题做少了。。。
A. Space Navigation
You were dreaming that you are traveling to a planet named Planetforces on your personal spaceship. Unfortunately, its piloting system was corrupted and now you need to fix it in order to reach Planetforces.
Space can be represented as the XY plane. You are starting at point (0,0), and Planetforces is located in point (px,py).
The piloting system of your spaceship follows its list of orders which can be represented as a string s. The system reads s from left to right. Suppose you are at point (x,y) and current order is si:
if si=U, you move to (x,y+1); if si=D, you move to (x,y−1); if si=R, you move to (x+1,y); if si=L, you move to (x−1,y). Since string s could be corrupted, there is a possibility that you won’t reach Planetforces in the end. Fortunately, you can delete some orders from s but you can’t change their positions.
Can you delete several orders (possibly, zero) from s in such a way, that you’ll reach Planetforces after the system processes all orders?
Input The first line contains a single integer t (1≤t≤1000) — the number of test cases.
Each test case consists of two lines. The first line in each test case contains two integers px and py (−105≤px,py≤105; (px,py)≠(0,0)) — the coordinates of Planetforces (px,py).
| The second line contains the string s (1≤ | s | ≤105: | s | is the length of string s) — the list of orders. |
| It is guaranteed that the sum of | s | over all test cases does not exceed 105. |
Output For each test case, print “YES” if you can delete several orders (possibly, zero) from s in such a way, that you’ll reach Planetforces. Otherwise, print “NO”. You can print each letter in any case (upper or lower).
中文大意：判断能否通过删除一些行动，到达指定的位置
解析：算出可以到达的极限在哪，在判断指定的位置是否在其中就可以了
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
#include <iostream>
using namespace std;
int main() {
int cas;
cin >> cas;
while (cas--) {
int x, y;
string str;
cin >> x >> y >> str;
int u = 0, d = 0, r = 0, l = 0;
for (int i = 0; i < str.size(); i++) {
if (str[i] == 'U') u++;
if (str[i] == 'D') d++;
if (str[i] == 'R') r++;
if (str[i] == 'L') l++;
}
bool is_x = false, is_y = false;
if (y >= 0 && u >= y) {
is_y = true;
}
if (y <= 0 && d >= abs(y)) {
is_y = true;
}
if (x >= 0 && r >= x) {
is_x = true;
}
if (x <= 0 && l >= abs(x)) {
is_x = true;
}
if (is_x && is_y) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
B. New Colony
After reaching your destination, you want to build a new colony on the new planet. Since this planet has many mountains and the colony must be built on a flat surface you decided to flatten the mountains using boulders (you are still dreaming so this makes sense to you).
You are given an array h1,h2,…,hn, where hi is the height of the i-th mountain, and k — the number of boulders you have.
You will start throwing boulders from the top of the first mountain one by one and they will roll as follows (let’s assume that the height of the current mountain is hi):
if hi≥hi+1, the boulder will roll to the next mountain; if hi<hi+1, the boulder will stop rolling and increase the mountain height by 1 (hi=hi+1); if the boulder reaches the last mountain it will fall to the waste collection system and disappear. You want to find the position of the k-th boulder or determine that it will fall into the waste collection system.
Input The first line contains a single integer t (1≤t≤100) — the number of test cases.
Each test case consists of two lines. The first line in each test case contains two integers n and k (1≤n≤100; 1≤k≤109) — the number of mountains and the number of boulders.
The second line contains n integers h1,h2,…,hn (1≤hi≤100) — the height of the mountains.
It is guaranteed that the sum of n over all test cases does not exceed 100.
Output For each test case, print −1 if the k-th boulder will fall into the collection system. Otherwise, print the position of the k-th boulder.
中文大意：计算出最后一颗石头的位置，如果进入了回收装置则输出-1
解析：先判断最后一颗石头是否一定会进入回收装置，一定会则输出-1，否则进行模拟算出位置
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
#include <iostream>
using namespace std;
int h[105];
int main() {
int cas;
cin >> cas;
while (cas--) {
int n, k;
cin >> n >> k;
int ma = 0;
for (int i = 1; i <= n; i++) {
cin >> h[i];
ma = max(ma, h[i]);
}
if (k >= ma * n) {
cout << -1 << endl;
} else {
int pos = 0;
int i = 1; // 第i块石头
for (; i <= k; i++) {
for (int j = 1; j <= n; j++) {
if (j == n) {
pos = -1;
break;
}
if (h[j] >= h[j + 1]) {
continue;
} else {
pos = j;
h[j]++;
break;
}
}
if (pos == -1) {
break;
}
}
cout << pos << endl;
}
}
return 0;
}
C. Fence Painting
You finally woke up after this crazy dream and decided to walk around to clear your head. Outside you saw your house’s fence — so plain and boring, that you’d like to repaint it.
You have a fence consisting of n planks, where the i-th plank has the color ai. You want to repaint the fence in such a way that the i-th plank has the color bi.
You’ve invited m painters for this purpose. The j-th painter will arrive at the moment j and will recolor exactly one plank to color cj. For each painter you can choose which plank to recolor, but you can’t turn them down, i. e. each painter has to color exactly one plank.
Can you get the coloring b you want? If it’s possible, print for each painter which plank he must paint.
Input The first line contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.
The first line of each test case contains two integers n and m (1≤n,m≤105) — the number of planks in the fence and the number of painters.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — the initial colors of the fence.
The third line of each test case contains n integers b1,b2,…,bn (1≤bi≤n) — the desired colors of the fence.
The fourth line of each test case contains m integers c1,c2,…,cm (1≤cj≤n) — the colors painters have.
It’s guaranteed that the sum of n doesn’t exceed 105 and the sum of m doesn’t exceed 105 over all test cases.
Output For each test case, output “NO” if it is impossible to achieve the coloring b.
Otherwise, print “YES” and m integers x1,x2,…,xm, where xj is the index of plank the j-th painter should paint.
You may print every letter in any case you want (so, for example, the strings “yEs”, “yes”, “Yes” and “YES” are all recognized as positive answer).
中文大意：篱笆有$n$块板子，第$i$块板子的颜色为$a_i$，现在我们觉得颜色的篱笆太丑了，想把第$i$块板子的颜色改为$b_i$，我们找了$m$个画家，第$i$个画家会在时刻$i$到来，选择一块板子并将其颜色涂成$c_i$，我们可以决定画家涂哪块板子，而且每个画家必须涂一块板子，请你判断是否能够涂成我们想要的颜色，能的话请输出方案
解析：
- temp[]：记录需要的颜色i的个数
- map<int, vector
> need：记录需要颜色i的位置 - map<int, int> color： 颜色及其出现次数
- 读入数据，当a[i] != b[i]时，temp[b[i]]++，need[b[i]].push_back(i)，color[i] = temp[i]
- 读入数据，temp[c[i]]–
- 判断最后一个画家的颜色是否在数组$b$中，在的话优先选择a[i] != b[i]的位置作为最后一个画家的位置（last_pos)，其他没用的画家也涂这个位置
- 再判断是否temp[i] > 0
- 假如3和4成立，则输出”YES”，否则输出”NO”
- 假如$c_i$画家有用（!nedd[c[i]].empty()），则输出$c_i$画家涂的位置，否则输出最后一个画家的位置（last_pos）
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
/*
c中最后一块必须在b数组里面
c中数组必须有那么多可以改变
c >= b - a
记录颜色的次数
改变出现的位置及其相应的位置
*/
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N], temp[N];
int main() {
int cas;
cin >> cas;
while (cas--) {
memset(temp, 0, sizeof(temp));
map<int, vector<int>> need; // 需要改变的颜色及其位置
map<int, int> color; // 颜色及其出现次数
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
cin >> b[i];
if (b[i] != a[i]) {
temp[b[i]]++;
need[b[i]].push_back(i);
}
}
// 记录颜色改变的次数
for (int i = 1; i <= n; i++) {
if (temp[i] > 0) {
color[i] = temp[i];
}
}
for (int i = 1; i <= m; i++) {
cin >> c[i];
temp[c[i]]--;
}
bool flag = false, use = false;
int last_pos = 0; // 最后一个画家画的地方
// 最后一个画家画的地方应该尽可能有用 即改变的地方a[i]!=b[i]
// 条件1
for (int i = 1; i <= n; i++) {
if (c[m] == b[i]) {
if (!flag) {
flag = true;
last_pos = i;
}
if (b[i] != a[i]) {
use = true;
last_pos = i;
}
if (use) {
break;
}
}
}
// 条件二
if (flag) {
for (int i = 1; i <= n; i++) {
if (temp[i] > 0) {
flag = false;
break;
}
}
}
if (flag) {
cout << "YES" << endl;
for (int i = 1; i < m ; i++) {
bool have = false;
if (!need[c[i]].empty()) {
cout << need[c[i]].back() << " ";
need[c[i]].pop_back();
have = true;
}
if (!have) {
cout << last_pos << " ";
}
}
cout << last_pos << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
