A. Turtle and Good Strings
题意：确定是否存在一种方案使得 \(s = t_1 + t_2 + \cdots + t_m\)，满足 \(m > 1\) 且任意 \(i < j\)，\(t_i\) 的第一个字母不等于 \(t_j\) 的最后一个字母。
\(s_1\) 和 \(s_n\) 一定不属于一个子串，因此 \(s_1 \ne s_n\) 是条件非法的必要条件。
那么反之是否能构造一组解呢？这是显然的，取 \(t_1 = s[1], t_2 = s[2, n]\) 即可。
void solve() {
int n; string s; cin >> n >> s;
cout << (s.front() != s.back() ? "Yes\n" : "No\n");
}
B. Turtle and Piggy Are Playing a Game 2
题意：Alice 和 Bob 进行博弈，Alice 先手。
每次 Alice 可以选一个 \(i\) 并删掉 \(i, i + 1\) 中较小的一个，Bob 可以选一个 \(i\) 并删掉 \(i, i + 1\) 中较大的一个。
Alice 想最大化 \(a_1\)，Bob 想最小化 \(a_1\)，求两人都在最优策略下的 \(a_1\)。
策略很明了了，Alice 每次删掉全局最小，Bob 每次删掉全局最大，删到最后只剩整个序列的中位数。
void solve() {
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
sort(a + 1, a + n + 1);
cout << a[n / 2 + 1] << '\n';
}
C. Turtle and Good Pairs
题意：\((i, j)\) 是好的当且仅当 \(i < j\) 且存在 \(k \in [i, j)\) ，满足 \(s_k \ne s_{k + 1}\) 且 \(s_i \ne s_k \lor s_{j} \ne s_{k + 1}\)。将 \(s\) 重新排序，最大化好的数对个数。
把字符串分为若干极长连续颜色段 \([l_i, r_i]\)（如 \(aaabbcc = [aaa][bb][cc]\)）。
容易发现 \((i, j)\) 是好的的充要条件为 \(i, j\) 所在颜色段不相邻。
令 \(a_i = r_i - l_i + 1\)，那么好的数对个数等于 \(\dfrac{n(n - 1)}{2} - \sum a_{i}a_{i + 1}\)。
目标转化为最小化 \(\sum a_i a_{i + 1}\)。
当字符集大小不为 \(1\) 时，可以证明 \(\sum a_i a_{i + 1} \ge n - 1\) 并且这个下界是可以达到的。
如果存在 \(a_k = 1\)：
\[\sum_{i = 1}^{m - 1}a_ia_{i + 1} \ge \sum_{i = 1}^{k - 1}a_i + \sum_{i = k}^{m - 1}a_{i + 1} \ge n - a_k \]如果 \(\forall a_k \ge 2\)，\(a_ia_{i + 1} \ge1 a_i + a_{i + 1}\)：
\[\sum_{i = 1}^{m - 1}a_ia_{i + 1} \ge \sum_{i = 1}^{m - 1}a_i + \sum_{i = 2}^{m}a_{i} > n \]
我们让前面所有 \(a_i = 1\)，最后一个连续段放多出来的相同字母（如 \(aaabbcc = ababacc\)），显然有 \(\sum a_ia_{i + 1} = n - 1\)。
时间复杂度 \(O(26n)\)
void solve() {
cin >> n >> s;
for(auto x : s) ++ cnt[x - 'a'];
int Len = 0;
string t;
while(Len < n) {
for(int i = 0; i < 26; ++ i) {
if(cnt[i]) {
-- cnt[i], ++ Len;
t += char(i + 'a');
}
}
}
cout << t << '\n';
}
D1. Turtle and a MEX Problem (Easy Version)
题意：给定 \(n\) 个序列 \([a_i]\)，\(f(x)\) 定义为 \(x\) 经过若干次操作（可能不操作）达到的最大值。
一次操作定义为：选定一个序列 \([a_i]\)，\(x \gets \text{mex}(x \cup [a_i])\)。在简单版中，一个序列可以被重复选择。
给定 \(m \le 10^9\)，求 \(\sum_{x = 0}^{m} f(x)\)。
定义 \(u_i = \text{mex}[a_i],\ v_i = \text{mex}\big([a_i] \cup u_i\big)\)。
我们发现不管是什么 \(x\)，不管对 \([a_i]\) 操作几次，能够达到且一定能达到的只有 \(v_i\) 和 \(u_i\)。
因此 \(f(x) = \max\big(x, \max v_i\big)\)。
ll sum(ll l, ll r) {
if(l > r) return 0;
return (l + r) * (r - l + 1) / 2;
}
void solve() {
int n, m, mx = 0; cin >> n >> m;
ll ans = 0;
while(n --) {
int k; cin >> k;
set<int> se;
for(int i = 0; i <= k + 1; ++ i) {
se.ep(i);
}
for(int i = 0; i < k; ++ i) {
int x; cin >> x;
se.erase(x);
}
mx = max(mx, *++ se.begin());
}
cout << mx * ll(min(m, mx) + 1) + sum(mx + 1, m) << '\n';
}
D2. Turtle and a MEX Problem (Hard Version)
题意与 D1 相同，多了每个序列只能选一次的限制。
如果 \(x = u_i\)，那么 \(x\) 能够走到 \(v_i\)。
不难想到 \(u_i\) 向 \(v_i\) 连边。
如果 \(x = u_i\)，那么 \(x \to v_i\) 后是可以继续走 \(v_i\) 的出边的，因为一个序列只会产生一条边， \(v_i\) 的出边对应的序列不是 \(i\)。
定义 \(f_i\) 表示 \(i\) 能到达的最大点坐标，可以逆拓扑序完成。
- 一个 \(x\) 的答案至少是 \(f_i\)。
- 一个 \(x\) 的答案至少是 \(\max u_i\)。
- 如果 \(i\) 只有一条出边，只有 \(x = i\) 能够到达 \(f_i\)。
- 如果存在 \(i\) 有大于一条出边，那么对于任意 \(x\)，我们可以先走另一条出边对应的序列来达到 \(i\)，然后再走通向 \(f_i\) 的出边。
ll sum(ll l, ll r) {
if(l > r) return 0;
return (l + r) * (r - l + 1) / 2;
}
void solve() {
int n, m; cin >> n >> m;
ll ans = 0;
vector<vector<int>> g(2 * n);
vector<int> d(2 * n), w(2 * n), val(2 * n);
int idx = 0, mx = 0;
map<int, int> mp;
while(n --) {
int k; cin >> k;
set<int> se;
for(int i = 0; i <= k + 3; ++ i) {
se.ep(i);
}
for(int i = 0; i < k; ++ i) {
int x; cin >> x;
se.erase(x);
}
int p1 = *se.begin(), p2 = *++ se.begin();
int x = 0, y = 0;
(mp.count(p1)) ? x = mp[p1] : val[x = mp[p1] = idx ++] = p1;
(mp.count(p2)) ? y = mp[p2] : val[y = mp[p2] = idx ++] = p2;
mx = max(mx, p1);
g[y].eb(x), ++ d[x];
}
queue<int> q;
vector<int> vec;
for(int i = 0; i < idx; ++ i) {
if(!d[i]) {
q.ep(i);
}
if(d[i] > 1) vec.eb(i);
}
while(!q.empty()) {
int x = q.front();
q.pop();
w[x] = max(w[x], val[x]);
for(int y : g[x]) {
w[y] = max(w[y], w[x]);
if(!-- d[y]) q.ep(y);
}
}
for(int i : vec) mx = max(mx, w[i]);
vector<int> id(idx);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
return val[i] < val[j];
});
int lst = 0;
for(int i = 0; i < idx; ++ i) {
int x = id[i];
if(val[x] > m) break;
int l = lst, r = val[x] - 1;
ans += max(min(mx, r) - l + 1, 0) * (ll)mx + sum(max(l, mx + 1), r);
ans += max(mx, w[x]);
lst = val[x] + 1;
}
int l = lst, r = m;
ans += max(min(mx, r) - l + 1, 0) * (ll)mx + sum(max(l, mx + 1), r);
cout << ans << '\n';
}