Codeforces Round #612 (Div. 2) 前四题题解

Codeforces Round #612 (Div. 2) 前四题题解

这场比赛的出题人挺有意思，全部magic成了青色。

还有题目中的图片特别有趣。

晚上没打，开virtual contest打的，就会前三道，我太菜了。

最后看着题解补了第四道。

比赛传送门

A. Angry Students

题目大意：有t队学生，每个学生有两种状态，生气（A）或不生气（P）。（话说为什么生气的戴着圣诞帽哇）所有生气的人都会往前一个人丢雪球，被丢到的人也会变得生气，也会丢雪球。问你每队人中最后一个学生变得生气的时刻。

这题就是统计最长的连续的'P'当然前提是左边有生气的人。

代码如下：

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 #define rep(x, l, r) for(int x = l; x <= r; x++)
 #define repd(x, r, l) for(int x = r; x >= l; x--)
 #define clr(x, y) memset(x, y, sizeof(x))
 #define all(x) x.begin(), x.end()
 #define pb push_back
 #define mp make_pair
 #define MAXN 105
 #define fi first
 #define se second
 #define SZ(x) ((int)x.size())
 using namespace std;
 typedef long long ll;
 typedef vector<int> vi;
 typedef pair<int, int> pii;
 const int INF =  << ;
 const int p = ;
 int lowbit(int x){ return x & (-x);}
 int fast_power(int a, int b){ int x; for(x = ; b; b >>= ){ if(b & ) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

 char st[MAXN];

 int main(){
     int t;
     scanf("%d", &t);
     while(t--){
         int n;
         scanf("%d", &n);
         scanf("%s", st);
         int flag = , ans = , sum = ;
         rep(i, , n - ){
             if(st[i] == 'A'){
                 flag = ;
                 sum = ;
             }
             if(st[i] == 'P' && flag){
                 sum++;
                 ans = max(ans, sum);
             }
         }
         printf("%d\n", ans);
     }
     return ;
 }

-A

B.Hyperset

题目大意：有n张卡，每张卡有k个特征，每个特征有三种（'S', 'E', 'T'），让你选出三张卡组成一套，使得三张卡中的每个特征全部相等或者全部不同。如样例三中的"SETT", "TEST", "EEET"是一套，"TEST", "ESTE", "STES"也是一套，问一共能选出几套。

这题数据很小，n在1500以内，把所有状态直接改为三进制数也是在longlong范围内，怎么做都行。

我的解法极其繁杂，转成数字后离散化再进行计数。

先枚举两张卡i和j，这样可以直接求出第三张卡的状态（如果前两张相同，第三张也相同，如果前两张不同，第三张就是剩下的那种），答案加上符合该种状态卡的个数。

又臭又长的代码：

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 #include <map>
 #define rep(x, l, r) for(int x = l; x <= r; x++)
 #define repd(x, r, l) for(int x = r; x >= l; x--)
 #define clr(x, y) memset(x, y, sizeof(x))
 #define all(x) x.begin(), x.end()
 #define pb push_back
 #define mp make_pair
 #define MAXN 1505
 #define MAXM 35
 #define fi first
 #define se second
 #define SZ(x) ((int)x.size())
 using namespace std;
 typedef long long ll;
 typedef vector<int> vi;
 typedef pair<int, int> pii;
 const int INF =  << ;
 const int p = ;
 int lowbit(int x){ return x & (-x);}
 int fast_power(int a, int b){ int x; for(x = ; b; b >>= ){ if(b & ) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

 map<ll, int> Rank;
 char st[MAXM];
 int a[MAXN][MAXM], c[MAXN], sum[MAXN];
 ll num[MAXN], b[MAXN];

 int judge(char ch){
     if(ch == 'S') return ;
     if(ch == 'E') return ;
     if(ch == 'T') return ;
 }

 int main(){
     int n, len;
     scanf("%d%d", &n, &len);
     rep(i, , n){
         scanf("%s", st);
         rep(j, , len - ){
             num[i] = num[i] *  + judge(st[j]);
             a[i][j + ] = judge(st[j]);
         }
         b[i] = num[i];
     }
     sort(b + , b + n + );
     rep(i, , n) Rank[b[i]] = i;
     rep(i, , n) c[i] = Rank[num[i]];
     int ans = ;
     rep(i, , n){
         rep(j, i + , n){
             ll s = ;
             rep(k, , len){
                 int x = ( - a[i][k] - a[j][k]) % ;
                 s = s *  + x;
             }
             if(Rank.find(s) != Rank.end()) ans += sum[Rank[s]];
         }
         sum[c[i]]++;
     }
     printf("%d\n", ans);
     return ;
 }

-B

C.Garland

题目大意：有一个由[ 1…n ]组成的排列，其中有一些数被取走了（取走的数用0表示），现在将这些数放回这些空余的位置中。序列中每有相邻一对数的奇偶性不同就会增加序列的复杂度，求复杂度最小为多少。

这题我是在大佬的提示下才做出来的。

首先看到这个奇偶性，那么就不客气了，把数字直接给丢了留个膜2的余数就好。

现在问题变成了再剩余的位置放0/1使得相邻的复杂度最小。

虽然codeforces上这题的算法标签标了个greedy，但是我没搞懂这题怎么贪。

但是我们发现放的数为多少只会对后一个数字产生影响，所以可以用动态规划。

状态为放了i个数，用了j个1，这个数放的是0/1。

转移分两种第i个空余位置和第i - 1个空余位置相邻或者不相邻。

相邻的话只要比较第i个数和第i - 1个数，不相邻的话要比较第i个数和它的前一个以及第i - 1个数和它后一个。

有以下几个注意点：

1. j要比第i个数+第i - 1个数大，当然比i要小。
2. （方便起见我给i = 1的时候赋了初值）赋初值得时候也需要分类，判断第一个空余位置是否在原排列的第一位，不然还要判断第一个数和它之前的数字对答案的贡献。
3. 最后结束别忘了如果最后一个空余位置在原序列不是最后，也要计算贡献。

代码如下：

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 #define rep(x, l, r) for(int x = l; x <= r; x++)
 #define repd(x, r, l) for(int x = r; x >= l; x--)
 #define clr(x, y) memset(x, y, sizeof(x))
 #define all(x) x.begin(), x.end()
 #define pb push_back
 #define mp make_pair
 #define MAXN 105
 #define fi first
 #define se second
 #define SZ(x) ((int)x.size())
 using namespace std;
 typedef long long ll;
 typedef vector<int> vi;
 typedef pair<int, int> pii;
 const int INF =  << ;
 const int p = ;
 int lowbit(int x){ return x & (-x);}
 int fast_power(int a, int b){ int x; for(x = ; b; b >>= ){ if(b & ) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

 int id[MAXN], a[MAXN], dp[MAXN][MAXN][];

 int main(){
     int n, m = ;
     scanf("%d", &n);
     int tot1 = ;
     rep(i, , n){
         int x;
         scanf("%d", &x);
         if(!x){
             m++;
             id[m] = i;
             a[i] = -;
         }
         else{
             a[i] = x % ;
             if(x % ) tot1++;
         }
     }
     int l = (n + ) /  - tot1;
     rep(i, , m)
         rep(j, , l)
             rep(k, , ) dp[i][j][k] = INF;
     if(id[] == ){
         dp[][][] = ;
         dp[][][] = ;
     }
     else{
         dp[][][] =  ^ a[id[] - ];
         dp[][][] =  ^ a[id[] - ];
     }
     rep(i, , m)
         rep(j, , min(i, l))
             rep(k, , ){
                 dp[i][j][k] = INF;
                 if(j < k) continue;
                 if(id[i - ] < id[i] - ){
                     dp[i][j][k] = min(dp[i][j][k], dp[i - ][j - k][] + ( ^ a[id[i - ] + ]) + (k ^ a[id[i] - ]));
                     if(j >= k + ) dp[i][j][k] = min(dp[i][j][k], dp[i - ][j - k][] + ( ^ a[id[i - ] + ]) + (k ^ a[id[i] - ]));
                 }
                 else{
                     dp[i][j][k] = min(dp[i][j][k], dp[i - ][j - k][] + ( ^ k));
                     if(j >= k + ) dp[i][j][k] = min(dp[i][j][k], dp[i - ][j - k][] + ( ^ k));
                 }
             }
     int s1 = dp[m][l][], s2 = dp[m][l][];
     if(id[m] != n){
         s1 +=  ^ a[id[m] + ];
         s2 +=  ^ a[id[m] + ];
     }
     int ans = min(s1, s2);
     rep(i, , n - ){
         if(a[i] == - || a[i + ] == -) continue;
         ans += a[i] ^ a[i + ];
     }
     printf("%d\n", ans);
     return ;
 }

-C

D.Numbers on Tree

题目大意：有一颗有根树，每一个节点有一个值a_i，用c_i表示以i为根的子树中比i小的节点的j个数（即a_j < a_i）。现在给你n和c数组，让你给出满足以上条件的任意一种a的方案。

这题一开始完全不会，百度了题解后才过的：大佬的题解

我们发现一个子树整体无论变化多少，这个子树中所有节点都是满足情况的。

并且一个子树中只要大小关系保持不变，怎么变化也都是满足情况的。

那么我们只要将当前节点的子树按照原来节点的值排个序。每个节点的值直接改成它的编号，还是满足条件。

至于当前节点u，在这些节点的上面不会产生影响，只需要在编号c[u]处插入，后面的节点都忘后移就好（反正n才2000，够我们玩）。

当一个点的时候直接是1（就是c[u] + 1）了。

这边为了方便排序使用pair，表示节点的值和这个节点的数。

代码如下:

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 #define rep(x, l, r) for(int x = l; x <= r; x++)
 #define repd(x, r, l) for(int x = r; x >= l; x--)
 #define clr(x, y) memset(x, y, sizeof(x))
 #define all(x) x.begin(), x.end()
 #define pb push_back
 #define mp make_pair
 #define MAXN 2005
 #define fi first
 #define se second
 #define SZ(x) ((int)x.size())
 using namespace std;
 typedef long long ll;
 typedef vector<int> vi;
 typedef pair<int, int> pii;
 const int INF =  << ;
 const int p = ;
 int lowbit(int x){ return x & (-x);}
 int fast_power(int a, int b){ int x; for(x = ; b; b >>= ){ if(b & ) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;}

 int c[MAXN], ans[MAXN], sz[MAXN];
 vi edge[MAXN];
 vector<pii> ve[MAXN];

 void dfs(int u){
     ve[u].clear();
     sz[u] = ;
     rep(i, , SZ(edge[u]) - ){
         int v = edge[u][i];
         dfs(v);
         sz[u] += sz[v];
         rep(j, , SZ(ve[v]) - ) ve[u].pb(ve[v][j]);
     }
     if(c[u] >= sz[u]){
         puts("NO");
         exit();
     }
     sort(all(ve[u]));
     rep(i, , SZ(ve[u]) - ) ve[u][i].fi = i + ;
     ve[u].insert(ve[u].begin() + c[u], mp(c[u] + , u));
     rep(i, c[u] + , SZ(ve[u]) - ) ve[u][i].fi++;
 }

 int main(){
     int n;
     scanf("%d", &n);
     int root;
     rep(i, , n){
         int fa;
         scanf("%d%d", &fa, &c[i]);
         if(!fa) root = i;
         else edge[fa].pb(i);
     }
     dfs(root);
     puts("YES");
     sort(all(ve[root]));
     rep(i, , SZ(ve[root]) - ) ans[ve[root][i].se] = ve[root][i].fi;
     rep(i, , n) printf("%d ", ans[i]);
     puts("");
     return ;
 }

-D