脑电波场(对于 A 到 D, 因为 fvv xkm 不会 E).

A. Turtle and Good Strings

第一个串的首字母要和后面的所有串的末尾字母不同, 显然是分的串数 \(> 2\) 就会比只分成两串的限制强, 且包含只分成两串的限制.

那么只要考虑分成两串, 也就是判断原串首尾字母是否相等即可.

B. Turtle and Piggy Are Playing a Game 2

发现两人的操作是很类似的, 一个是删掉一个大的数, 一个是删掉一个小的数, 很公平, 然后就猜到类似中位数的东西了.

笨蛋 xkm 不会证明.

C. Turtle and Good Pairs

由题意可得:

• \(s_i \neq s_j\) 时, \(i\) 和 \(j\) 之间只要有一个不为 \(s_i\) or \(s_j\) 的值就行.
• 对于 \(s_i = s_j\) 的情况, 无论怎么排都是产生一样的贡献.

那么就尽可能的在 \(s_i \neq s_j\) 的 \(i\) 和 \(j\) 间塞上一个不一样的数.

那么输出类似 \(a \to z + a \to z\) 这样的序列即可.

D1. Turtle and a MEX Problem (Easy Version)

对于一个序列, 我们操作后能得到什么呢?

• 得到这个序列的 \(mex\) —- 记为 \(mex1\)
• 得到这个{序列 + \(mex1\)} 的 \(mex\) —- 记为 \(mex2\)

那么我们初始值为 \(x\), 能得到的就是 \(max(x, maxof(mex2))\), 故 \(f(x)\) 是个前面恒为 \(maxof(mex2)\) , 后面为 \(x\) 的分段函数, 容易求和.

D2. Turtle and a MEX Problem (Hard Version)

本题每个序列只能用一次, 但我们还是考虑 \(mex1\) 和 \(mex2\).

\(f(x)\) 可能有几种来源:

• 为 \(x\).
• \(x\) 经过一个序列操作, 得到某个 \(mex2\), 此时 \(x\) 对应这个 \(mex2\) 的 \(mex1\).
• \(x\) 经过一个序列操作, 得到某个 \(mex1\).
• 上述的 \(mex\) 对应的 \(f(mex)\), 以及递归下去.

那么可以考虑记忆化搜索: \(f_x\) 为初始为 \(x\) 能得到的最大值.

\(f_x =\) :

• \(x\) 对应的所有的 \(mex2\) 的 \(f_{mex2}\).
• \(x\) 本身

另外我们对一个序列操作还可能得到这个序列的 \(mex1\), 这样就不能再走这个序列. 当 \(mex1\) 的数量为 \(1\) 时, 不能转移, 结果为 \(mex1\); 不为 \(1\) 时, 可转移到 \(mex2\), 结果也就和 \(f_{mex1}\) 相等. 找到这样得到的最大值, 记为 \(minn\).

因为得到 \(mex1\) 是不看初始值的, 我们令 \(f_i = max(f_i, minn)\).

对 \(f\) 求和得到答案.

显然 \(mex2\) 有限, 对于超出极限的部分等差数列求和即可.

code

const int N = 2e5 + 10;
vector<int> have(N);
void solve() {
    LL n, m;
    cin >> n >> m;
    map<int, int> cnt1, cnt2;
    map<int, vector<int>> two2one, one2two;
    int maxx = 0;
    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        maxx = max(maxx, l);
        fill(have.begin(), have.begin() + l + 2, 0);
        while (l--) {
            int temp;
            cin >> temp;
            if (temp < N)
                have[temp] = 1;
        }
        int tp = -1;
        for (int i = 0; i < N; i++) {
            if (have[i] == 0) {
                if (tp == -1) {
                    tp = i;
                    cnt1[i]++;
                } else {
                    cnt2[i]++;
                    one2two[tp].push_back(i);
                    two2one[i].push_back(tp);
                    break;
                }
            }
        }
    }

    vector<int> f(maxx + 5, -1);
    auto dfs = [&](auto self, int x) -> int {
        if (f[x] != -1)
            return f[x];
        else {
            if (one2two.count(x)) {
                for (auto to : one2two[x]) {
                    f[x] = max(f[x], self(self, to));
                }
            } else
                f[x] = x;
            return f[x];
        }
    };

    for (int i = 0; i <= maxx + 4; i++) {
        dfs(dfs, i);
    }
    LL minn = 0;
    for (auto [x, y] : cnt1) {
        LL res;

        if (cnt1[x] == 1)
            res = x;
        else
            res = f[x];

        minn = max<int>(minn, res);
    }
    for (int i = 0; i <= maxx + 4; i++) {
        f[i] = max<int>(f[i], minn);
    }
    LL ans;
    deb(f);
    deb(maxx);
    if (m <= maxx + 4) {
        ans = accumulate(f.begin(), f.begin() + m + 1, 0LL);
    } else {
        ans = accumulate(f.begin(), f.end(), 0LL);
        ans += (m + maxx + 5) * (m - maxx - 4) / 2;
    }

    cout << ans << '\n';
}