现在是 10 题。虽然看着很掉价，但是写够了 10 就改成 20 题。以此类推，免得我摆烂（）
自用向，不写太详细，把破题点写出来就差不多了。哦哦这里的破题是动词不是名词。
1. 字符合并
https://www.luogu.com.cn/problem/P3736
状压，区间 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
技巧 / 特殊性质类 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
你会发现删最少 = 留最多。
考虑 \(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_{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
容易发现鸡的奔跑方向从始至终不会变，如果我们要从往左追变成往右追，显而易见地我们会在追上右边第一只鸡前经过原点，反之同理。
那么有一个很神奇的状态设计，设 \(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;
}