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;
}