Codeforces Round 968 (Div. 2)

本文主要是介绍Codeforces Round 968 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

掉大分的一场比赛aaa

原因是 D1 看错条件了一直在想 D2 最后还没想出来。

Standings：6922

题目链接：Dashboard - Codeforces Round 968 (Div. 2) - Codeforces

A. Turtle and Good Strings

题意：

给一个字符串，判断是否能把它分成 k（k >= 2）个连续的段，使得每一段的起点和其他任意一段的终点不相等。

思路：

首先注意到首字母一定是第一段的开头，尾字母一定是最后一段的结尾，那么只要这两个字母不相等我们就有办法分割（直接 1 ~ n-1 作一段，n 单独作一段即可），反之无解。

#include<cstdio>
#include<cstring>
using namespace std;int T,n;
char s[105];int main()
{scanf("%d",&T);while (T --){scanf("%d",&n);scanf("%s",s + 1);if(s[1] == s[n]) printf("No\n");else printf("Yes\n");}return 0;
}

B. Turtle and Piggy Are Playing a Game 2

题意：

给一个序列，A 每次可以移除相邻两个数中较小的那个数，B 每次可以移除相邻两个数中较大的那个数，A 想要使最后剩下的那个数最大，B 想要使最后剩下的那个数最小，两个人都以最优方案操作，A 先开始，求最后剩下的那个数。

思路：

显然每次 A 会移除一个最小的数，B 会移除一个最大的数，于是把序列从小到大排序，最后剩下的数就是排名第 $\lfloor \frac{n}{2} \rfloor + 1$ 的数。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;#define N 100005int T,n,a[N],ans;int main()
{scanf("%d",&T);while (T --){scanf("%d",&n);for (int i = 1;i <= n;++ i) scanf("%d",&a[i]);sort(a + 1,a + n + 1);printf("%d\n",a[n / 2 + 1]);}return 0;
}

C. Turtle and Good Pairs

题意：

给一个字符串。

定义 “ pleasant pair ” (i,j) 为当前仅当存在一个 k (i <= k < j) 满足以下条件的数对：

1. $s_k \neq s_{k + 1}$

2. $s_k \neq s_i$ or $s_{k + 1} \neq s_j$

定义 “ good pair ” (i,j) 为当且仅当 $s_i = s_j$ 或者 (i,j) 是 “ pleasant pair ” 的数对。

你需要重排这个字符串，使得 “ good pair ” 的数目尽量多。

思路：

正难则反，我们可以发现 “not good pair” 会满足 “A...AB...B” 这种形式，其中 A 和 B 出现一次以上，且这个子串中只有 A，B 两种字母。

手玩一下可以发现我们想要这些 “not good pair” 尽量少，就得把相同字母尽量都隔开，于是有一个贪心的构造方法：按相同字母出现次数从大到小排序，以黑白相间的方式轮流插入。

注意输出的时候用 cout 貌似会比 printf 快很多。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;#define N 200005int T,n;
char s[N];struct Node
{int id,val;
}a[30];int cmp(Node x,Node y) { return x.val > y.val ; }int main()
{scanf("%d",&T);while (T --){scanf("%d",&n);scanf("%s",s + 1);for (int i = 0;i < 26;++ i) a[i].id = i,a[i].val = 0;for (int i = 1;i <= n;++ i) ++ a[s[i] - 'a'].val;sort(a,a + 26,cmp);int now = a[0].id;int tmp = a[0].val;for (int i = 1;i < 26;++ i){if(!a[i].val) break;if(now == a[i].id) continue;if(a[i].val < tmp){for (int j = 1;j <= a[i].val;++ j)cout << char('a' + now) << char('a' + a[i].id);tmp -= a[i].val;}else if(a[i].val == tmp){for (int j = 1;j <= a[i].val;++ j)cout << char('a' + now) << char('a' + a[i].id);if(i <= 24) tmp = a[i + 1].val,now = a[i + 1].id;else tmp = 0;}else{for (int j = 1;j <= tmp;++ j)cout << char('a' + a[i].id) << char('a' + now);now = a[i].id,tmp = a[i].val - tmp;}}if(tmp){for (int j = 1;j <= tmp;++ j) cout << char('a' + now);}cout << endl;}return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

题意：

给若干个序列和一个数 m ，你可以通过这些数列对 m 做任意次操作，每次操作选择一个数列，将 m 插入这个数列得到一个新的数列 a ，然后让 m = MEX(a) 。设 f(i) 表示 m = i 的时候能通过操作得到的最大值（每个序列可以用无数次），求 $\sum_{i = 0} ^ m f(i)$ 。

思路：

由于每个序列可以用无数次，那么显然某个数 x 要么不操作，要么就选定一个数列操作两次。我们统计每个数列的 mex1 和 mex2 ，分别记作 v1 和 v2 ，那么操作一次可能得到 v1 或者 v2，操作两次一定会得到 v2 ，操作三次以上都再也不能使得到的值更大了。

记所有 v2 的 max 为 mx，那么对于比 mx 大的 x ，显然不需要进行操作；对于小于等于 mx 的 x ，显然能通过操作得到的最大值就是 mx 了。

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;#define N 200005int T,n,m,l[N],mx,p[N];
long long ans;struct Node
{int v1,v2;
}a[N];int max(int x,int y) { return x > y ? x : y ; }int min(int x,int y) { return x < y ? x : y ; }int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&m),mx = 0;for (int i = 1;i <= n;++ i){map<int, int> vis;scanf("%d",&l[i]);for (int j = 1,x;j <= l[i];++ j)scanf("%d",&x),vis[x] = 1;int now = 0;for (int j = 0;j <= l[i] + 2;++ j){if(now >= 2) break;if(!vis[j]){if(!now) a[i].v1 = j;else a[i].v2 = j;++ now;}}mx = max(mx,a[i].v2);}if(m > mx) ans = 1ll * (mx + 1 + m) * (m - mx) / 2ll;else ans = 0ll;ans += 1ll * min(m + 1,mx + 1) * mx;printf("%lld\n",ans);}return 0;
}

