Codeforces Round 968 (Div. 2)

A. Turtle and Good Strings

思路：题意大致为把一个字符串分成若干段，要求每两段，前一段的首字符不能等于后的一段的尾字符，给你一个字符串，能不能构造出合法方案。观察到，分的段数越小，越有助于我们判断。所以，不妨分成两段，问题转化为判断首尾字符是否相等。

代码：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
void solve()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        string s;
        int n;
        cin >> n >> s;
        if (s[0] != s[n - 1])
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}

B. Turtle and Piggy Are Playing a Game 2

思路：题意可以转化成，为了最大化最后剩下的数，每次先手能删除当前最大的数，每次后手能删除当前最小的数。 所以答案是原序列的第 $$\lfloor \frac {n}{2} \rfloor + 1$$ 小的数。

代码：

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n' 
#define pii pair<int,int>
#define debug(x) cout<<"x = "<<x<<endl;
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 5e5 + 5,P = 13331;
int a[N],n;
void solve() {
    int T = 1;
    cin>>T;
    while(T --) {
        cin >> n;
        for (int i = 1; i <= n; i ++)
            cin >> a[i];
        sort(a + 1, a + 1 + n);
        int cnt = n - 1,l;
        if(cnt&1)
        {
            l = cnt / 2 + 1;
        }
        else 
        {
            l = r = cnt / 2;
        }
        cout << a[l + 1] << endl;
   }
}
signed main() {
    ios;
    solve();
    return 0;
}

C. Turtle and Good Pairs

思路：既然题目让我们最大化好对的数量，那我们不让去分类讨论一下那些 $$(i,j)$$ 是好对。

1. 若 $$S_i=S_j$$，那么 $$(i,j)$$ 是一个好对。
2. 若 $$S_i \neq S_j$$ ，且 $$\exists k \in [i,j)$$ 使得 $$S_k \neq S_i \and S_k \neq S_j$$，那么 $$(i,j)$$ 是一个好对。

不妨把 $$S$$ 划分成若干个由相同字符组成的连续段，那么如果 $$(i,j)$$ 为好对，则 $$i$$ 所在的连续段和 $$j$$ 所在的连续段必然不相邻。令 $$m$$ 为字符串 $$S$$ 连续段的数量，$$a_i$$ 为第 $$i$$ 段的长度，那么好对数量应为 $$\frac{n(n-1)}{2}-\sum_{i=1}^{m-1}a_ia_{i+1}$$，问题转化为令 $$\sum_{i=1}^{m-1}a_i*a_{i+1}$$ 最小。我们只需这样构造，令每一个字符不等于上一个字符，当只剩余一个字符时，全放在字符串最后即可。

代码：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
struct node
{
    int id, num;
    bool operator<(const node &u) const
    {
        return num < u.num;
    }
};
int n;
void solve()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        node a[26];
        cin >> n;
        char c;
        for (int i = 0; i < 26; i++)
            a[i].id = i, a[i].num = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> c;
            a[c - 'a'].num++;
        }
        sort(a, a + 26);
        int st = 0, ed = 25;
        while (a[st].num == 0)
            st++;
        int cnt = 0;
        while (cnt < n)
        {
            if (cnt % 2 == 0)
            {
                if (a[ed].num == 0)
                {
                    ed--;
                }
                cout << (char)('a' + a[ed].id);
                a[ed].num--;
                cnt++;
            }
            else
            {
                if (a[st].num == 0)
                {
                    st++;
                }
                cout << (char)('a' + a[st].id);
                a[st].num--;
                cnt++;
            }
        }
        cout << endl;
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

思路：思路很好想到，设 $$u_i$$ 为序列 $$i$$ 最小的没有出现的非负整数，$$v_i$$ 为序列 $$i$$ 次小的没有出现的非负整数，容易发现 $$x$$ 经过若干次操作，最大值为 $$\max(\sum^n_{i=1}v_i,x)$$。不让设 $$\sum^n_{i=1}v_i$$ 为 $$k$$，则最后的答案为 $$\sum_{i=0}^{kk+\sum_{i=k+1}}mi$$，因为 $$m \leq 10^9$$，所以后面那一段需要用等差数列求和公式。（赛时脑抽了，没注意到...）

代码：

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define pii pair<int, int>
#define debug(x) cout << "x = " << x << endl;
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 5e5 + 5, P = 13331;
map<int, int> mp;
void solve()
{
    int T = 1;
    cin >> T;
    while (T--)
    {
        int mx = 0, n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            int l;
            cin >> l;
            mp.clear();
            for (int j = 1, x; j <= l; j++)
            {
                cin >> x;
                mp[x] = 1;
            }
            bool f = false;
            for (int j = 0; j <= l + 2; j++)
            {
                if (mp[j] == 0)
                {
                    if (!f)
                        f = true;
                    else
                    {
                        mx = max(mx, j);
                        break;
                    }
                }
            }
        }
        int cnt1 = min(mx, m) + 1, cnt2 = max(m - mx, (int)0);
        int ans = cnt1 * mx + (mx + 1 + m) * cnt2 / 2;
        cout << ans << endl;
    }
}
signed main()
{
    ios;
    solve();
    return 0;
}

D2. Turtle and a MEX Problem (Hard Version)

待补......