Codeforces Round #612 (Div. 2) 前四题题解
nblyz2003 人气:2这场比赛的出题人挺有意思，全部magic成了青色。
还有题目中的图片特别有趣。
晚上没打，开virtual contest打的，就会前三道，我太菜了。
最后看着题解补了第四道。
比赛传送门
A. Angry Students
题目大意：有t队学生，每个学生有两种状态，生气（A）或不生气（P）。（话说为什么生气的戴着圣诞帽哇）所有生气的人都会往前一个人丢雪球，被丢到的人也会变得生气，也会丢雪球。问你每队人中最后一个学生变得生气的时刻。
这题就是统计最长的连续的'P'当然前提是左边有生气的人。
代码如下：
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #define rep(x, l, r) for(int x = l; x <= r; x++)
7 #define repd(x, r, l) for(int x = r; x >= l; x--)
8 #define clr(x, y) memset(x, y, sizeof(x))
9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN 105
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long ll;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 1000000009;
22 int lowbit(int x){ return x & (-x);}
23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
24
25 char st[MAXN];
26
27 int main(){
28 int t;
29 scanf("%d", &t);
30 while(t--){
31 int n;
32 scanf("%d", &n);
33 scanf("%s", st);
34 int flag = 0, ans = 0, sum = 0;
35 rep(i, 0, n - 1){
36 if(st[i] == 'A'){
37 flag = 1;
38 sum = 0;
39 }
40 if(st[i] == 'P' && flag){
41 sum++;
42 ans = max(ans, sum);
43 }
44 }
45 printf("%d\n", ans);
46 }
47 return 0;
48 }
B.Hyperset
题目大意：有n张卡，每张卡有k个特征，每个特征有三种（'S', 'E', 'T'），让你选出三张卡组成一套，使得三张卡中的每个特征全部相等或者全部不同。如样例三中的"SETT", "TEST", "EEET"是一套，"TEST", "ESTE", "STES"也是一套，问一共能选出几套。
这题数据很小，n在1500以内，把所有状态直接改为三进制数也是在longlong范围内，怎么做都行。
我的解法极其繁杂，转成数字后离散化再进行计数。
先枚举两张卡i和j，这样可以直接求出第三张卡的状态（如果前两张相同，第三张也相同，如果前两张不同，第三张就是剩下的那种），答案加上符合该种状态卡的个数。
又臭又长的代码：
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #include <map>
7 #define rep(x, l, r) for(int x = l; x <= r; x++)
8 #define repd(x, r, l) for(int x = r; x >= l; x--)
9 #define clr(x, y) memset(x, y, sizeof(x))
10 #define all(x) x.begin(), x.end()
11 #define pb push_back
12 #define mp make_pair
13 #define MAXN 1505
14 #define MAXM 35
15 #define fi first
16 #define se second
17 #define SZ(x) ((int)x.size())
18 using namespace std;
19 typedef long long ll;
20 typedef vector<int> vi;
21 typedef pair<int, int> pii;
22 const int INF = 1 << 30;
23 const int p = 1000000009;
24 int lowbit(int x){ return x & (-x);}
25 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
26
27 map<ll, int> Rank;
28 char st[MAXM];
29 int a[MAXN][MAXM], c[MAXN], sum[MAXN];
30 ll num[MAXN], b[MAXN];
31
32 int judge(char ch){
33 if(ch == 'S') return 0;
34 if(ch == 'E') return 1;
35 if(ch == 'T') return 2;
36 }
37
38 int main(){
39 int n, len;
40 scanf("%d%d", &n, &len);
41 rep(i, 1, n){
42 scanf("%s", st);
43 rep(j, 0, len - 1){
44 num[i] = num[i] * 3 + judge(st[j]);
45 a[i][j + 1] = judge(st[j]);
46 }
47 b[i] = num[i];
48 }
49 sort(b + 1, b + n + 1);
50 rep(i, 1, n) Rank[b[i]] = i;
51 rep(i, 1, n) c[i] = Rank[num[i]];
52 int ans = 0;
53 rep(i, 1, n){
54 rep(j, i + 1, n){
55 ll s = 0;
56 rep(k, 1, len){
57 int x = (6 - a[i][k] - a[j][k]) % 3;
58 s = s * 3 + x;
59 }
60 if(Rank.find(s) != Rank.end()) ans += sum[Rank[s]];
61 }
62 sum[c[i]]++;
63 }
64 printf("%d\n", ans);
65 return 0;
66 }
C.Garland
题目大意：有一个由[ 1…n ]组成的排列，其中有一些数被取走了（取走的数用0表示），现在将这些数放回这些空余的位置中。序列中每有相邻一对数的奇偶性不同就会增加序列的复杂度，求复杂度最小为多少。
这题我是在大佬的提示下才做出来的。
首先看到这个奇偶性，那么就不客气了，把数字直接给丢了留个膜2的余数就好。
现在问题变成了再剩余的位置放0/1使得相邻的复杂度最小。
虽然codeforces上这题的算法标签标了个greedy，但是我没搞懂这题怎么贪。
但是我们发现放的数为多少只会对后一个数字产生影响，所以可以用动态规划。
状态为放了i个数，用了j个1，这个数放的是0/1。
转移分两种第i个空余位置和第i - 1个空余位置相邻或者不相邻。
相邻的话只要比较第i个数和第i - 1个数，不相邻的话要比较第i个数和它的前一个以及第i - 1个数和它后一个。
有以下几个注意点：
- j要比第i个数+第i - 1个数大，当然比i要小。
- （方便起见我给i = 1的时候赋了初值）赋初值得时候也需要分类，判断第一个空余位置是否在原排列的第一位，不然还要判断第一个数和它之前的数字对答案的贡献。
- 最后结束别忘了如果最后一个空余位置在原序列不是最后，也要计算贡献。
代码如下：
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #define rep(x, l, r) for(int x = l; x <= r; x++)
7 #define repd(x, r, l) for(int x = r; x >= l; x--)
8 #define clr(x, y) memset(x, y, sizeof(x))
9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN 105
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long ll;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 1000000009;
22 int lowbit(int x){ return x & (-x);}
23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
24
25 int id[MAXN], a[MAXN], dp[MAXN][MAXN][2];
26
27 int main(){
28 int n, m = 0;
29 scanf("%d", &n);
30 int tot1 = 0;
31 rep(i, 1, n){
32 int x;
33 scanf("%d", &x);
34 if(!x){
35 m++;
36 id[m] = i;
37 a[i] = -1;
38 }
39 else{
40 a[i] = x % 2;
41 if(x % 2) tot1++;
42 }
43 }
44 int l = (n + 1) / 2 - tot1;
45 rep(i, 1, m)
46 rep(j, 0, l)
47 rep(k, 0, 1) dp[i][j][k] = INF;
48 if(id[1] == 1){
49 dp[1][0][0] = 0;
50 dp[1][1][1] = 0;
51 }
52 else{
53 dp[1][0][0] = 0 ^ a[id[1] - 1];
54 dp[1][1][1] = 1 ^ a[id[1] - 1];
55 }
56 rep(i, 2, m)
57 rep(j, 0, min(i, l))
58 rep(k, 0, 1){
59 dp[i][j][k] = INF;
60 if(j < k) continue;
61 if(id[i - 1] < id[i] - 1){
62 dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - k][0] + (0 ^ a[id[i - 1] + 1]) + (k ^ a[id[i] - 1]));
63 if(j >= k + 1) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - k][1] + (1 ^ a[id[i - 1] + 1]) + (k ^ a[id[i] - 1]));
64 }
65 else{
66 dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - k][0] + (0 ^ k));
67 if(j >= k + 1) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - k][1] + (1 ^ k));
68 }
69 }
70 int s1 = dp[m][l][0], s2 = dp[m][l][1];
71 if(id[m] != n){
72 s1 += 0 ^ a[id[m] + 1];
73 s2 += 1 ^ a[id[m] + 1];
74 }
75 int ans = min(s1, s2);
76 rep(i, 1, n - 1){
77 if(a[i] == -1 || a[i + 1] == -1) continue;
78 ans += a[i] ^ a[i + 1];
79 }
80 printf("%d\n", ans);
81 return 0;
82 }
D.Numbers on Tree
题目大意：有一颗有根树，每一个节点有一个值ai，用ci表示以i为根的子树中比i小的节点的j个数（即aj < ai）。现在给你n和c数组，让你给出满足以上条件的任意一种a的方案。
这题一开始完全不会，百度了题解后才过的：大佬的题解
我们发现一个子树整体无论变化多少，这个子树中所有节点都是满足情况的。
并且一个子树中只要大小关系保持不变，怎么变化也都是满足情况的。
那么我们只要将当前节点的子树按照原来节点的值排个序。每个节点的值直接改成它的编号，还是满足条件。
至于当前节点u，在这些节点的上面不会产生影响，只需要在编号c[u]处插入，后面的节点都忘后移就好（反正n才2000，够我们玩）。
当一个点的时候直接是1（就是c[u] + 1）了。
这边为了方便排序使用pair，表示节点的值和这个节点的数。
代码如下:
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #define rep(x, l, r) for(int x = l; x <= r; x++)
7 #define repd(x, r, l) for(int x = r; x >= l; x--)
8 #define clr(x, y) memset(x, y, sizeof(x))
9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN 2005
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long ll;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 1000000009;
22 int lowbit(int x){ return x & (-x);}
23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}
24
25 int c[MAXN], ans[MAXN], sz[MAXN];
26 vi edge[MAXN];
27 vector<pii> ve[MAXN];
28
29 void dfs(int u){
30 ve[u].clear();
31 sz[u] = 1;
32 rep(i, 0, SZ(edge[u]) - 1){
33 int v = edge[u][i];
34 dfs(v);
35 sz[u] += sz[v];
36 rep(j, 0, SZ(ve[v]) - 1) ve[u].pb(ve[v][j]);
37 }
38 if(c[u] >= sz[u]){
39 puts("NO");
40 exit(0);
41 }
42 sort(all(ve[u]));
43 rep(i, 0, SZ(ve[u]) - 1) ve[u][i].fi = i + 1;
44 ve[u].insert(ve[u].begin() + c[u], mp(c[u] + 1, u));
45 rep(i, c[u] + 1, SZ(ve[u]) - 1) ve[u][i].fi++;
46 }
47
48 int main(){
49 int n;
50 scanf("%d", &n);
51 int root;
52 rep(i, 1, n){
53 int fa;
54 scanf("%d%d", &fa, &c[i]);
55 if(!fa) root = i;
56 else edge[fa].pb(i);
57 }
58 dfs(root);
59 puts("YES");
60 sort(all(ve[root]));
61 rep(i, 0, SZ(ve[root]) - 1) ans[ve[root][i].se] = ve[root][i].fi;
62 rep(i, 1, n) printf("%d ", ans[i]);
63 puts("");
64 return 0;
65 }
加载全部内容