A - T-shirt
https://codeforces.com/problemset/problem/183/D
如果知道一个衣服序列，怎么算出期望呢？
B - Two Melodies
https://codeforces.com/problemset/problem/813/D
如果设 \(f_{i,j}\) 表示第一个以 \(i\) 结尾，第二个以 \(j\) 结尾的方案数，就会有一个弊端——假设现在有 \(i>j\)，又假设有 \(j<j'<i\)，那么就不可以直接把 \(f_{i,j}\) 转移到 \(f_{i,j'}\)，因为 \(j'\) 可能已经被第一个选过了。但如果从 \(i\) 转移就没有这样的问题（不管 \(i'\) 是比 \(j\) 大还是比 \(j\) 小）。
那就可以固定从较大的一维转移，也可以枚举所有情况。但是这样就会有一个问题，这是一个 \(n^3\) 的过程，而且对于不单调的内层 \(j\)，维护它的数值只能用带 \(\log\) 的数据结构优化，似乎不太过得了；但 \(i\) 却可以前缀优化。
其实，两个组是无序的，这意味着可以强制 \(i>j\) 再从 \(i\) 转移；这个时候转移就和 \(j\) 没有太大的关系了，可以把 \(j\) 放到外层，对 \(i\) 前缀优化。可能需要注意边界的处理。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, res = 0;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<int> > f(n + 1, std::vector<int> (n + 1));
for (int j = 0; j < n; ++j) {
std::vector<int> mx(100002), mmx(7);
for (int i = 1; i < j; ++i) {
mx[a[i]] = std::max(mx[a[i]], f[j][i]);
mmx[a[i] % 7] = std::max(mmx[a[i] % 7], f[j][i]);
}
for (int i = j + 1; i <= n; ++i) {
f[i][j] = std::max({ !!i + !!j, mx[a[i] - 1] + 1, mx[a[i] + 1] + 1, mmx[a[i] % 7] + 1, f[j][0] + 1 });
mx[a[i]] = std::max(mx[a[i]], f[i][j]);
mmx[a[i] % 7] = std::max(mmx[a[i] % 7], f[i][j]);
// printf("f[%d][%d] = %d\n", i, j, f[i][j]);
res = std::max(res, f[i][j]);
}
}
std::cout << res << '\n';
return 0;
}C - 巡逻
https://www.luogu.com.cn/problem/P3629
你可能需要注意：目的是遍历所有边而非所有点。
\(K=1\) 的时候，环上除了关键边的所有边经过次数会减 \(1\)。所以选树的直径就可以最优。
\(K=2\) 的时候，答案是 \(2\times (m + 2)\) 减去两个边构成的环的大小 \(L\)。那么就只需要最大化 \(L\) 了。
其实是在树上任选两个没有祖孙关系的点 \(x,y\)，找到它们不相交的最长儿子链和次长儿子链，要这四条链加起来最长。\(x\) 和 \(y\) 其实无关，分别找就可以了。
当 \(x\) 与 \(y\) 重合时可能会退化（？）成两个环，取树上任意 \(x\) 子树和补集里面可以构成的最大环就可以了。