题目：[[2024.10.14 题目]]
## 通配符
有 $m$ 个不同的字符串，第 $i$ 个字符串为 $t_i$。又有长度为 $n$ 的含有 $\texttt{*}$ 的字符串 $S$，通配符 $\texttt{*}$ 可以在必要时变为任意字符串包括空串。对于 $S$ 的任意连续子串 $s\in S$，若 $s$ 能匹配任意 $t_i$ 则称 $s$ 是好的。求好的 $s$ 的数量。
---
对于 $n\le 200$ 的点，我们考虑枚举子串，然后判断子串是否能满足条件。设 $dp_{i,j}$ 表示为子串的前 $i$ 个字符能否匹配任意 $t_k$ 的前 $j$ 个字符。这是一个很基础的序列 dp，对于单个字符串的匹配时间复杂度为 $\mathcal O(n|t_k|)$，总时间复杂度为 $\mathcal O(n^3\sum\limits_{i=1}^m|t_i|)$。
加下来我们考虑如何将枚举子串判断转换为对于 $t_k$ 有什么类型的子串能够匹配。令 $f_{i,j}$ 表示为有多少个以 $i$ 结尾的子串能够匹配 $t_k$ 的前 $j$ 位。此时可能会有两种情况：$s_i=\texttt{*}$，那么可以匹配任意多位的 $j$，类似完全背包，让 $f_{i,j}\gets f_{i-1,j-1}+f_{i,j-1}$；否则我们枚举可能匹配到的 $j$，再判断 $s_i$ 是否等于 $s_j$，如果是就代表可以匹配多一位 $f_{i,j}\gets f_{i-1,j-1}$，否则不能匹配，为 $0$。注意，这里的第一个维度是表示「以 $i$ 结尾」，这能够帮助我们在最后统计的时候统计所有的子串。此时，$f_{n,m}$ 里面装的就是以 $n$ 结尾、匹配了 $t_k$ 整个字符串的子串数量（$m=|t_k|$）。
但是我们仍然不能达到以任意位置结尾（任意子串），能够匹配 $t_k$ 的数量。因此我们加一个额外转移：$f_{i,j}\gets f_{i-1,j}$，这样哪怕没有匹配这一位也会继续下去，就能够达成我们的目的。此外，为了防止爆空间，我们可以对 $f$ 采取滚动数组或压数组的方式避免。时间复杂度 $\mathcal O(n\sum\limits_{i=1}^m|t_i|)$。
```cpp
#include <fstream>
#include <string>
using namespace std;
using LL = long long;
const LL kMaxN = 5e4 + 5, kMod = 998244853;
ifstream cin("char.in");
ofstream cout("char.out");
LL dp[kMaxN], n, m, T, ans;
string s;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> T >> s;
s = ' ' + s;
for (string t; T; T--) {
cin >> t;
m = t.size();
t = ' ' + t;
fill(dp, dp + m + 1, 0);
for (LL i = 1; i <= n; i++) {
dp[0]++;
if (s[i] != '*') {
for (LL j = m; j >= 1; j--) {
dp[j] = s[i] == t[j] ? dp[j - 1] : 0;
}
dp[0] = 0;
} else {
for (LL j = 1; j <= m; j++) {
dp[j] = (dp[j] + dp[j - 1]) % kMod;
}
}
ans = (ans + dp[m]) % kMod;
}
}
cout << ans << '\n';
return 0;
}
```
## 树
有 $n$ 个点的树，第 $i$ 个点上染了 $c_i=0/1$ 的颜色。设 $S=\{i|c_i=1\},T=\{i|c_i=0\}$，则树的价值为 $\sum\limits_{i\in S}\sum\limits_{j\in T}d(i,j)$，其中 $d(i,j)$ 表示 $i$ 到 $j$ 的简单路径上的边权最大值。可以修改最多一个点使它的颜色反转，求最大价值。
---
利用惊人的注意力注意到 $1\le n\le 3\times 10^3$（坏笑），可以使用 $\mathcal O(n^2)$ 量级的算法。不难想到，我们可以枚举需要改变颜色的位置 $i$，将 $c_i$ 反转，然后在反转的基础上求出树的价值，这样压力就落到了 $\mathcal O(n)$ 求树的价值上了。
由于本题当中距离为取最大值而非累加的方式，因此我们可以以权值为单位进行处理。画图发现，对于一条边 $(u,v,w)$，有两个连通块分别为 $u,v$ 连接且权值不大于 $w$ 的，那么此时就可以将答案累加上 $u,v$ 两个连通块颜色不同的组合数量乘上 $w$，因此我们考虑如何合并满足要求的连通块。
合并连通块很容易想到并查集。我们按照权值 $w$ 对每一条边从小到大进行排序，此时对于边 $i$，$u_i$ 和 $v_i$ 的连通块都是满足条件的（连通块内所有边边权均不大于 $w$），我们直接进行累加，然后合并 $u_i$ 与 $v_i$ 所在的联通块。
使用额外数组 $s_{x,0/1}$ 记录 $x$ 所在连通块内黑白结点的数量，并在并查集合并时累加，即可完成需要的任务。时间复杂度 $\mathcal O(n^2\alpha(n))$。
**后记**：有巨佬整出了 $\mathcal O(n^2)$ 解法，就是 $\mathcal O(n^2)$ 预处理任意两个点之间的距离，然后再 $\mathcal O(n^2)$ 枚举更改颜色的结点并求出答案，比 $\mathcal O(n^2\alpha(n))$ 优秀一点。
```cpp
#include <fstream>
#include <algorithm>
using namespace std;
using LL = long long;
const LL kMaxN = 3e3 + 5;
ifstream cin("tree.in");
ofstream cout("tree.out");
struct Edge {
LL u, v, w;
} e[kMaxN];
LL c[kMaxN], f[kMaxN], s[kMaxN][2], n, ans;
LL findMotherFucker(LL x) {
return !f[x] ? x : f[x] = findMotherFucker(f[x]);
}
void getMarried(LL u, LL v) {
f[u] = v;
s[v][0] += s[u][0];
s[v][1] += s[u][1];
}
LL fuck() {
fill(f + 1, f + n + 1, 0);
for (LL i = 1; i <= n; i++) {
s[i][0] = c[i] == 0;
s[i][1] = c[i] == 1;
}
LL res = 0;
for (LL i = 1; i < n; i++) {
LL x = findMotherFucker(e[i].u);
LL y = findMotherFucker(e[i].v);
res += s[x][0] * s[y][1] * e[i].w;
res += s[x][1] * s[y][0] * e[i].w;
getMarried(x, y);
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> c[i];
}
for (LL i = 1; i < n; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e + 1, e + n, [](auto a, auto b) {
return a.w < b.w;
});
ans = max(ans, fuck());
for (LL i = 1; i <= n; i++) {
c[i] ^= 1;
ans = max(ans, fuck());
c[i] ^= 1;
}
cout << ans << '\n';
return 0;
}
```
## 木棍
有一根长度为 $n$ 的木棍，可以变出另外三根木棍 $a,b,c$ 满足 $n<a<b<c\le 4\times n$。如果这 $4$ 根木棍能够组成三角形，则称这次变换为成功的变换。求可能的成功的变换的数量。
---
采用暴力。枚举 $a,b,c$ 并判断可以达到 $\mathcal O(n^3)$。然后开始无用优化：不难发现拼凑三角形只会选择长度相邻的三根小木棒，因此我们可以只枚举 $a$ 和 $b$ 然后通过三角形的定义算出 $c$ 的范围。时间复杂度 $\mathcal O(n^2)$，和 $\mathcal O(n^3)$ 一样都是 $40$ 分。
## 群星
有一游戏分为 $k$ 个世纪，第 $i$ 个世纪会发生 $a_i$ 场最后战争。游戏里有 $n$ 个文明，第 $i$ 个文明初始排名为 $i$。每场战争会在 $\cfrac{n(n-1)}{2}$ 对文明中随机选取一对，交换排名。对于每个世纪，你需要求出在任意世纪选择的文明，在世纪结束后最终期望的排名的最小值。保留五位小数输出。
---
没有看懂题目，文件都没有创建，$0$ 分。赛后发现全部输出 $1$ 和第 $i$ 行输出 $i$ 均能够获得 $10$ 分，出题人你没马 🐴。
![[want-to-fuck-problem-creator.png]]
## 总结
- **排名**：$4$；
- **比赛分数**：$240/400$；
- **情况**：相比 [[2024.10.13 模拟赛]]，好；
- **问题**：找规律、数学推导水平较弱。