#A - T-shirt
https://codeforces.com/problemset/problem/183/D
如果知道一个衣服序列，怎么算出期望呢？
#B - Two Melodies
https://codeforces.com/problemset/problem/813/D
如果设 fi,j 表示第一个以 i 结尾，第二个以 j 结尾的方案数，就会有一个弊端——假设现在有 i>j，又假设有 j<j′<i，那么就不可以直接把 fi,j 转移到 fi,j′，因为 j′ 可能已经被第一个选过了。但如果从 i 转移就没有这样的问题（不管 i′ 是比 j 大还是比 j 小）。
那就可以固定从较大的一维转移，也可以枚举所有情况。但是这样就会有一个问题，这是一个 n3 的过程，而且对于不单调的内层 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;
}查看代码
#CF633F The Chocolate Spree
https://codeforces.com/problemset/problem/633/F
树形 DP 求直径的时候，有一种方法是找到每个点下面的最大两条不交链。
这里也可以有类似的求法。假设答案出现在子树 u 中（下面的 vi 都是 u 的直接儿子），可以讨论 u 参与构成两条路径的情况：
- 不参与构成任何一条路径，答案是 v1,v2 子树中的最长路径之和。
参与构成其中一条：
- 这一条与子树 v 完全相离，答案是 v 中最长路径，和 u 下面不经过 v 的最大两条不交链。
- 这一条有一支来自 v 子树，但和 v 中最长路径没有重合的点。答案是 u 的点权、u 下面不经过 v 的最大链、v 中一条路径（不经过 v）和 v 下面一条链之和的最大值；
- 这一条两支都来自 v 子树：有重合，不可能发生。
参与构成其中两条，答案是 u 下面最长的四条链：路径重复经过 u，不可能发生。
可以记录 u 下方最大的四条不交链、u 中选取一条不经过 u 的路径和 u 下方一条链之和的最大值、u 中最长路径求解。
#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;
std::cin >> n;
std::vector<int> a(n + 1);
std::vector<std::vector<int> > g(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
auto res(0ll);
std::vector<long long> s(n + 1), w(n + 1);
std::vector<std::vector<std::pair<long long, int> > > f(n + 1, std::vector<std::pair<long long, int> > (4));
std::function<void(int, int)> DFS = [&](int x, int fa) {
f[x][0] = { 0, x };
w[x] = s[x] = a[x];
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
{
if (f[i][0].first + a[i] > f[x][3].first)
f[x][3].first = f[i][0].first + a[i], f[x][3].second = i;
std::sort(f[x].begin(), f[x].end(), std::greater<std::pair<long long, int> > ());
}
w[x] = std::max(w[x], w[i] + a[x]);
}
auto mx(0ll);
for (auto i : g[x])
if (i != fa) {
s[x] = std::max({ s[x], s[i], f[x][0].first + f[x][1].first + a[x] });
w[x] = std::max(w[x], (f[x][0].second != i ? f[x][0] : f[x][1]).first + s[i] + a[x]);
res = std::max({ res,
mx + s[i], // 情况 1
(f[x][0].second == i ? f[x][1].first + f[x][2].first : (f[x][1].second == i ? f[x][0].first + f[x][2].first : f[x][0].first + f[x][1].first)) + s[i] + a[x], // 情况 2.1
(f[x][0].second == i ? f[x][1].first : f[x][0].first) + w[i] + a[x], // 情况 2.2
});
mx = std::max(mx, s[i]);
}
// printf("%d: res = %lld\n f: \n", a[x], res);
// for (int i = 0; i < 4; ++i)
// printf(" [%d] %lld\n", f[x][i].second, f[x][i].first);
// printf(" s: %lld\n w: %lld\n", s[x], w[x]);
};
DFS(1, -1);
std::cout << res << '\n';
return 0;
}查看代码
#C - 巡逻
https://www.luogu.com.cn/problem/P3629
你可能需要注意：目的是遍历所有边而非所有点。
K=1 的时候，环上除了关键边的所有边经过次数会减 1。所以选树的直径就可以最优。
K=2 的时候，答案是 2×(m+2) 减去两个边构成的环的 并集减交集 大小 L。环实际上是不存在的，L 其实是两条路径 并集减交集 再加上两条新边的值。
两条路径有交的时候，可以等效成无交的情况：
就化归成上一个问题了。注意此时情况 3 可能发生；同时情况 2.2 可以选取经过 v 的路径。
#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, k;
std::cin >> n >> k;
std::vector<std::vector<int> > g(n + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
int res = 0;
if (k == 1) {
std::vector<std::vector<std::pair<int, int> > > f(n + 1, std::vector<std::pair<int, int> > (2));
std::function<void(int, int)> DFS = [&](int x, int fa) {
f[x][0] = { 0, x };
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
{
if (f[i][0].first + 1 > f[x][1].first)
f[x][1].first = f[i][0].first + 1, f[x][1].second = i;
std::sort(f[x].begin(), f[x].end(), std::greater<std::pair<int, int> > ());
}
}
res = std::max(res, f[x][0].first + f[x][1].first);
};
DFS(1, -1);
std::cout << 2 * n - res - 1 << '\n';
}
else {
std::vector<int> s(n + 1), w(n + 1);
std::vector<std::vector<std::pair<int, int> > > f(n + 1, std::vector<std::pair<int, int> > (4));
std::function<void(int, int)> DFS = [&](int x, int fa) {
f[x][0] = { 0, x };
for (auto i : g[x])
if (i != fa) {
DFS(i, x);
{
if (f[i][0].first + 1 > f[x][3].first)
f[x][3].first = f[i][0].first + 1, f[x][3].second = i;
std::sort(f[x].begin(), f[x].end(), std::greater<std::pair<int, int> > ());
}
w[x] = std::max(w[x], w[i] + 1);
}
{
int t = 0;
for (auto [v, id] : f[x])
t += v;
res = std::max(res, t); // 情况 3
w[x] = std::max(w[x], t - f[x][3].first); // 路径可经过 u
}
int mx = 0;
for (auto i : g[x])
if (i != fa) {
s[x] = std::max({ s[x], s[i], f[x][0].first + f[x][1].first });
w[x] = std::max(w[x], (f[x][0].second != i ? f[x][0] : f[x][1]).first + std::max(s[i], f[i][0].first + 1));
res = std::max({ res,
mx + s[i], // 情况 1
(f[x][0].second == i ? f[x][1].first + f[x][2].first : (f[x][1].second == i ? f[x][0].first + f[x][2].first : f[x][0].first + f[x][1].first)) + s[i], // 情况 2.1
(f[x][0].second == i ? f[x][1].first : f[x][0].first) + w[i] + 1, // 情况 2.2
});
mx = std::max(mx, s[i]);
}
};
DFS(1, -1);
std::cout << 2 * (n + 1) - res - 2 << '\n';
}
return 0;
}查看代码
#D - 瞬间传送 / Teleport
https://www.luogu.com.cn/problem/P11915
需要观察到一个很厉害的贪心策略：如果钦定所有点的距离不大于 r，且存在 d(i,j)>r。假设 一种满足条件的新边是 (u,v)（由于两者无序，不妨钦定 d(i,u)<d(i,v)），可以进行讨论：
d(j,v)<d(j,u)：
此时最优路径为 i→u→v→j，判断一下这种方案是否不大于 r 就可以了。d(j,v)≥d(j,u)：
此时不管是走 i→u→v→j 还是 i→v→u→j 都不如走已经存在的 i→u→j 这条路径，也就是说如果要走新边，代价是一定比原距离大，更是比 r 大的；也就是说，(u,v) 不能解决 (i,j) 之间的问题，假设就不成立了。
综上，只需要判断 i→u→v→j≤r 是否成立，就可以判断 (u,v) 是否合法。从大到小枚举 r，同时维护当前依然合法的 (u,v)（显然是有单调性的），对于不合法的 (i,j)，枚举每个 i，维护 max{d(v,j)}，精细实现（主要是利用各种均摊）一下就能 O(n3)。
这里具体提一下需要摊的几个点：
- 枚举到 r 的时候用所有 d(i,j)=r+1 把 v 在 i 处的最大 d(v,j) 更新，方便后面 O(n) 地 check。摊出来是 O(n3) 的。
- 枚举仍然处在合法队列里的 (u,v)，如果 check 合法，就说明对于当前 r 至少存在一个合法解，就可以
break了；否则，把 (u,v) 弹出，继续 check 下一条边。这样每条边只会被弹出一次，而未弹出边的 check 次数最多是 O(n)；加上 O(n) 的 check，摊出来是 O(n3) 的。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
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 T;
for (std::cin >> T; T--; ) {
int n;
std::cin >> n;
std::vector<std::vector<int> > g(n + 1, std::vector<int> (n + 1, inf));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
char t;
std::cin >> t;
if (t == '1' || i == j)
g[i][j] = t - '0';
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
if (i != k)
for (int j = 1; j <= n; ++j)
if (j != i && j != k)
g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
std::queue<std::pair<int, int> > q;
std::vector<std::vector<std::pair<int, int> > > p(n + 1);
std::vector<std::vector<int> > mx(n + 1, std::vector<int> (n + 1));
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
q.emplace(i, j);
p[g[i][j] - 1].emplace_back(i, j);
}
auto check = [&](int u, int v, int r) {
for (int i = 1; i <= n; ++i) {
if (g[u][i] > g[v][i])
std::swap(u, v);
if (g[u][i] + mx[v][i] > r)
return false;
}
return true;
};
for (int r = n; r >= -1; --r) {
for (auto [i, j] : p[r])
for (int v = 1; v <= n; ++v) {
mx[v][i] = std::max(mx[v][i], g[v][j]);
mx[v][j] = std::max(mx[v][j], g[v][i]);
}
for (; !q.empty(); ) {
auto [u, v] = q.front();
if (!check(u, v, r))
q.pop();
else
break;
}
if (q.empty()) {
std::cout << r + 1 << '\n';
break;
}
}
}
return 0;
}查看代码
#E. Two Tanks
https://codeforces.com/problemset/problem/1809/E
果然还是不会简单 DP 
可以观察到如果总水量相同，且某个时刻两种初始状态当前是相同状态，那么以后它们也会是相同状态。但光凭这个好像还是不太能做出来的样子 
这里大概算一个定式，对于类似这种两个元素总和不变的问题，可以把两个元素的容量画到数轴上，原点表示分界，当前水为一条定长线段，倒水就相当于左右平移这条线段：
需要意识到，
