补题
Crsuh2er0
·
·
个人记录
DP
线性 DP
P9753 [CSP-S 2023] 消消乐
遇到子段，考虑子段划分模型。
不难想到 $f[i]$ 可由前面得出的子串加上一个单位可消除子串得到。
这样的话，可以每次 $O(n^2)$ 暴力找以当前位置为结尾的单位可消除子串，设为 $s[j,i]$，则有
$$f[i] = f[j - 1] + 1$$
左右分别对应：
1. 将之前的串延长。
2. 当前新开一串。
时间复杂度 $O(n^3)$，期望得分 $35$。
考虑优化。
由于 $s[j,i]$ 是单位可消除子串，易知 $s[j] = s[i]$。
考虑 $s[j,i]$ 还包含若干个更小的可消除子串，所以不难证明 $j$ 应该是跳过这些更小的可消除子串后得到的使得 $s[j] = s[i]$ 成立的第一个 $j$。
用 $g[i]$ 表示最大的能使 $s[g[i],i]$ 成为可消除子串的起点位置，则初始时 $g[i] = i - 1$，然后
$$g[i] \leftarrow g[g[i]] - 1$$
直到 $s[g[i]] = s[i] \lor g[i] = 0$。
则有
$$f[i] = f[g[i] - 1] + 1 $$
考虑对于序列中的每种不同字符，从它在序列中出现的位置至多向前跳 $n$ 次就能找到相同的字符或跳到 $0$，故时间复杂度 $O(n|W|)$。
答案即为 $\sum_{i = 1}^n f[i]$。
空间复杂度 $O(n)$。
下面考虑进一步优化。
注意到对于每个字符我们都要往前跳不少次，而最重要的是其中很多次都是其他字符。
因此我们考虑用一种分类方法把不同字符分开。
如果令 $g[i] \leftarrow g[i] - 1$，会发现跳的方式形成若干条链。
考虑在每个位置记录 $a[c][i] = g[i]$，表示对于字符 $c$ 来说，可以合并成一段的新的单位可消除子串起点。
则 $s[a[c][i]] = c$ 且 $s[a[s[i]][i],i]$ 为合法子串。
每次修改 $a[s[i]][i]$。可以用 $to[i]$ 表示该链链头，每次修改 $a[s[i]][to[i]]$ 即可。
时间复杂度 $O(n)$，空间复杂度 $O(n|W|)$。
具体实现：
```cpp
for(int i = 1;i <= n;i++){
to[i] = i;
int g = a[s[i] - 'a'][to[i - 1]];
if(g) to[i] = to[g - 1],f[i] = f[g - 1] + 1; // 存在链头
a[s[i] - 'a'][to[i]] = i,ans += f[i]; // 更新 a，让下一个位置接上自己
}
```
[P11233 [CSP-S 2024] 染色](https://www.luogu.com.cn/problem/P11233)
不难想到的是子序列划分模型。
$O(n^3)$ 的 DP：
$f[i][x][y]$ 表示对于前 $i$ 个位置，上一个染成红色的是 $x$，上一个染成蓝色的是 $y$，此时得分的最大可能值。
那么有转移（由于每次都读取上一行的数据，这里压掉第一维）：
$$f[x][i] = \max_{x = 0}^{i - 2}(
f[x][i - 1] + [a[i] = a[i - 1]] \times a[i]) $$
$$
f[i][x] = \max_{x = 0}^{i - 2}(
f[i - 1][x] + [a[i] = a[i - 1]] \times a[i])
$$
$$
f[i - 1][i] = \max_{x = 0}^{i - 2}(
f[i - 1][x] + [a[i] = a[x]] \times a[i])
$$
$$
f[i][i - 1] = \max_{x = 0}^{i - 2}(
f[x][i - 1] + ]a[i] = a[x]] \times a[i])
$$
发现它是 $O(n^2)$ 的，喜提 $50pts$。
由于我太菜了，不能直接从转移或者问题的性质中得出优化，所以考虑输出 $f[i][j]$ 找规律优化。
观察由大样例第一个数据得出的表（$18$ 为输出的答案）：
```
18
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 5 10 10 10 10 10 10
0 0 0 0 0 0 0 0 5 0 5 5 5 5 5 5
5 5 5 5 5 5 5 5 10 5 0 10 10 10 10 10
5 5 5 5 5 5 5 5 10 5 10 0 15 15 15 15
5 5 5 5 5 5 5 5 10 5 10 15 0 15 15 15
5 5 5 5 5 5 5 5 10 5 10 15 15 0 15 15
5 5 5 5 5 5 5 5 10 5 10 15 15 15 0 18
5 5 5 5 5 5 5 5 10 5 10 15 15 15 18 0
```
容易发现蓝色与红色是对称的，所以我们先想办法把一半优化掉。
考虑使 $f[i][j],i < j$。
我们再画个转移图：
考虑我们上面得到的 $f[i - 1][i]$ 的转移会跨越对角线，而又由对称性可知 $f[i - 1][x] = f[x][i - 1]$，所以这个转移可以被改成不跨越对角线的。
那么有：
$$f[x][i] = \max_{x = 0}^{i - 2}(
f[x][i - 1] + [a[i] = a[i - 1]] \times a[i]) $$
$$
f[i - 1][i] = \max_{x = 0}^{i - 2}(
f[x][i - 1] + [a[i] = a[x]] \times a[i])
$$
现在得出的表：
```
18
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 5 10 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 5 5 5 5 5 5
0 0 0 0 0 0 0 0 0 0 0 10 10 10 10 10
0 0 0 0 0 0 0 0 0 0 0 0 15 15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 15 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
```
继续集中注意力，注意到除非 $a[i] = a[i - 1]$，否则答案好像总是在对角线旁边？（猜想）
继续注意。发现从上面的表中向右走等价于 $i$ 和 $i - 1$ 被染为同色。
注意到向右走的答案会更大当且仅当 $a[i] = a[i - 1]$。所以，猜想正确。
考虑不存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况，对于所有 $i$，它的答案都在对角线旁边。
先处理不存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况。考虑如何写出代码。
再观察一遍转移图：
显然，在没有长度 $\ge 2$ 相同段的情况下，有
$$f[i][j] = f[i][j + 1] \ (j > i)$$
而每一次 $f[i][i + 1]$ 的转移只与 $f[j][i] \ (0 \le j < i)$ 有关。
联立得，每一次 $f[i][i + 1]$ 的转移只与 $f[j][j + 1] \ (0 \le j < i)$ 有关。
此时如何优化已经显而易见。
用 $f[i]$ 表示上面的 $f[i][i + 1]$。
由之前得出的转移：
$$
f[i - 1][i] = \max_{x = 0}^{i - 2}(
f[x][i - 1] + [a[i] = a[x]] \times a[i])
$$
则在上述情况下，
$$f[i - 1] = \max_{x = 0}^{i - 2} (f[x] + [a[i] = a[x]] \times a[i]) \ (1 \le i \le n)$$
阶段性成果：
```cpp
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2020;
int n,a[MAXN];
ll f[MAXN];
void init() {
memset(f,0,sizeof f);
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
}
void solve() {
init();
for(int i = 1;i <= n;i++){
for(int x = 0;x <= i - 2;x++){
f[i - 1] = max(f[i - 1],f[x] + (a[i] == a[x]) * a[i]);
}
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
```
再考虑存在长度 $\ge 2$ 的相同 $a[i]$ 段的情况。
回忆我们刚刚干了什么，发现我们事实上做了：
$$f[i] \leftarrow f[i][j] \ (i < j \le n) $$
考虑这样的段，发现如果 $a[i] = a[i - 1]$，则由上面打的 $f$ 表发现：
$$f[i][j + 1] \leftarrow f[i][j] + a[i] \ (i < j < n) $$
对应到我们现在定义的状态，则有
$$f[j] \leftarrow f[j] + a[i] \ (0 \le j < i - 1) $$
暴力加即可。
做完这些，我们得到了一个全新的，时间 $O(n^2)$，空间 $O(n)$ 的算法，仍然 $50pts$。
阶段性成果：
```cpp
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10;
int n,a[MAXN];
ll f[MAXN];
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
for(int i = 1;i <= n;i++) cin >> a[i];
}
void solve() {
init();
for(int i = 1;i <= n;i++){
for(int x = 0;x <= i - 2;x++){
f[i - 1] = max(f[i - 1],f[x] + (a[i] == a[x]) * a[i]);
}
if(a[i] == a[i - 1]){
for(int j = 0;j <= i - 2;j++) f[j] += a[i];
}
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
```
继续优化。
观察上述转移方程，分类讨论发现：
$$f[i - 1] = \max(\max_{1 \le j \le i - 2} f[j] ,\max_{1 \le j \le i - 2,a[j] = a[i]}f[j] + a[i])$$
因此考虑记录 $f[j]$ 的最大值和 $a[j] = C$ 的 $f[j]$ 最大值（开桶记录），直接转移即可。
做完这些，我们得到了一个全新的，时间 $O(n^2)$，空间 $O(n)$ 的算法，但是常数比上一个小一点，喜提 $60pts$。
阶段性成果：
```cpp
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10,MAXV = 1e6 + 10;
int n,a[MAXN];
ll f[MAXN],premax,maxlst[MAXV];
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
premax = 0;
for(int i = 1;i <= n;i++) cin >> a[i],maxlst[a[i]] = 0;
}
void solve() {
init();
for(int i = 2;i <= n;i++){
f[i - 1] = max(premax,maxlst[a[i]] ? f[maxlst[a[i]]] + a[i] : 0);
if(a[i] == a[i - 1]) {
premax += a[i];
for(int j = 0;j <= i - 2;j++) {
f[j] += a[i];
}
}
premax = max(premax,f[i - 1]);
if(maxlst[a[i - 1]] == 0 || f[i - 1] > f[maxlst[a[i - 1]]]) maxlst[a[i - 1]] = i - 1;
}
cout << *max_element(f,f + n) << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
```
不难发现要实现前缀加，单点查，所以直接糊一个 BIT 上去就完事了！！！11。
时间复杂度 $O(n \log n)$，空间复杂度 $O(n + V)$。
注意 BIT 下标必须从 $1$ 开始，所以我们把所有下标 $ + 1$。
由于没有把修改直接应用于 $f$，所以输出答案时要输出 $premax$ 而不是 $\max f[i]$。
```cpp
#include <bits/extc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 10,MAXV = 1e6 + 10;
int n,a[MAXN];
ll f[MAXN],premax,maxlst[MAXV],ans;
struct bit{
ll t[MAXN];
void init(){
memset(t,0,sizeof(ll) * (n + 7));
}
int lb(int x){
return x & -x;
}
void add(int loc,ll val){
for(int i = loc;i <= n;i += lb(i)) t[i] += val;
}
void add(int l,int r,ll val){
add(l,val),add(r + 1,-val);
}
ll query(int loc){
ll res = 0;
for(int i = loc;i;i -= lb(i)) res += t[i];
return res;
}
} t;
void init() {
cin >> n;
memset(f,0,sizeof(ll) * (n + 7));
t.init();
premax = ans = 0;
for(int i = 1;i <= n;i++) cin >> a[i],maxlst[a[i]] = 0;
}
void solve() {
init();
for(int i = 2;i <= n;i++){
f[i - 1] = max(premax,maxlst[a[i]] ? f[maxlst[a[i]]] + t.query(maxlst[a[i]] + 1) + a[i] : 0);
if(a[i] == a[i - 1]) {
premax += a[i];
t.add(1,i - 1,a[i]);
}
premax = max(premax,f[i - 1]);
if(maxlst[a[i - 1]] == 0 || f[i - 1] > f[maxlst[a[i - 1]]] + t.query(maxlst[a[i - 1]] + 1)) maxlst[a[i - 1]] = i - 1;
}
cout << premax << '\n';
}
int main(){
int t;
cin >> t;
while(t--) solve();
}
```
# 图论
## 图染色
[P9869 [NOIP2023] 三值逻辑](https://www.luogu.com.cn/problem/P9869)
容易想到的是先求出原序列和末序列，末序列中的值为对应值在原序列中的下标，然后这原值和末值应相等。
可能有人和我一样想到用一个 $fa[u]$ 数组表示末序列，然后再用另一个数组 $val[u]$ 记录一个点是否是 $T,F,U$。
这个做法的局限性在于 $val[u]$ 记录的值具有时效性。
第一种情况是我们在 $+$ 操作时 $val[u] \leftarrow val[fa[v]]$。
例如下面一组数据：
```
3 3
+ 3 1
U 1
+ 1 3
```
根据上面的方法，我们认为最终 $fa[1] = 1,val[1] = U$。显然，这是错的。
因为第三个操作时，我们读取了 $val[3]$，而 $val[3]$ 是在我们操作二之前得到的 $val[1]$。
然而我们在第三个操作时会错误地认为 $val[3] = val[1] = U$。
我们改一下，在 $+$ 操作时 $val[u] \leftarrow val[v]$。这样，每次读取的都是对应变量的当前值，是正确的。
此外，对于 $u$ 与 $fa[u]$ 的 $+/-$ 关系，我们还应用一个 $con[u]$ 数组来记录。当每次更新 $fa[u] \leftarrow fa[v]$ 时，还应更新 $con[u] \leftarrow [sgn = -] \oplus con[v]$。
然后建图染色即可。这样，本题就做完了。
其实本题的主要难度并不在于后面的图染色/并查集做法，而是在于保持头脑清醒并理解如何记录关系的变换。
# DS
## DSU