2025.9.13 模拟赛

MEXP

树形dp 质数 前缀和 差分

首先我把最小的、不整除其中一个数的最小质数转成每个数，不整除它的最小质数，中的最小值。因此对于每一个点我们维护一个值，表示不整除它的最小质数，那么 $f(x,y)$ 就变成了求 $x$ 到 $y$ 路径上的点的最小值。

由于前 $10$ 个质数的 LCM（即乘积）就已经超过值域了，因此再离散化一下变成 $0\sim 9$ 的数。发现很小，所以考虑把它放进状态里面做 dp。设 $d{p}_{i,j}$ 表示在 $i$ 到 $i$ 的子树中任意一个点的路径，其中最小值为 $j$ 的个数，那么合并子树时就可以枚举 $j$ 然后把儿子连到当前节点上，新的 $j$ 就是 $\min (a_x,j)$。那么统计 $i$ 到 $i$ 子树的路径答案和就很容易了。

但是还有一种路径是 $x$ 往上走若干个节点到一个祖先，然后往其它子树走。这种情况可以使用整个树和当前子树做差得到……吗？由于根是不一样的，因此 $j$ 很难处理。如果我们只往上面走一步的话，还是很好处理的，用父亲的状态整体对儿子的状态做差（按照合并时的方式逆着做），然后统计。

但是很明显可以往上走超过 $1$ 步，因此可以做一个树上前缀和。

include <iostream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kP = 12, kD[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
 
LL a[kMaxN], dp[kMaxN][kP], ans[kMaxN], tmp[kMaxN], t, n;
vector<LL> e[kMaxN];
 
void dfs(LL x, LL f) {
  fill(begin(dp[x]), end(dp[x]), 0);
  dp[x][a[x]] = 1;
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    dfs(i, x);
    for (LL j = 0; j < kP; j++) {
      dp[x][min(a[x], j)] += dp[i][j];
    }
  }
  for (LL i = 0; i < kP; i++) {
    ans[x] += kD[i] * dp[x][i];
  }
}
 
void dfs2(LL x, LL f) {
  if (f) {
    for (LL i = 0; i < kP; i++) {
      dp[f][min(a[f], i)] -= dp[x][i];
      tmp[i] = dp[x][i];
    }     
    for (LL i = 0; i < kP; i++) {
      ans[x] += dp[f][i] * kD[min(a[x], i)];
    }
    for (LL i = 0; i < kP; i++) {
      dp[x][min(a[x], i)] += dp[f][i];
    }
    for (LL i = 0; i < kP; i++) {
      dp[f][min(a[f], i)] += tmp[i];
    }
  }
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    dfs2(i, x);
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    fill(e + 1, e + n + 1, vector<LL>());
    fill(ans + 1, ans + n + 1, 0);
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
      for (LL j = 0; j < kP; j++) {
        if (a[i] % kD[j]) {
          a[i] = j;
          break;
        }
      } 
    }
    for (LL i = 1, u, v; i < n; i++) {
      cin >> u >> v;
      e[u].push_back(v);
      e[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    for (LL i = 1; i <= n; i++) {
      cout << ans[i] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

音乐节目

数学 组合数学 博弈论 博弈dp

赛时我靠着手玩样例+大脑烧烤+结论猜测，得到了 $m=1$ 下的答案为 $\frac{k}{2^{n-1}}$，成功获得了 $20$ 分。但没有继续思考了，遗憾挂分。赛后我把我的思路写一下。

首先刚才我只写了子任务一，但是做人是要有追求的，所以我们盯着子任务二，发现其 $\le 2000$ 的数据范围很适合做一个 $\mathcal{O}(nm)$ 的 dp，所以可以设计状态：设 $d{p}_{i,j}$ 表示为当 $n=i,j=m$ 时的答案。首先是初始状态，如果 $n=m$ 时即 Bob 每次都要加，因此答案为 $nk$，所以有 $d{p}_{i,i}=ik$。

然后就是我最摸不透的转移部分了，主要还是对这种博弈题“绝对聪明”的各个情况分析能力不行。假设多一个回合，新回合 Alice 选择的数为 $x$，如果 Bob 这回合要增加音量，那么值就是 $d{p}_{i-1,j-1}+x$，如果 Bob 这回合降低音量，那么值就是 $d{p}_{i-1,j}-x$，但是 Bob 会选择音量小的，因此值是 $\min (d{p}_{i-1,j-1}+x,d{p}_{i-1,j}-x)$。而 Alice 会选择最大化音量，因此最终值为 $\underset{x\in [0,k]}{\max }\min (d{p}_{i-1,j-1}+x,d{p}_{i-1,j-x})$。这个值是 $d{p}_{i-1,j-1}+x$ 和 $d{p}_{i-1,j}-x$ 的平均值。

我觉得思路还是不够清晰，其实就是 Alice 虽然是先手，但是 Bob 掌控着最终决策权，因此 Alice 选完任意的之后 Bob 会选 $\min$ 值，Alice 需要最大化 $\min$ 值，也就是求 $\min$ 值的 $\max$。

所以我们得到了转移方程 $d{p}_{i,j}=\frac{d{p}_{i-1,j-1}+d{p}_{i-1,j}}{2}$。时间复杂度 $\mathcal{O}(nm)$。

现在我们需要优化。假设初始状态为 $(i,i)$，那么我们需要计算他有多少种方式得到 $(n,m)$，并根据步数相应地折半。把除以二拆掉，可以发现上面的形式和组合数递推公式一模一样，但是把 $(i,i)$ 作为组合数的初始状态，那么就需要进行一些减法偏移。最终会得到分子为 $\left(\genfrac{}{}{0ex}{}{n-i-1}{m-i}\right)$，带上初始状态值就是 $ik\times \left(\genfrac{}{}{0ex}{}{n-i-1}{m-i}\right)$。然而步数恒定是 $n-i$ 步的，因此分子为 $2^{n-i}$，最终答案就是

$$\sum _{i=1}^{m}ik\times \left(\genfrac{}{}{0ex}{}{n-i-1}{m-i}\right)$$

还要注意 $n=m$ 的边界情况。

两个排列

不会啊，代码啥都没写。

蜗蜗序列

首先轻而易举地写出对于 $n\le 7$ 的数据时间复杂度为 $\mathcal{O}((n+1{)}^n{2}^{n}n)$ 的暴力 DFS，然后观察到子任务二只有 $\le 10$，因此加上一个可行性优化之后直接把 $\le n$ 的所有答案都跑出来（最后一个开 O2 跑了两分钟），打成表之后直接输出。时间复杂度 $\mathcal{O}(1)$，成功通过 $30$ 分。

总结

总分：$100+20+0+30=150$

主要还是第二题没有仔细思考，写完第一题就开摆了，其实第二题的思路并不是过于复杂的，如果下次能更加仔细、深度地思考应该就可以在这种结论题中取得更好的结果。主要还是放 T2 以为做不了，放 T1 肯定能做出来。 其中一个例子就是上次 2025.9.11 模拟赛 的 T1，这么难我都花 3h 写出来了。