现在是 10 题。虽然看着很掉价，但是写够了 10 就改成 20 题。以此类推，免得我摆烂（）
自用向，不写太详细，把破题点写出来就差不多了。哦哦这里的破题是动词不是名词。
1. 字符合并
https://www.luogu.com.cn/problem/P3736
给定长度为 \(n\) 的 \(01\) 串和 \(2^k\) 条规则，第 \(i\) 条规则形如：
- 对于序列中的 \(k\) 位二进制数 \(i\)，可以将它合并为 \(c(c\in\{0,1\})\)，并产生 \(v\) 的价值。
进行任意次合并，求出能取得的最大总价值。\(n\le 300,k\le 8\)。
状压，区间 DP。
注意到 \(k\) 只有 \(8\)，独特的输入方式也引导我们注意到状态数为 \(10^2\) 级别。合并的背景又让我们本能想到区间 DP，所以刚好盲猜这题是个 \(O(2^k\times n^2)\) 的区间状压 DP。
然后我觉得最神的一个地方是什么呢？最后的答案一定是一个长度小于 \(k\) 的串，每位展开还原，可以知道，每个合并操作选取的区间可能包含但不相交。
看起来很蠢很显然，但这是我们 \(n^2\) 区间 DP 的基础啊（（（
然后我们区间 DP 套路，枚举对于 \([l,r]\) 最左边一位，然后就可以开始大力转移了。
但是这里我们会发现，这一位原本的样子有点多，可以是任何一个长度为 \(1 + d\times (k-1)\) 的数，所以只能再来一层 \(\dfrac nk\) 的枚举，极限情况是个有点难绷的 3e9，作为正解只能说这个数据范围的提示性有点令人难评了。
实现着实现着把自己整懵了：00000 和 0 压出来都是 0，但二者代表的含义显然不同，又无法简单区别。但其实长度为 \(1+d\times (k-1)\) 的区间和长度为 \(d\) 的最终结果是一一对应的，所以在我们设计的包含了区间作右端点的状态中，压出来的就是我们想要的那个。
这里的实现比所有我找到的题解都更像人打出来的。导致我想对比疗法都找不到合适的代码 
换言之，这最像是一份通常的区间 DP 代码，不存在其他题解中乱七八糟的填表啊相互影响啊之类的恶心 feature。
sto rybp orz
#include <bits/stdc++.h>
const int maxn = 305;
const int maxm = (1 << 8) + 5;
char a[maxn];
int c[maxm], w[maxm];
long long f[maxn][maxn][maxm];
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
int siz = (1 << k), si = (1 << (k - 1));
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = 0; i < siz; ++i)
std::cin >> c[i] >> w[i];
memset(f, -0x3f, sizeof(f));
for (int l = 1; l < k; ++l)
for (int i = 1; i <= n - l + 1; ++i) {
int j = i + l - 1, now = 0;
for (int p = i; p <= j; ++p)
now = now * 2 + a[p] - '0';
f[i][j][now] = 0;
}
for (int i = 1; i <= n - k + 1; ++i) {
int now = 0;
for (int j = i; j <= i + k - 1; ++j)
now = now * 2 + a[j] - '0';
f[i][i + k - 1][c[now]] = w[now];
}
for (int l = k + 1; l <= n; ++l)
for (int i = 1; i <= n - l + 1; ++i) {
int j = i + l - 1;
for (int p = i; p < j; p += k - 1) {
for (int q = 0; q < si; ++q)
if (!(q >> ((l - 1) % (k - 1) + 1)))
f[i][j][q] = std::max(f[i][j][q], f[i][p][q >> ((l - 1) % (k - 1))] + f[p + 1][j][q & ((1 << ((l - 1) % (k - 1))) - 1)]);
if (l % (k - 1) == 1 || k == 2)
for (int q = 0; q < siz; ++q)
f[i][j][c[q]] = std::max(f[i][j][c[q]], f[i][p][q >> (k - 1)] + f[p + 1][j][q & ((1 << (k - 1)) - 1)] + w[q]);
}
}
std::cout << *std::max_element(f[1][n], f[1][n] + si) << '\n';
return 0;
}其实一开始挺担心会不会因为写博客影响做题时间之类的。
直到发现我可以看知乎看一个上午然后代码动都不动一下
2. Mod Mod Mod
https://codeforces.com/contest/889/problem/E
给定 \(a_{1\sim n}\)，对于所有非负整数 \(x\) 定义 \(f(x,n)=x\bmod a_n\)，\(f(x,i)=x\bmod a_i+f(x\bmod a_i,i+1)\)。
求 \(f(x,1)\) 最大值。\(n\le 2\times 10^5\)。
技巧 / 特殊性质类 DP。
小神题。注意到题意可以转化为，找到一个 \(x\)，最大化：
\[ x\bmod a_1 + x\bmod a_1\bmod a_2 + \cdots + x\bmod a_1\bmod a_2\bmod\cdots\bmod a_n. \]
简称 \(x\bmod a_1\bmod a_2\bmod \cdots\bmod a_i\) 的值为 \(f_i\)。
这个时候我们不难注意到，\(f_i\) 肯定是单调不升的。形象化地，整个 \(f\) 序列肯定是由若干个单调下降的段组成的。并且，必定存在至少一个 \(i\)，使得 \(f_i = a_i-1\)，否则可以将所有 \(f_i\gets f_i+1\)，同时 \(\sum f\gets (\sum f) + n\)。
这启示我们关注 \(f_i\) 的值域。假设已经确定了 \(f\) 序列的一个前缀 \(f_1\sim i\)，对于任意 \(0\le k\le f_{\min}\)（注意由于单调不降，\(f_{\min} = f_i\)），我们可以将所有 \(f_j\gets f_j-k\)，得到一个新的合法的 \(f'_{1\sim i}\)。
形象化地，将 \(f_{1\sim i}\) 想象为一个逐渐降低的柱状图，任意切去了一个高度的底部，并且这个高度不高于最矮的元素（即第 \(i\) 个元素）。
这时候有一个很美妙的性质，就是我们对于切之前和切之后的柱状图，其 最矮元素以上的部分 长得完全相同。然后就是神中神之 DP 状态设计。很难想象是在什么样的精神状态下凑出来这种神奇状态的，可能是某种我不了解的 trick？
令 \(dp_{i, j}\) 表示对于前缀 \(f_{1, i}\)，当切去的高度为 \(0\sim j\) 时，最矮元素以上的部分 的和都为 \(dp_{i, j}\)。那么易得 \(\sum f_{1\sim i}=j\times i + dp_{i, j}\)。
考虑转移。假设已知所有 \(dp_{i - 1, j}\)，需转移到 \(i\)，我们有三种转移路径：
\(j < a_i\)：
对 \(a_i\) 取模取不动，不会产生任何影响。\(dp_{i, j}\gets dp_{i - 1, j}\)。\(j\ge a_i\)：
让 \(i\) 承担 \(f_i=a_i-1\) 的责任。我们从 \(0\sim j\) 中找到一个满足 \(j'\bmod a_i=a_i-1\) 的 \(j'\)，\(j'\) 肯定是越大越好，故 \(j'=(\left\lfloor \dfrac {j}{a_i}\right\rfloor-1)\times a_i+(a_i-1)\)。
此时便有 \(dp_{i, a_i-1}\gets dp_{i - 1, j'} + [j' - (a_i-1)]\times (i-1)\)。盲猜 \(0\sim i - 1\) 或 \(i+1\sim n\) 中会出现承担 \(f_{i'}=a_{i'-1}\) 的 \(i'\)，故按照 \(j\) 取最大来转移。
此时有 \(dp_{i, j\bmod a_i}=dp_{i-1,j}+(j-j\bmod a_i)\times (i-1)\)。
答案即为 \(\max\{j\times n+dp_{n, j}\}\)。由于不存在 \(f_i=a_i-1\) 的 \(f\) 肯定比存在的要劣，所以我们肯定选到的是正确的答案。
注意到每个 \(i\) 只会新增 \(a_i-1\) 一个状态，故状态总数为 \(O(n)\)。把 \(dp\) 开成 map 就可以 \(O(n\log n)\) 地解决问题。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> a(n + 1);
std::map<long long, long long> t;
std::cin >> a[1];
t[a[1] - 1] = 0;
for (int i = 2; i <= n; ++i) {
std::cin >> a[i];
for (;;) {
auto p = t.lower_bound(a[i]);
if (p == t.end())
break;
long long j = p->first, f = p->second;
t[j % a[i]] = std::max(t[j % a[i]], f + (j - j % a[i]) * (i - 1));
if (j >= a[i]) {
j = (j / a[i] - 1) * a[i] + a[i] - 1;
t[a[i] - 1] = std::max(t[a[i] - 1], f + (j - (a[i] - 1)) * (i - 1));
}
t.erase(p);
}
}
long long res = 0;
for (auto i : t)
res = std::max(res, i.first * n + i.second);
std::cout << res << '\n';
return 0;
}3. StalinSort Algorithm
给定排列 \(A_{1\sim n}\)。从 \(i=2\) 开始往右扫，每一步执行以下操作：
- 若 \(A_i> A_{i-1}\)，什么也不做。
- 否则，你可以删除 \(A_{i-1}\) 或 \(A_i\)，但要求删除后，该前缀必须单调递增。
问最少可以删除多少个数。\(n\le 10^5\)。
你会发现删最少 = 留最多。
考虑 \(i\) 能够转移到的 \(j(j>i)\) 需满足的条件。若令 \(nex_p\) 表示 \(p\) 之后第一个值比 \(a_p\) 大的元素，则 \(j\in [nex_i, nex_{nex_i})\) 且 \(a_j>a_i\)。
赛时误认为右端点为 \(i\) 之后第二个值比 \(a_i\) 大的元素，导致完全寄掉。
时间复杂度 \(O(n^2)\)，考虑优化。注意到如果只有 \(j\in [nex_i, nex_{nex_i})\) 这个条件很容易用线段树维护，考虑消去 \(a_j>a_i\) 的影响。故考虑按 \(a\) 从小到大 的顺序选取 \(i\)，因为当前最小的 \(i\) 一定已经被刷完表了。
时间复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
struct _ { int u, d; } t1[maxn << 2];
int n, t[maxn << 2];
#define lt (p << 1)
#define rt (lt | 1)
void upd(int p, int l, int r, int x, int v) {
t[p] = std::min(t[p], v);
if (l == r)
return;
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v);
else
upd(rt, mid + 1, r, x, v);
return;
}
int ask(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return t[p];
int mid = (l + r) >> 1, res = n + 1;
if (ql <= mid)
res = ask(lt, l, mid, ql, qr);
if (qr > mid)
res = std::min(res, ask(rt, mid + 1, r, ql, qr));
return res;
}
void pushdown(int p) {
if (t1[p].d) {
t1[lt].u = std::max(t1[lt].u, t1[p].d);
t1[lt].d = std::max(t1[lt].d, t1[p].d);
t1[rt].u = std::max(t1[rt].u, t1[p].d);
t1[rt].d = std::max(t1[rt].d, t1[p].d);
t1[p].d = 0;
}
return;
}
void upd(int p, int l, int r, int ql, int qr, int v) {
t1[p].u = std::max(t1[p].u, v);
if (ql <= l && r <= qr) {
t1[p].d = std::max(t1[p].d, v);
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (ql <= mid)
upd(lt, l, mid, ql, qr, v);
if (qr > mid)
upd(rt, mid + 1, r, ql, qr, v);
return;
}
int ask(int p, int l, int r, int x) {
if (l == r)
return t1[p].u;
pushdown(p);
int mid = (l + r) >> 1;
if (x <= mid)
return ask(lt, l, mid, x);
return ask(rt, mid + 1, r, x);
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen("sort3.in", "r", stdin);
// freopen(".out", "w", stdout);
#endif
int res = 0;
std::cin >> n;
std::vector<int> a(n + 1), ne(n + 1), f(n + 1);
std::fill(t + 1, t + 4 * n + 1, n + 1);
std::fill(t1 + 1, t1 + 4 * n + 1, (_){ -inf, 0 });
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
for (int i = n; ~i; --i) {
ne[i] = ask(1, 0, n, a[i] + 1, n);
upd(1, 0, n, a[i], i);
}
std::vector<int> id(n + 1);
std::iota(id.begin(), id.end(), 0);
std::sort(id.begin(), id.end(), [&](int x, int y) { return a[x] < a[y]; });
f[0] = 0;
for (int i = 0; i <= n; ++i) {
if (i) {
f[id[i]] = ask(1, 0, n, id[i]);
res = std::max(res, f[id[i]]);
}
if (ne[id[i]] <= n)
upd(1, 0, n, ne[id[i]], ne[ne[id[i]]] - 1, f[id[i]] + 1);
}
std::cout << n - res << '\n';
return 0;
}4. Merge Triplets
https://atcoder.jp/contests/agc043/tasks/agc043_d
给定 \(A_{1\sim 3N}=\{1, 2, \dots, 3N\}\)，从 \(1\) 开始每 \(3\) 个数分为一组，每一组初始有一个指针指向第一个元素。执行若干次以下操作：
- 在所有指针指向的数中选择一个最小的，把它放到序列末（不会加入末端的组）；将原本指向它的指针后移一位，如果移出原本的组就删除这个指针。
问任意次操作后，可能得到多少种序列。\(n\le 2\times 10^3\)。
由于要对合法的最终序列进行计数，考虑最终序列的性质。
若序列中 \(a_{i+1}<a_i\)，则说明在某一组中，值为 \(a_i\) 的元素下一个就是 \(a_{i+1}\)。否则，因 \(a_{i+1}\) 可选且比 \(a_i\) 小，\(a_{i+1}\) 应排在 \(a_i\) 前面。
否则，\(a_{i+1}\) 既可以与 \(a_i\) 不在同一组，也可以是 \(a_i\) 的下一个元素。
一组最多三个元素，也就是说，不能出现 \(a_i>a_{i+1},a_{i+2},a_{i+3}\) 的情况。而 \(N=1\) 时序列长度只有 \(3\)，这就是为什么样例一的答案为 \(3!\)。
但这个限制并不能排除所有非法情况。\(N=2\) 时暴搜我们目前限制下的解，共有 276 个，比答案中的 261 个要多，说明包含了其他非法解。
暴搜输出并观察，易得这 15 个非法序列即为满足目前限制且存在 \(3\) 个 \(i\)，满足 \(a_i>a_{i+1}\) 且 \(a_i<a_{i+2}\) 的所有序列，由前面的推导，必须分为三个长度为 2 的组，而我们要求的是长度为 3 的组。显然无法用前者组合得到后者。
在我们第一个条件的限制下，必须被分到同一组的数的连续长度，只有 \(1,2,3\) 三种。而：
- 长度为 3 的对答案合法性无影响；
- 而长度为 1 的既可以和 2 组为一组，也可以和其他两个 1 组为一组；
- 长度为 2 的只能和 1 组成一组。
这时，我们发现所有限制都指向长度为 2 的段，其总个数不能比长度为 1 的段多。
于是乎，上述限制可总结为两点：
- 若令所有满足 \(a_l>\max\{a_{l\sim r}\}\) 的极大区间为一段（易证每段互不重合且覆盖全序列），那么其长度不能超过 3。
- 其中，长度为 2 的个数不能比长度为 1 的个数多。
令 \(f_{i, j}\) 表示若当前枚举的最后一段右端点为 \(i\)，长度为 1 的段比长度为 2 的段多 \(j\) 的方案数。
最后答案即为 \(\sum\limits_{j=0}^n f_{i, j}\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#else
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int n, mod;
std::cin >> n >> mod;
n *= 3;
std::vector<std::unordered_map<int, long long> > f(n + 1);
f[0][0] = 1;
for (int i = 0; i < n; ++i)
for (auto [j, k] : f[i]) {
(f[i + 1][j + 1] += k) %= mod;
if (i + 2 <= n)
(f[i + 2][j - 1] += k * (i + 1) % mod) %= mod;
if (i + 3 <= n)
(f[i + 3][j] += k * (i + 1) % mod * (i + 2) % mod) %= mod;
}
long long res = 0;
for (int i = 0; i <= n; ++i)
(res += f[n][i]) %= mod;
std::cout << res << '\n';
return 0;
}5. Runaway Quail
数轴上有 \(n\) 只鸡，初始位置为非 \(0\) 整数 \(p_i\)，奔跑速度为 \(s_i\)。你初始在 \(0\) 位置，奔跑速度为 \(Y(Y>s_i)\)。你要抓到所有鸡。
你可以在任意时刻调转方向；鸡总会朝着远离你的方向奔跑；当你的坐标和鸡重合时，你抓到鸡。
问抓到所有鸡的最短时间（显然是个实数）。\(n\le 500\)。
容易发现鸡的奔跑方向从始至终不会变，如果我们要从往左追变成往右追，显而易见地我们会在追上右边第一只鸡前经过原点，反之同理。
那么有一个很神奇的状态设计，设 \(f_{i,j}\) 为追上了左边速度第 \(1\sim i - 1\) 大的所有鸡和右边速度第 \(1\sim j - 1\) 大的所有鸡，然后跑回原点的最小时间，这样我们就不用记录这个非常难记录的当前位置信息，对于速度排名 \(\ge i,j\) 的所有鸡，当前是否追上我们并不关心——如果其位置比较远，那么我们会在后续转移中再考虑；如果其位置比较近，在解决速度排名 \(<i,j\) 的鸡时就已经抓住。
我们 \(\mathcal O(n)\) 枚举上一次反向是在抓住哪一只鸡时，然后让中间全部同向跑即可。
也就是说，假设我们要用 \(f_{i,j}\) 更新 \(f_{k,j}\)（\(k<i\)），那么只需要更新抓住速度排名 \(i\sim k+1\) 中跑得最远的一只鸡所需额外时间。按速度排序后可以线性算代价。
#include <bits/stdc++.h>
const long double eps = 1e-12;
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 v, n;
std::cin >> v >> n;
std::vector<std::pair<int, int> > a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i].first;
for (int i = 1; i <= n; ++i)
std::cin >> a[i].second;
a.emplace_back(0, 0), ++n;
std::sort(a.begin() + 1, a.end());
int p = std::lower_bound(a.begin() + 1, a.end(), std::make_pair(0, 0)) - a.begin();
std::sort(a.begin() + 1, a.begin() + p, [](std::pair<int, int> x, std::pair<int, int> y) { return x.second == y.second ? x.first < y.first : x.second > y.second; });
std::sort(a.begin() + p + 1, a.end(), [](std::pair<int, int> x, std::pair<int, int> y) { return x.second == y.second ? x.first < y.first : x.second < y.second; });
std::vector<std::vector<long double> > f(n + 1, std::vector<long double> (n + 1, 1e18));
f[1][n] = 0.;
auto at = [&](int i, long double t) {
return std::fabs(a[i].first + t * a[i].second * (i < p ? -1 : 1));
};
auto calc = [&](int i, long double t) {
return at(i, t) / (v - a[i].second);
};
// for (int i = 1; i <= n; ++i)
// printf("%d: (%d, %d)\n", i, a[i].first, a[i].second);
for (int i = 1; i <= p; ++i)
for (int j = n; j >= p; --j) {
if (i == p && j == p)
break;
long double d = 0.;
// printf("[%d, %d]: %lf\n", i, j, f[i][j]);
for (int k = i; k < p; ++k) {
if (at(k, f[i][j]) >= at(i, f[i][j]) - eps)
d = std::max(d, calc(k, f[i][j]));
// printf(" k1 = %d, d = %lf\n", k, d);
f[k + 1][j] = std::min(f[k + 1][j], f[i][j] + d + (k != j - 1) * d);
}
d = 0.;
for (int k = j; k > p; --k) {
if (at(k, f[i][j]) >= at(j, f[i][j]) - eps)
d = std::max(d, calc(k, f[i][j]));
// printf(" k2 = %d, d = %lf\n", k, d);
f[i][k - 1] = std::min(f[i][k - 1], f[i][j] + d + (k != i + 1) * d);
}
}
{
static int casetot = 0;
std::cout << "Case #" << ++casetot << ": ";
}
std::cout << std::fixed << std::setprecision(9) << f[p][p] << '\n';
}
return 0;
}6. The Great Marathon
https://codeforces.com/problemset/problem/38/H
给定一个 \(n\) 个点 \(m\) 条边的无向连通图，点 \(i\) 上初始有选手 \(i\)。为每个选手任意指定终点（可重复），那么最后的排名按照最短路为第一关键字、编号为第二关键字排序。
现按照排名序列分成前中后三段，记为金银铜牌；满足金牌数在 \([g_1,g_2]\) 之间，银牌数在 \([s_1,s_2]\) 之间。任意指定发牌数量和每个人的终点，问最后有多少种方案数；两个方案不同当且仅当有至少一个人拿的牌不一样。
\(n\le 50,m\le 1000\)。
\(n=50\)：可能需要考虑 \(n^5\) 做法。
发现是 需要确定顺序的 DP。关键位置自然在于『金银、银铜界处』。考虑钦定金牌最后一名、铜牌第一名的人选（不考虑中间的银牌是因为会出现这样那样的问题），还需要枚举他们的路程吗？并不。甚而至于，这样做会算重。
考虑『最小化』左右两侧的金牌、铜牌可选集合。强行让金牌最后一名 \(u\) 的路程为 \(\min\{dis_{u,i}\}\)，最小路程小于这个值的所有元素都可以成为金牌；同时让铜牌第一名 \(v\) 的路程为 \(\max\{dis_{v,i}\}\)，最大路程大于这个值的所有数都可以成为铜牌。
Q1: 如果存在一个 \(i\)，它最小的距离也比 \(u\) 的最小距离大，但实际上当 \(u\) 更大一点儿的时候，\(i\) 可以成为金牌呢？
A1：这种情况在钦定 \(i\) 为最后一名的时候讨论过了。
Q2：是否会算重？
A2：如上所述，假如在钦定 \(i\) 的时候统计了 \(u\)，那么在钦定 \(u\) 的时候就不会统计 \(i\)。
考虑转移。令 \(f_{i,u,v,j,k}\) 为考虑到 \(i\)，金牌倒一为 \(u\)，铜牌第一为 \(v\)，选了 \(j\) 个金、\(k\) 个铜的方案数。转移是 \(O(1)\) 的。
注意 vector 要开在循环外面，不然申请空间很耗时间 /ll
#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 n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1, std::vector<int> (n + 1, inf));
for (int x, y; m--; ) {
std::cin >> x >> y;
std::cin >> g[x][y], g[y][x] = g[x][y];
}
for (int i = 1; i <= n; ++i)
g[i][i] = 0;
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
if (k != i)
for (int j = 1; j <= n; ++j)
if (i != k && j != k)
g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
int g1, g2, s1, s2;
std::cin >> g1 >> g2 >> s1 >> s2;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (g[i][j] != inf)
g[i][j] = g[i][j] * n + i;
std::vector<int> mx(n + 1), mn(n + 1, inf);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
if (j != i)
mn[i] = std::min(mn[i], g[i][j]);
mx[i] = *std::max_element(g[i].begin() + 1, g[i].end());
}
auto res(0ll);
std::vector<std::vector<std::vector<long long> > > f(n + 1, std::vector<std::vector<long long> > (n + 1, std::vector<long long> (n + 1)));
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
if (v != u) {
f[0][1][1] = 1ll;
for (int i = 1; i <= n; ++i)
if (i == u || i == v)
f[i] = f[i - 1];
else {
bool flag = 0;
for (int j = 1; j <= n; ++j)
if (mn[u] < g[i][j] && g[i][j] < mx[v]) {
flag = 1;
break;
}
for (int j = 1; j <= g2; ++j)
for (int k = 1; k <= n - g1 - s1; ++k) {
f[i][j][k] = 0ll;
if (mx[i] < mn[u])
f[i][j][k] = f[i - 1][j - 1][k];
else if (mn[i] > mx[v])
f[i][j][k] = f[i - 1][j][k - 1];
else {
if (flag)
f[i][j][k] = f[i - 1][j][k];
if (mn[i] < mn[u])
f[i][j][k] += f[i - 1][j - 1][k];
if (mx[i] > mx[v])
f[i][j][k] += f[i - 1][j][k - 1];
}
}
}
for (int g = g1; g <= g2; ++g)
for (int s = s1; s <= s2; ++s)
res += f[n][g][n - g - s];
}
std::cout << res << '\n';
return 0;
}7. Sorting Pancakes
https://codeforces.com/contest/1675/problem/G
给定盒子 \(1\sim n\) 和每个盒子 \(i\) 里的初始球数 \(a_i\)，每次可以选择一个球移动到相邻盒子，最后欲使盒子内球数单调不升,求最小移球次数。
\(n,\sum a_i\le 250\)。
简单题！这种『移动元素的题』，会考虑钦定每个元素最终的值，把前面的元素富余的 / 欠下来的存储起来。当然也有例外，比如添加了『时间』这一维的限制，goto solu to Pass to Next
在如果在 \(i\) 处富余了 \(x\)，那么在移动到 \(i+1\) 的过程中就会产生 \(|x|\) 的代价。
令 \(f_{i,k,j}\) 表示第 \(i\) 个元素处，钦定它最终为 \(j\)，富余 \(k\)，则 \(f_{i,k,j}\gets \min\limits_{j'\ge j}\{f_{i-1, k-(j-a_i),j'}\}\)。显而易见后缀 min 优化就能 \(O(n\cdot m^2)\) 地做了。
DP 数组和后缀 min 数组要合起来，不然会 MLE /ll
#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 n, m;
std::cin >> n >> m;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
using arr = std::vector<int>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
crr f(n + 1, brr(2 * m + 1, arr(m + 1, inf)));
std::fill(f[0][m].begin(), f[0][m].begin() + m + 1, 0);
for (int i = 1; i <= n; ++i)
for (int k = 0; k <= 2 * m; ++k)
for (int j = std::min(m, k + a[i]); j >= std::max(0, k + a[i] - 2 * m); --j) {
f[i][k][j] = f[i - 1][k - (j - a[i])][j] + std::abs(k - m);
if (j != m)
f[i][k][j] = std::min(f[i][k][j], f[i][k][j + 1]);
}
std::cout << f[n][m][0] << '\n';
return 0;
}8. Complexity
https://atcoder.jp/contests/agc033/tasks/agc033_d
给定 \(n\times m\) 的 \(01\) 矩阵。定义其子矩阵的凌乱度：
- 若该矩阵中只有一种值，凌乱度为 \(0\)。
- 否则，任意竖直 / 水平切一刀，得到两个小矩阵；若它们的凌乱度分别为 \(a,b\)，则大矩阵的凌乱度为 \(\max(a,b)+1\) 的最小值。
求给定矩阵的凌乱度。\(n,m\le 185\)。
如果暴力枚举 DP，很不幸是 \(n^5\) 的。考虑优化。发现矩阵的凌乱度大致在 \(O(\log n)\) 级别，考虑用状态交换答案减小复杂度。具体地，设 \(f_{k,u,d,l}\) 表示凌乱度 \(\le k\) 时，\(r\) 可取到的最大值，那么有转移：
- 竖着切一刀，枚举切点 \(i\le f_{k-1,u,d,l}\)，有 \(f_{k,u,d,l}\gets f_{k-1,u,d,i+1}\)。发现显然 \(i\) 取 \(f_{k-1,u,d,l}\) 的时候最优，这个是 \(O(1)\) 的。
- 横着切一刀，枚举切点 \(i\in[u,d)\)，有 \(f_{k,u,d,l}\gets \min(f_{k-1,u,i,l},f_{k-1,i+1,d,l})\)。发现随 \(i\) 增大左边单调不增，右边单调不降。随着 \(d\) 的增大，左边不变，右边下移，交出来的交点一直右移。然后就可以优化到均摊 \(O(1)\)。
#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 n, m;
std::cin >> n >> m;
std::vector<std::vector<char> > a(n + 1, std::vector<char> (m + 1));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
std::cin >> a[i][j];
using arr = std::vector<int>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
std::vector<std::string> res;
std::vector<crr> _f(2, crr(n + 1, brr(m + 1, arr(n + 1))));
for (int k = 0; ; ++k) {
auto &f = _f[k & 1], &f1 = _f[(k & 1) ^ 1];
if (k == 0) {
crr tag(m + 1, brr(n + 1, arr(n + 1, -1)));
for (int l = 1; l <= m; ++l)
for (int u = 1; u <= n; ++u)
for (int d = u; d <= n && a[d][l] == a[u][l]; ++d)
tag[l][u][d] = a[u][l];
for (int u = 1; u <= n; ++u)
for (int d = u; d <= n; ++d)
for (int l = m; l; --l) {
f[u][l][d] = l - 1;
if (~tag[l][u][d]) {
if (l != m && tag[l][u][d] == tag[l + 1][u][d])
f[u][l][d] = f[u][l + 1][d];
else
f[u][l][d] = l;
}
}
}
else
for (int u = 1; u <= n; ++u)
for (int l = 1; l <= m; ++l)
for (int d = u, pos = 1; d <= n; ++d) {
f[u][l][d] = f1[u][l][d];
if (f[u][l][d] != m) {
f[u][l][d] = std::max(f[u][l][d], f1[u][f1[u][l][d] + 1][d]);
int mx = 0;
for (int i = pos; i < d; ++i) {
if (std::min(f1[u][l][i], f1[i + 1][l][d]) >= mx)
mx = std::min(f1[u][l][i], f1[i + 1][l][d]), pos = i;
else
break;
}
f[u][l][d] = std::max(f[u][l][d], mx);
}
}
if (f[1][1][n] == m) {
std::cout << k << '\n';
return 0;
}
}
return 0;
}9. Boxes and Balls
https://www.luogu.com.cn/problem/CF1845E
给定一个长度为 \(n\) 的 \(01\) 序列 \(a_{1\sim n}\)。你可以进行恰好 \(k\) 次如下操作：
- 选择序列中一对相邻且值不同的元素，将它们交换。
问有多少种最终序列。\(n,k\le 1500\)。
沿用 7. Sorting Pancakes 的思路，考虑令 \(f_{i,j,l}\) 表示最终序列的前 \(i\) 个里有 \(j\) 个 \(1\)，代价已经有 \(l\) 的方案数；那么令 \(s_i\) 为 \(a\) 的前缀和，显然有：
\[ f_{i+1,j+1,k+|j-s_i|}\gets f_{i,j,k}\\ f_{i+1,j,k+|j-s_i|}\gets f_{i,j,k} \]
最后在比 \(k\) 小且奇偶性和 \(k\) 相同的 \(l\) 里找答案。然后想怎么优化。
答案是不用优化。考虑有效状态数，打个表发现每个 \(i\) 在 \(O(n\sqrt n)\) 左右，但有另一种方法是发现有效的 \(|j-s_i|\) 不会超过 \(O(\sqrt n)\)（原因：为了消除 \(|j-s_i|\) 的欠账，需要 \(|j-s_i|\) 个位置；每个位置都会有差不多 \(|j-s_i|\) 的代价），所以枚举时只用枚举 \(O(\sqrt n)\) 个 \(j\)。
总之只用存有效状态会发现跑不满 
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
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<int> a(n + 1), s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::partial_sum(a.begin() + 1, a.end(), s.begin() + 1);
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
brr tag(n + 1, arr(n + 1));
std::vector<std::vector<std::pair<int, int> > > stt(2);
stt[0].emplace_back(0, 0);
crr _f(2, brr(n + 1, arr(k + 1)));
_f[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
auto &f = _f[i & 1], &f1 = _f[(i & 1) ^ 1];
std::vector<std::pair<int, int> >().swap(stt[(i & 1) ^ 1]);
for (auto [j, l] : stt[i & 1]) {
if (j + 1 <= s[n] && l + std::abs(j - s[i]) <= k) {
if (tag[j + 1][l + std::abs(j - s[i])] != i + 1)
tag[j + 1][l + std::abs(j - s[i])] = i + 1, stt[(i & 1) ^ 1].emplace_back(j + 1, l + std::abs(j - s[i])), f1[j + 1][l + std::abs(j - s[i])] = 0ll;
(f1[j + 1][l + std::abs(j - s[i])] += f[j][l]) %= mod;
}
if (l + std::abs(j - s[i]) <= k) {
if (tag[j][l + std::abs(j - s[i])] != i + 1)
tag[j][l + std::abs(j - s[i])] = i + 1, stt[(i & 1) ^ 1].emplace_back(j, l + std::abs(j - s[i])), f1[j][l + std::abs(j - s[i])] = 0ll;
(f1[j][l + std::abs(j - s[i])] += f[j][l]) %= mod;
}
}
std::cout << (int)stt[i & 1].size() << '\n';
}
auto res(0ll);
for (int i = k & 1; i <= k; i += 2)
if (tag[s[n]][i] == n)
(res += _f[n & 1][s[n]][i]) %= mod;
std::cout << res << '\n';
return 0;
}10. LEGOndary Grandmaster
https://codeforces.com/problemset/problem/1615/F
给定两个长度为 \(n\) 的 \(0/1/?\) 串 \(s,t\)，你可以对 \(s\) 进行若干次如下操作：
- 选择序列中一对相邻且值相同的元素，将它们取反。
现任意将 \(s\) 和 \(t\) 中的
?填为 \(0/1\)，问所有情况中 \(s\) 转化为 \(t\) 所需最小操作次数和（规定无解的操作次数为 \(0\)）。\(n\le 2000\)。
如果我们之前做过某些令人心（咬）旷（牙）神（切）怡（齿）的题目，会发现这个操作等价于交换任意两个相邻数，再让他们取反。
进一步地，可以交换运算顺序，先取反某个位置，再交换，再取反这个位置——把这个操作平均分配到 \(s\) 和 \(t\) 上，结合『相邻两数位置必一奇一偶』这个美妙的性质，想到把 \(s\) 和 \(t\) 的奇数位都提前取反，这样就可以转化成直接交换了，
接下来就和上一题有点不一样了。这里我们直接算一个位置的贡献——这意味着不需要统计一个序列的代价（此时失去了 \(k\) 的限制，代价来到 \(n^2\) 级别）。令 \(f_{i,j}\) 表示从前往后到了第 \(i\) 个位置，欠债为 \(j\) 的方案数；同样地，令 \(g_{i,j}\) 表示从后到前到了第 \(i\) 个位置，欠债为 \(j\) 的方案数。则贡献为 \(\sum_i \sum_j f_{i, j}\times g_{i + 1, -j}\times j\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
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::string s, t;
std::cin >> n >> s >> t, s = '#' + s, t = '#' + t;
for (int i = 1; i <= n; ++i)
if (i & 1) {
if (s[i] != '?')
s[i] = '0' + '1' - s[i];
if (t[i] != '?')
t[i] = '0' + '1' - t[i];
}
using arr = std::vector<long long>;
using brr = std::vector<arr>;
brr f(n + 1, arr(2 * n + 1)), g(n + 2, arr(2 * n + 1));
f[0][n] = 1ll;
for (int i = 1; i <= n; ++i) {
for (int S = 0; S <= 1; ++S)
if ((S == 0 && s[i] == '1') || (S == 1 && s[i] == '0'));
else
for (int T = 0; T <= 1; ++T) {
if ((T == 0 && t[i] == '1') || (T == 1 && t[i] == '0'));
else
for (int j = 0; j <= 2 * n; ++j)
if (j - (T - S) >= 0 && j - (T - S) <= 2 * n)
(f[i][j] += f[i - 1][j - (T - S)]) %= mod;
}
}
g[n + 1][n] = 1ll;
for (int i = n; i; --i) {
for (int S = 0; S <= 1; ++S)
if ((S == 0 && s[i] == '1') || (S == 1 && s[i] == '0'));
else
for (int T = 0; T <= 1; ++T) {
if ((T == 0 && t[i] == '1') || (T == 1 && t[i] == '0'));
else
for (int j = 0; j <= 2 * n; ++j)
if (j - (T - S) >= 0 && j - (T - S) <= 2 * n)
(g[i][j] += g[i + 1][j - (T - S)]) %= mod;
}
}
auto res(0ll);
for (int i = 1; i < n; ++i)
for (int j = 1; j <= n; ++j) {
(res += j * f[i][n + j] % mod * g[i + 1][n - j] % mod) %= mod;
(res += j * f[i][n - j] % mod * g[i + 1][n + j] % mod) %= mod;
}
std::cout << res << '\n';
}
return 0;
}