2024.10.14 模拟赛

题目：2024.10.14 题目

通配符

有 $m$ 个不同的字符串，第 $i$ 个字符串为 $t_i$。又有长度为 $n$ 的含有 $\text{*}$ 的字符串 $S$，通配符 $\text{*}$ 可以在必要时变为任意字符串包括空串。对于 $S$ 的任意连续子串 $s\in S$，若 $s$ 能匹配任意 $t_i$ 则称 $s$ 是好的。求好的 $s$ 的数量。

---

对于 $n\le 200$ 的点，我们考虑枚举子串，然后判断子串是否能满足条件。设 $d{p}_{i,j}$ 表示为子串的前 $i$ 个字符能否匹配任意 $t_k$ 的前 $j$ 个字符。这是一个很基础的序列 dp，对于单个字符串的匹配时间复杂度为 $\mathcal{O}(n|t_k|)$，总时间复杂度为 $\mathcal{O}(n^3\sum _{i=1}^m|t_i|)$。

加下来我们考虑如何将枚举子串判断转换为对于 $t_k$ 有什么类型的子串能够匹配。令 $f_{i,j}$ 表示为有多少个以 $i$ 结尾的子串能够匹配 $t_k$ 的前 $j$ 位。此时可能会有两种情况：$s_i=\text{*}$，那么可以匹配任意多位的 $j$，类似完全背包，让 $f_{i,j}\leftarrow f_{i-1,j-1}+f_{i,j-1}$；否则我们枚举可能匹配到的 $j$，再判断 $s_i$ 是否等于 $s_j$，如果是就代表可以匹配多一位 $f_{i,j}\leftarrow f_{i-1,j-1}$，否则不能匹配，为 $0$。注意，这里的第一个维度是表示「以 $i$ 结尾」，这能够帮助我们在最后统计的时候统计所有的子串。此时，$f_{n,m}$ 里面装的就是以 $n$ 结尾、匹配了 $t_k$ 整个字符串的子串数量（$m=|t_k|$）。

但是我们仍然不能达到以任意位置结尾（任意子串），能够匹配 $t_k$ 的数量。因此我们加一个额外转移：$f_{i,j}\leftarrow f_{i-1,j}$，这样哪怕没有匹配这一位也会继续下去，就能够达成我们的目的。此外，为了防止爆空间，我们可以对 $f$ 采取滚动数组或压数组的方式避免。时间复杂度 $\mathcal{O}(n\sum _{i=1}^m|t_i|)$。

#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 _{i\in S}\sum _{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))$ 优秀一点。

#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$。每场战争会在 $\frac{n(n-1)}{2}$ 对文明中随机选取一对，交换排名。对于每个世纪，你需要求出在任意世纪选择的文明，在世纪结束后最终期望的排名的最小值。保留五位小数输出。

---

没有看懂题目，文件都没有创建，$0$ 分。赛后发现全部输出 $1$ 和第 $i$ 行输出 $i$ 均能够获得 $10$ 分，出题人你没马 🐴。

总结

• 排名：$4$；
• 比赛分数：$240/400$；
• 情况：相比 2024.10.13 模拟赛，好；
• 问题：找规律、数学推导水平较弱。