这一周练习了关于字符串专题。
复习了可持久化 trie，并学习了 AC 自动机。
AC 自动机
可以记录多个串互相的前缀关系，并用一个文本串可以匹配多个模式串。
简单来说就是在 trie 树上找 fail，具体方法是通过不断跳其父亲的 fail 来判断有没有这个相同的儿子，找到了则 fail 指向那个相等的节点，否则指向根（没有匹配）。
然而在实际使用中，可能需要一个点走向不是它原本儿子的字符，此时如果暴力跳 fail 就是不优的，所以可以提前处理它的其它儿子（指向它上面的点），这样就构成了 trie 图：每个点都能走向任意字符，保证 走到位置的串 和 当前串 + 字符 有最长的公共后缀，预处理整个过程的复杂度都是线性的，即为 \(\mathcal O(m)\)，其中 \(m\) 为模式串总长。
代码
void add(string s) {int len = s.size(), u = 0;for(int i = 0; i < len; i++) {if(!son[u][s[i] - 'A']) son[u][s[i] - 'A'] = ++idx;u = son[u][s[i] - 'A'];}vis[u]++; // 模式串的结尾
}
void build_nfa() {queue<int> q;for(int i = 0; i < 26; i++) {if(son[0][i]) {fail[son[0][i]] = 0;q.push(son[0][i]);}}while(q.size()) {int u = q.front();q.pop();for(int i = 0; i < 26; i++) {if(son[u][i]) {fail[son[u][i]] = son[fail[u]][i]; // 儿子的 fail 就是自己 fail 的儿子vis[son[u][i]] += vis[fail[son[u][i]]]; // fail 链上是模式串结尾的个数q.push(son[u][i]);} else {son[u][i] = son[fail[u]][i]; // 不存在这样的儿子就到 fail 去找}}}
}
可以用 AC 自动机解决一些有子串限制的计数（在 trie 图上 DP）。
电脑游戏
题目 和 题目。
这种 AC 自动机 DP 的题目一般状态都定义为 \(dp_{u,i}\)，\(u\) 表示走到了 \(u\) 号节点，\(i\) 表示考虑到文本串的第 \(i\) 位。
对于这道题，\(dp_{u,i}\) 就表示走到 \(u\) 且考虑了 \(i\) 位的最大得分。
其中 \(val_v\) 表示 \(v\) 及其 fail 链中的点作为模式串末尾的总次数，也就是走这一步的得分。
DP 部分
dp[0][0] = 0;
for(int i = 0; i < k; i++) {for(int u = 0; u <= idx; u++) {if(dp[i][u] == -0x3f3f3f3f) continue;for(int j = 0; j < 3; j++) {int v = son[u][j];dp[i + 1][v] = max(dp[i + 1][v], dp[i][u] + vis[v]);}}
}
这周的周练没有挂分，不过除了 T1 并没有过题。
T2 和 T3 都是有性质的，都没发现。
T2 和 T2：一个数 \(x\) 不断变为 \((x+P) \bmod Q\) 是会有周期的，且 \([0,Q-1]\) 中的数组成的若干个周期总共正好是 \([0,Q-1]\)。
T3 和 T3：考虑逆序对数变化时可以关注一个数前面比它大的数的个数的变化。
T4：最大（二进制）与生成树。一个方法是套用异或生成树的 01-trie 方法，其中把 0 的分支替换为 0 和 1 的 trie 树合并后的结果，然后正常做即可。
不过有更巧妙的解法，按照 kruskal 的方法从大到小枚举边权，考虑哪些点之间会有这样的边权，发现如果将 \(x\mid 2^j\) 看做 \(x\) 的父亲，则凡是有父亲的点想连的边由它的父亲来连是不会更劣的，所以套用这个思路，连向它的父亲并计算权值和即可。