本文主要是介绍Codeforces Round 968 (Div. 2) ABCD1D2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
背景
重感冒，所以迟发了www
A题：Turtle and Good Strings
思路
如果字符串的开头不等于末尾，那么就可以截取n-1个作为s1，剩下1个作为s2，这样是符合题意的。反之，如果相等，那么无论怎么取都无法满足题意。这是一个对立条件，故可以直接拿来进行判断
代码
inline void solve() {int n; cin >> n;string s; cin >> s;s = ' ' + s;cout << (s[1] == s[n] ? "NO" : "YES") << endl;return;
}B题：Turtle and Piggy Are Playing a Game 2
思路
给定一个数组，T每次可以删去选定的两个相邻元素中较小的一个，而P会删去较大的一个。
如果这么理解就清楚多了，我们贪心地想，T一定是删去最小的，而P一定是删去最大的，按题意模拟即可
这样是输出n/2+1大的元素
代码
inline void solve() {int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];sort(a.begin() + 1, a.end());cout << a[n / 2 + 1] << endl;return;
}C题：Turtle and Good Pairs
思路
众生平等构造题
显然地，如果相邻的两个元素不同的组数越多，答案越大
这样怎么构造呢？放了一个字符后，放下一个不是它的字符即可
最后可能会剩余3个d等等情况，我们还是照样放最后面，因为按照题意，它也是good的
复杂度 26n
代码
inline void solve() {int n; cin >> n;string s; cin >> s;s = ' ' + s;if (n <= 3) return cout << s.substr(1) << endl, void();vector<int> a(26);for (int i = 1; i <= n; i ++ ) a[s[i] - 'a'] += 1;while (true) {bool flag = false;for (int i = 0; i < 26; i ++ ) {if (a[i]) {flag = true;cout << char('a' + i);a[i] -= 1;}}if (!flag) break;}cout << endl;return;
}D1：Turtle and a MEX 问题 (Easy Version)
思路
3 4
2 0 2
3 2 3 3
4 7 0 1 5
这三个数组的mex1分别为1，0，2
如果x分别与之相等的情况下，数组的mex还可以增长
可以得到mex2: 3，1，3
得到的关系为
1-3
0-1
2-3
可以抽象成一个有向无环图
0-1-3
2-3
在任意次操作下，根据mex的定义，给定的任意一个x，都可以变成mex1中的元素，然后在图中向下遍历
所以任意一个x都可以变成mex2中的最大元素
因为还可以不操作，所以我们只要将x和最大的mex2比较取大即可
这过程中用到了等差数列
代码
inline void solve() {int n, m; cin >> n >> m;int mex = 0;for (int i = 1; i <= n; i ++ ) {int num; cin >> num;set<int> s;for (int j = 1; j <= num; j ++ ) {int x; cin >> x;s.insert(x);}int cur = 0;bool flag = true;while (true) {if (!s.count(cur)) {if (flag) flag = false;else break;}cur += 1;}mex = max(mex, cur);}if (mex >= m) cout << (ll)mex * (m + 1) << endl;else cout << (ll)mex * (mex + 1) + (ll)(mex + 1 + m) * (m - mex) / 2 << endl;return;
}D2:Turtle and a MEX 问题 (Hard Version)
思路
因为只能每个数组操作一次了，一开始我们可以定义一个默认值M，意为任意的x都可以直接变成M
对于任意的x，都可以花费一次操作到mex1中的任意元素，所以我们又可以将M定义为mex1中最大的一个元素
我们再进行分类讨论
如果x是mex1中的元素
1:它可以继续往下遍历，成为“它可以遍历的到的最大mex2”
2:立刻变成M
3:不操作
如果x不是mex1中的元素
1:立刻变成M
2:不操作
这个M怎么求呢？
我们注意到
如果出现了
1-3
3-5
3-4
这种情况，我们先将它连成图，是
1-3-4
-5
这个3可以前往4或者5，
因为是3-4和3-5
所以我们可以花费一次操作变成3，然后往下遍历4或者5任意一支
这样就还可以更新M了，因为要最大，所以可以更新为所有分支中的最大一个
最后还是等差数列求和，不过有些因为可以变大，所以我们可以用一个extra存其变化
此题细节较多，代码较烦，难度分2000
代码
inline void solve() {ll n, m; cin >> n >> m;map<int, vector<int>> tr;map<ll, ll> to;ll M = 0;for (int i = 1; i <= n; i ++ ) {int num; cin >> num;set< int > s;for (int j = 1; j <= num; j ++ ) {int x; cin >> x;s.insert(x);}bool flag = false;ll cur = 0, mex;while (true) {if (!s.count(cur)) {if (flag) {tr[mex].push_back(cur);to[cur] = cur;break;}mex = cur;M = max(M, mex);flag = true;}cur += 1;}}for (int i = M; i >= 0; i -- ) {if (tr[i].size()) {if (tr[i].size() > 1) {for (int v : tr[i]) {to[i] = max(to[i], to[v]);}M = max(M, to[i]);}else to[i] = max(to[i], to[tr[i][0]]);}}ll extra = 0;for (auto [x, y] : to) {if (x > m) break;if (x <= M) extra += max(y, M) - M;else extra += max({x, y, M}) - x;}if (M >= m) cout << extra + M * (m + 1) << endl;else cout << extra + M * (M + 1) + (M + 1 + m) * (m - M) / 2 << endl;return;
}这篇关于Codeforces Round 968 (Div. 2) ABCD1D2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
