## 字符串
#分治 #线段树
> [!note] 思路
>
> 首先看到每次都得砍半，所以划分子问题的个数不会超过 $\mathcal O(\log_2 n)$，可以直接分治求解。
>
> 设 ${} dp_{i,j,c} {}$ 表示 $[i,j]$ 为 $c$ 好串需要的最少替换数，那么令 $m=\cfrac{i+j}{m}$，有
>
> $
> dp_{i,j,c}=\min\left(\sum_{i=1}^m[s_i\ne c]+dp_{m+1,j,c+1},dp_{i,m,c+1}+\sum_{i=m+1}^r[s_i\ne c]\right)
> $
>
> 求和部分可以做前缀和。但是 DP 数组不能直接存储。注意到递归树是一个线段树的结构，所以可以用类似线段树的节点标号方式。时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
const int kMaxN = 131072 + 5;
int dp[4 * kMaxN][26], pre[kMaxN][26], n;
string s;
int solve(int p, int l, int r, char c) {
if (dp[p][c - 'a'] != -1) {
return dp[p][c - 'a'];
}
if (l == r) {
return s[l] != c;
}
int m = (l + r) / 2;
int s = (m - l + 1) - (pre[m][c - 'a'] - pre[l - 1][c - 'a']),
t = (r - m) - (pre[r][c - 'a'] - pre[m][c - 'a']);
return dp[p][c - 'a'] = min(s + solve(2 * p + 1, m + 1, r, c + 1), solve(2 * p, l, m, c + 1) + t);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> s;
s = " " + s;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) {
pre[i][j] = pre[i - 1][j] + (s[i] == 'a' + j);
}
}
memset(dp, -1, sizeof(dp));
cout << solve(1, 1, n, 'a') << '\n';
return 0;
}
```
## 枪战地牢
#序列dp
> [!failure] 悲伤的事
>
> 我赛时的思路完全错误了。我最开始认为他会一只往右跑了之后回到最左边，但是第二个样例是蛇形走位，所以我就修改代码支持了蛇形走位，但是大样例一直 WA，鏖战两个半小时，无力战胜，最终挂 $35$ 分。
> [!info] 性质
>
> 首先我们需要从题面当中获得一些性质。
>
> - 由于 AWP 耗时最长，所以 AWP 只能用于杀死 Boss。
> - 一次往右走最多一次不会更劣。
> - 由于 $2$，结束在 $n$ 或 $n-1$ 不会更劣。
> [!question] 疑问
>
> 这个结论和我之前的思路产生了巨大的偏差，因为我的算法固执地认为走到头再回来一定是最优的（$n$ 那里多走两次），这样子前面的边都只走了 $2$ 次。但是实际上，对于 $i$（到了 $i$ 但是杀了前 $i-1$）想要到 $i+2$，可以杀了 $i$ 的小怪和扣 Boss 一滴血然后到 $i+1$，同样做这种操作在 $i+1$，然后返回 $i$ 终结 Boss 再到 $i+1$ 终结 Boss，最后到 $i+2$。同样移动了四步，均摊每个边走两次，而边权 $d$ 是恒定的，所以这样子做一定不劣。
> [!note] 转移
>
> 现在我们设 $dp_i$ 表示当前到了 $i$，但是在 $i$ 这里啥也没干需要耗费的最小时间。第一种转移：把 $i$ 的小怪手枪毙掉，然后 AWP 直接秒 Boss
>
> $
> dp_{i+1}=dp_i+a_i\times r_1+r3+d
> $
>
> 然后是先把 $i$ 小怪全杀死再干 Boss 一滴血，然后跑到 $i+1$ 那里再回来，杀死 Boss 再到 $i+1$。
>
> $
> dp_{i+1}=dp_i+\min((a_i+1)\times r_1,r_2)+d+d+r_1+d
> $
>
> 最后就是我疑问板块那里的转移了。
>
> $
> dp_{i+2}=dp_i+\min((a_i+1)\times r_1,r_2)+d+\min((a_{i+1}+1)\times r_1,r_2)
> $
时间复杂度 $\mathcal O(n)$。不得不说赛时真的是太糖了，居然最简单的性质都认为是错的。
```cpp
using LL = long long;
const LL kMaxN = 1e6 + 5;
LL a[kMaxN], dp[kMaxN], n, r1, r2, r3, d;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> r1 >> r2 >> r3 >> d;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
fill(begin(dp), end(dp), 1e18);
dp[1] = 0;
for (LL i = 1; i <= n; i++) {
dp[i + 1] = min(dp[i + 1], dp[i] + a[i] * r1 + r3 + d);
dp[i + 1] = min(dp[i + 1], dp[i] + min((a[i] + 1) * r1, r2) + d + d + r1 + d);
dp[i + 2] = min(dp[i + 2], dp[i] + min((a[i] + 1) * r1, r2) + d + min((a[i + 1] + 1) * r1, r2) + d + r1 + d + r1 + d);
}
cout << min(dp[n + 1] - d, dp[n - 1] + min((a[n - 1] + 1) * r1, r2) + d + r1 * a[n] + r3 + d + r1) << '\n';
return 0;
}
```
## 序列
#线段树 #二分
> [!note] 暴力和初步优化
>
> 首先考虑如何单次 $\mathcal O(n^2)$ 做暴力。首先令 $l\gets x+1,r\gets n-y$，$[l,r]$ 就是查询的区间。把这个区间当中所有 $a_i=i$ 的都找出来，那么应该优先删 $i$ 最大的，否则后面的 $a_i=i$ 就删不了了。删了之后打标记做前缀和，得到 $a_i=i-k$（$k$ 是 $i$ 之前已删除节点数）。一直模拟。
>
> 如何优化？可能我们并不需要在意删除的顺序。假设 $i$ 前面有最多 $cnt$ 个可删除的节点（按照某种顺序删除），那么 $i$ 实际的下标区间在 $[i-cnt,i]$，只有 $a_i$ 属于这个区间 $i$ 才可能被删，如果满足总能找到某种顺序删除。
>
> 所以维护已删除数量 $cnt$，对于新的 $a_i$，如果 $cnt\ge a_i$，那么 $cnt\gets cnt+1$。最后 $cnt$ 就是答案。时间复杂度 $\mathcal O(qn)$。
> [!important] 优化
>
> 考虑优化。注意到我们的算法过程是从左到右的，因为依赖前面的 $cnt$，所以我们考虑再右端点上做功夫。把所有询问离线下来，对右端点进行排序，左端点的话就维护若干个 $cnt_l$，表示 $l$ 到当前的 $r$ 的最大删除数量。
>
> 那么当右端点往右扩展时，新加的元素要拼在后面，对于所有的 $cnt_l\ge a_r$，都要 $cnt_l\gets cnt_l+1$。看起来很难搞，但是注意到 $cnt_l$ 随着 $l$ 的递增而递减，所以可以用线段树维护 $cnt_l$，然后在线段树上二分出一段前缀均满足 $cnt_l\ge a_r$，把这个前缀的值都 $+1$。最后查询 $cnt_l$（$l$ 是当前询问的左端点）即可。
时间复杂度 $\mathcal O(q\log_2 n)$。
```cpp
const int kMaxN = 3e5 + 5;
int a[kMaxN], tr[4 * kMaxN], tag[4 * kMaxN], ans[kMaxN], n, q;
tuple<int, int, int> p[kMaxN];
void addTag(int p, int d) {
tr[p] += d;
tag[p] += d;
}
void pushDown(int p) {
if (tag[p]) {
addTag(2 * p, tag[p]);
addTag(2 * p + 1, tag[p]);
tag[p] = 0;
}
}
void modify(int p, int l, int r, int s, int t, int d) {
if (s > t) {
return;
}
if (s <= l && r <= t) {
addTag(p, d);
return;
}
pushDown(p);
int m = (l + r) / 2;
if (s <= m) {
modify(2 * p, l, m, s, t, d);
}
if (m < t) {
modify(2 * p + 1, m + 1, r, s, t, d);
}
tr[p] = min(tr[2 * p], tr[2 * p + 1]);
}
int binarySearch(int p, int l, int r, int val) {
if (l == r) {
return tr[p] >= val ? l : l - 1;
}
pushDown(p);
int m = (l + r) / 2, x = tr[2 * p];
if (x >= val) {
return binarySearch(2 * p + 1, m + 1, r, val);
}
return binarySearch(2 * p, l, m, val);
}
int query(int p, int l, int r, int x) {
if (l == r) {
return tr[p];
}
pushDown(p);
int m = (l + r) / 2;
if (x <= m) {
return query(2 * p, l, m, x);
}
return query(2 * p + 1, m + 1, r, x);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] = i - a[i];
if (a[i] < 0) {
a[i] = 1e9;
}
}
for (int i = 1; i <= q; i++) {
cin >> get<0>(p[i]) >> get<1>(p[i]);
get<0>(p[i])++;
get<1>(p[i]) = n - get<1>(p[i]);
get<2>(p[i]) = i;
}
sort(p + 1, p + q + 1, [](auto &&a, auto &&b) {
return get<1>(a) < get<1>(b);
});
for (int i = 1, j = 1; i <= q; i++) {
auto [l, r, id] = p[i];
for (; j <= r; j++) {
int x = min(binarySearch(1, 1, n, a[j]), j);
modify(1, 1, n, 1, x, 1);
}
ans[id] = query(1, 1, n, l);
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```
## 马自立
#欧拉回路
- [c] 赛时被 T2 折磨，根本无心做这道题，其实是后三题当中最简单的。
> [!note] 思路
>
> 首先可以看作先构建重要路径的图，然后加入若干条边，最后图整个变成欧拉回路。（因为不需要的边没加入）
>
> 无向图欧拉回路要求每个点的度数为偶数（连通性不用判，因为保证联通），所以对于必须加入的重要边先标记它们的度数。那么枚举端点跑 DFS，每次在遍历非关键邻边，然后递归搜索，回撤的时候判断这个点的度数是否为奇数，如果是那么就加入当前遍历的边。
>
> 最后看一下所有加入的边的点集每个点的度数是否为偶数即可。
时间复杂度 $\mathcal O(n+m)$。
```cpp
const int kMaxN = 5e5 + 5;
int d[kMaxN], f[kMaxN], t, n, m;
vector<pair<int, int>> g[kMaxN];
void dfs(int x) {
f[x] = 1;
for (auto [i, id] : g[x]) {
if (f[i]) {
continue;
}
dfs(i);
if (d[i]) {
d[i] ^= 1;
d[x] ^= 1;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> m;
fill(d + 1, d + n + 1, 0);
fill(f + 1, f + n + 1, 0);
fill(g + 1, g + n + 1, vector<pair<int, int>>());
for (int i = 1, u, v, c; i <= m; i++) {
cin >> u >> v >> c;
if (c == 1) {
d[u] ^= 1;
d[v] ^= 1;
} else {
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
}
bool b = 1;
for (int i = 1; i <= n; i++) {
if (!f[i]) {
dfs(i);
if (d[i]) {
b = 0;
break;
}
}
}
if (!b) {
cout << "No\n";
continue;
}
cout << "Yes\n";
}
return 0;
}
```
## 总结
**总分**：$100+35+40+0=175$。
最惨的一次，也是最糖的一次。死磕第二题，结果第三第四题我完全有能力做出来的没有写，然后第二题甚至还认为正确的性质是错误的。我以后一定不要在死磕 T2 了，包括像去年 CSP 一样，哪怕 T2 最后代码再短再糖，长时间写不出来（且不确定解法正确性），必须去写 T3 或者 T4。