T1
你是喵喵喵小学的一位老师，现在你带的班里有 \(n\) 个男生和 \(m\) 个女生需要列队，你可以按照任意顺序将 \(n+m\) 个学生进行列队。
你已知每个学生有一个整数快乐值：第 \(i\) 个男生的快乐值为 \(a_i\)，第 \(i\) 个女生的快乐值为 \(b_i\)。在队伍完毕后，如果某个学生和在 TA 前面的学生性别相同，则 TA 的心情值等于快乐值，否则心情值为 \(0\)；特殊地，排在最前面的学生心情值总是为 \(0\)。
当然，有些学生更喜欢交一些异性的朋友，所以学生的快乐值甚至可以为负数。那问题给到你——你应该怎么排，才能让所有学生的心情值总和最大？你只要输出这个最大的总和。
\(n,m\le 10^5\)
萌萌题。先把 \(a,b\) 分别倒序排序，考虑说我们要分成 \(k\) 段，则每个性别会少 \(k\) 个数的贡献，显然取最小的 \(k\) 个是对的。然后做一个前缀和，枚举 \(k=1\sim \min(n,m)\) 去最大答案即可。
T2
我们称一个序列 \(b_1,b_2,\ldots,b_m\) 是不友好的，如果它满足如下条件：
- 如果对于 \(1\le i<j\le m\) 且 \(j-i\le 2\)，有 \(b_i\neq b_j\)。
换句话说，一个序列是不友好的，如果任意距离至多为 \(2\) 的两个元素是不同的。
给定一个序列 \(a_1,a_2,\ldots,a_n\)，找到它最长不友好子序列的长度。
如果一个序列 \(d\) 可以通过删除一些（可能不删，也可能删除全部）元素得到序列 \(c\)，则称序列 \(c\) 是序列 \(d\) 的子序列。例如 \((1,3,5)\) 是 \((1,2,3,4,5)\) 的一个子序列，而 \((3,1)\) 不是。
\(n \le 2\times 10^5\)
一个 \(O(nV^2)\) 的 DP 是设 \(f_{i,j}\) 表示考虑前 \(i\) 个，以 \(i\) 为结尾且上一个数是 \(j\) 的最大长度，转移为 \(f_{i,j}=\max f_{lst_j,k} +1\;(k\ne a_i)\)
然后发现只有最近的五种颜色会产生贡献，于是做完了。
const int MAXN = 2e5 + 5, K = 6;
int n, a[MAXN], lst[MAXN], f[MAXN][K + 1];
set<int> st;
vector<int> col[MAXN];void work() {cin >> n;vector<int> v;for (int i = 1; i <= n; ++i) {cin >> a[i];v.push_back(a[i]);if (a[i] == a[i - 1]) lst[i] = lst[i - 1];}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());for (int i = 1; i <= n; ++i) {a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;}int ans = 1;for (int i = 1; i <= n; ++i) {if (lst[a[i]]) st.erase(lst[a[i]]);int j = 0;// cout << "before:" << endl;// for (auto x:st) cout << x << ' ';// cout << endl;for (auto it = st.rbegin(); it != st.rend() && j <= K; it++) {int x = *it;for (int k = 0; k < col[x].size(); ++k) {if (a[col[x][k]] == a[i]) continue; f[i][j] = max(f[i][j], f[x][k] + 1);}col[i].push_back(x);f[i][j] = max(f[i][j], 2);ans = max(ans, f[i][j]);// cout << i << ' ' << j << ' ' << x << ' ' << f[i][j] << endl;j++;}st.insert(lst[a[i]] = i);}cout << ans << endl;fill(lst + 1, lst + 1 + n, 0ll);for (int i = 1; i <= n; ++i) {for (int j = 0; j <= K; ++j) f[i][j] = 0;col[i].clear();}st.clear();
}
T3
你是一个国王，手下有 \(n\) 位骑士，第 \(i\) 位骑士的武力值为 \(a_i\)。为了更好地统治，你决定将骑士划分为黑白两个部队，每个部队都可以为空，但每个骑士都必须恰好被划分进一个部队。
如果属于相同部队的两个骑士武力值之和不低于 \(d\)，那么他们具备了叛变所需的力量，这很可能导致叛变。形式地，如果存在 \(x<y\)，使得 \(x,y\) 骑士属于相同部队，且 \(a_x+a_y\ge d\)，那么称 \((x,y)\) 为一组 可能的叛变组。
你需要找到最优的划分部队方案，最小化 可能的叛变组 的数量。你还希望知道有多少种划分部队方案可以最小化 可能的叛变组 数量，方案数对 \(998244353\) 取模。
\(n\le 5000\)
考虑将所有点按 \(<\frac d2\) 和 \(\ge \frac d2\) 分成两类，大点和大点之间一定有贡献，小点和小点之间一定没有贡献。
如果我们把他们按照 \(d,0,d-1,1,\cdots\) 这样的顺序排序的话，每个点就会只于前面的大点产生贡献，于是就满足无后效性可以 DP，设 \(f_{i,j}\) 表示考虑前 \(i\) 个数，将 \(j\) 个大点染成了黑色，其余 \(cnt-j\) 个点是白色，然后转移即可。
方案数和最小值可以在一起 DP 出来。
这个题之前在 MX 见过类似的，也涉及按照 \(\frac d2\) 分类。场上居然没想到，有点菜。
const int MAXN = 5e3 + 5, mod = 998244353;
int n, a[MAXN];
long double d;
struct _node {int a, b;_node operator + (const int x) const {return {a + x, b};}
};_node merge(_node a, _node b) {if (a.a < b.a) return a;else if (b.a < a.a) return b;else return {a.a, (a.b + b.b) % mod};
}void work() {cin >> n >> d;for (int i = 1; i <= n; ++i)cin >> a[i];sort(a + 1, a + 1 + n, [](auto x, auto y) {if (x >= d && y >= d) return x > y;if (x >= d) return true;if (y >= d) return false;if (x < d / 2 && y < d / 2) return x < y;if (x < d / 2) return x < (d - y);if (y < d / 2) return (d - x) <= y;return x > y;});vector<vector<_node>> f(n + 1, vector<_node>(n + 1, {INT_MAX, 0}));int cnt = 0;f[0][0] = {0, 1};for (int i = 1; i <= n; ++i) {cnt += (a[i] >= d / 2);if (a[i] < d / 2) {for (int j = 0; j <= cnt; ++j) {auto res1 = f[i - 1][j] + j, res2 = f[i - 1][j] + (cnt - j);f[i][j] = merge(res1, res2);}} else {f[i][0] = f[i - 1][0] + (cnt - 1);f[i][cnt] = f[i - 1][cnt - 1] + (cnt - 1);for (int j = 1; j < cnt; ++j) {auto res1 = f[i - 1][j - 1] + (j - 1), res2 = f[i - 1][j] + (cnt - j - 1); f[i][j] = merge(res1, res2);}}}_node ans = {INT_MAX, 0};for (int i = 0; i <= cnt; ++i)ans = merge(ans, f[n][i]);cout << ans.a << ' ' << ans.b << endl;
}
T4
你正在使用一个特殊的文本编辑器对字符串 \(S\) 进行编辑。
\(S\) 是一个长度为 \(n\) 的只包含小写字母的字符串，你可以对 \(S\) 使用以下两种指令，使用次数均没有限制：
Edit \(pos, c\)，要求 \(pos\) 为整数且 \(1 \le pos \le n\)，且 \(c\) 为一个小写字母，效果为
\(S_{pos} \leftarrow c\)，即将 \(S\) 的第 \(pos\) 个字符改为 \(c\)。ChangeAll \(a, c\)，要求 \(a, c\) 为两个不同的小写字母，效果为构造 \(S'\) 如下：
\[S'_i = \begin{cases} S_i & (S_i \ne a) \\ c & (S_i = a) \end{cases} \]然后用 \(S'\) 替换 \(S\)。
即将 \(S\) 中的所有 \(a\) 改为 \(c\)。现在已知进行一次 Edit 操作需要 \(1\) 的代价，进行一次 ChangeAll 操作则需要 \(k\) 的代价。你需要用最小的总代价，将 \(S\) 编辑为另一个长度为 \(n\) 的小写字母字符串 \(T\)。
原题：洛谷 P6700。
待补。