D2. Turtle and a MEX Problem (Hard Version)

题意：

和 Easy Version 唯一的区别就是每个数列只能用至多一次。

思路：

限定了每个序列的操作次数为 1 ，这里有个很妙的 trick ，就是把抽象的操作具化到图上：这里我们可以建一条边由 v1 指向 v2 ，走过这条边就表示把值从 v1 变成 v2 ，每条边只可以走一次。注意到 v1 < v2 是恒成立的，于是我们建出来的图就是一个 DAG ，我们接下来在 DAG 上 dp 即可。设 fi 表示从点 i 出发可以到达的最大的点，可以通过倒序DP解决。

那么对于大于 mx 的 x ，我们同样无需操作；对于小于等于 mx 的 x ，我们要么直接从 x 的出边走到最大的那个点，要么选择一个 “有两条以上出边” 的点，删掉这个点的一条出边再走，走到最大的那个点。

后者的操作实际上是将 x 先变成某一个 v1 再进行操作，在把 x 变成 v1 的时候相当于选择了 v1 所在的某个序列先得到了 v1，于是这个序列不能再用了，这等价于在图上先删掉了 v1 的一条出边再走，而删掉的这条边可以是任意一条出边，因为任何一个 v1 所在的序列都可以得到 v1 。

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
using namespace std;#define N 200005int T,n,m,l[N],mx,mxn,p[N],f[N];
long long ans;struct Node
{int v1,v2;
}a[N];int max(int x,int y) { return x > y ? x : y ; }int min(int x,int y) { return x < y ? x : y ; }void solve()
{vector<int> v[mx + 1];int tmp = 0;for (int i = 0;i <= mx;++ i) f[i] = i;for (int i = 1;i <= n;++ i) v[a[i].v1].push_back(a[i].v2);for (int i = mx;i >= 0;-- i){for (auto j : v[i]) f[i] = max(f[i],f[j]);if(int(v[i].size()) > 1) tmp = max(tmp,f[i]);}for (int i = 0;i <= min(mx,m);++ i) ans += 1ll * max(mxn,max(i,max(f[i],tmp)));return;
}int main()
{scanf("%d",&T);while (T --){scanf("%d%d",&n,&m),mx = mxn = 0;for (int i = 1;i <= n;++ i){map<int, int> vis;scanf("%d",&l[i]);for (int j = 1,x;j <= l[i];++ j)scanf("%d",&x),vis[x] = 1;int now = 0;for (int j = 0;j <= l[i] + 2;++ j){if(now >= 2) break;if(!vis[j]){if(!now) a[i].v1 = j;else a[i].v2 = j;++ now;}}mxn = max(mxn,a[i].v1);mx = max(mx,a[i].v2);}if(m > mx) ans = 1ll * (mx + 1 + m) * (m - mx) / 2ll;else ans = 0ll;solve();printf("%lld\n",ans);}return 0;
}