2025.10.18 模拟赛

矩阵最大值

模拟

首先我们可以通过 $\mathcal{O}(nm)$ 的复杂度预处理出每一行和每一列的最大值，然后求出初始时一共有多少个满足条件的元素。

现在考虑修改对答案的影响。注意题目中加粗强调了修改之后的元素一定比原来更大，这也就代表着原先是最小值的元素再修改之后不会失去其地位，相当于提示我们仅需维护最大位置即可。

1. 修改后第 $x$ 行的最大值发生改变：需要减去第 $x$ 行原先的答案，更新最大值下标数组。
2. 修改后第 $y$ 列的最大值发生改变：需要减去第 $y$ 列原先的答案，更新最大值下标数组。

然后是对答案的增加。判断第 $x$ 行的最大位置是否为 $y$ 以及第 $y$ 列的最大位置是否为 $x$ 即可。然后你就会发现样例挂了。

仔细思考，如果第 $x$ 行和第 $y$ 列的最大位置没有发生任何改变，那么最后一步的增量是完全无需的，因为我们根本就没有减掉原来的贡献（如果你要减的话面临减重的问题，同样需要额外进行操作）。所以开个变量记录是否发生更改即可。

时间复杂度 $\mathcal{O}(nm+q)$。

#include <fstream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
ifstream cin("matrix.in");
ofstream cout("matrix.out");
 
LL a[kMaxN], b[kMaxN], n, m, q, ans;
 
// 判断第 x 行
bool check(LL x) {
  return b[a[x]] == x;
}
 
bool check2(LL x) {
  return a[b[x]] == x;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q;
  vector<vector<LL>> v(n + 1, vector<LL>(m + 1));
  for (LL i = 1; i <= n; i++) {
    for (LL j = 1; j <= m; j++) {
      cin >> v[i][j];
    }
  }
  for (LL i = 1; i <= n; i++) {
    for (LL j = 1; j <= m; j++) {
      if (v[i][j] > v[i][a[i]]) {
        a[i] = j;
      }
    }
  }
  for (LL j = 1; j <= m; j++) {
    for (LL i = 1; i <= n; i++) {
      if (v[i][j] > v[b[j]][j]) {
        b[j] = i;
      }
    }
  }
  for (LL i = 1; i <= n; i++) {
    ans += check(i);
  }
  for (LL x, y, t; q; q--) {
    cin >> x >> y >> t;
    bool change = 0;
    if (a[x] != y && t > v[x][a[x]]) {
      ans -= check(x);
      change = 1;
      a[x] = y;
    }
    if (b[y] != x && t > v[b[y]][y]) {
      ans -= check2(y);
      change = 1;
      b[y] = x;
    }
    v[x][y] = t;
    ans += change && a[x] == y && b[y] == x;
    cout << ans << '\n';
  }
  return 0;
}

病毒感染

模拟

本题我赛时思路跟托石一样，根本无法回忆或复述，所以讲不了赛时思路。

• [!] 需要注意的是，提供的矩阵是对于细胞而言对病毒的易感程度，而非对于被特定病毒感染的细胞对病毒的易感程度。这直接导致了我最开始的思路完全错误。

首先是对于 $p=1$，枚举可能的答案病毒类型 $i$，如果初始感染了病毒 $i$ 的细胞 $i$ 可以被任意一种其它的病毒感染的话，那么病毒 $i$ 将不复存在。可以直接 $\mathcal{O}(n^2)$ 或 $\mathcal{O}(n^3)$ 判断。

当然，我赛时代码也就过了这些可怜的 $40$ 分；对于 $p=2$，我完全没有得到任何分数。可恶的捆绑测试，我与你不共戴天。

对于 $p=2$，我们还是枚举病毒 $i$，判断病毒 $i$ 能否在某种攻击顺序当中存活下来。直接判断 $i$ 是否会被其它病毒给干死，然后 $i$ 能否干死可以把 $i$ 干死的病毒是不正确的，因为 $i$ 可能提前感染其它类型的病毒，以此留下后代。$i$ 身已死，病毒永存。

为了快速判断病毒 $i$ 和病毒 $j$ 谁在某个细胞的易感程度更高，可以令 $i{d}_{i,a_{i,j}}=j$，这样即可 $\mathcal{O}(1)$ 判断。

枚举病毒 $i$ 后，再次枚举细胞 $j$，判断 $i$ 能否在任意一个 $j$ 上留下后代。具体来说，$i$ 的优先级要比在 $j$ 最开始时自带的 $j$ 病毒的优先级要高；其次，定义门槛值 $zr{r}_i$ 表示细胞 $i$ 对于所有其排列中 $j\ge zr{r}_i$ 的病毒 $a_j$ 都可能会感染掉 $i$，需要满足 $i$ 在 $j$ 的排名不能超过 $j$ 的门槛值，这样 $j$ 就不会被其它病毒感染了。

至于如何求 $zrr$ 数组，可以使用 $\mathcal{O}(n^3)$ 暴力计算。枚举病毒 $i$，枚举细胞 $j$ 和病毒 $k$，如果 $k$ 可以感染最开始的细胞 $j$，那么求 $\max i{d}_{i,k}$ 即 $k$ 在 $i$ 中的排名，然后对这个最大值求 $\min$，得到可以感染 $i$ 的最小病毒，也就是门槛值。

#include <fstream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 505;
 
ifstream cin("virus.in");
ofstream cout("virus.out");
 
int a[kMaxN][kMaxN], id[kMaxN][kMaxN], zrr[kMaxN], n, p;
vector<int> ans;
 
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      id[i][a[i][j]] = j;
    }
  }
  cin >> p;
  if (p == 1) {
    for (int i = 1; i <= n; i++) {
      if (id[i][i] == 1) {
        ans.push_back(i);
      }
    } 
  } else {
    for (int i = 1; i <= n; i++) {
      zrr[i] = n;
      for (int j = 1; j <= n; j++) {
        int jb = 0;
        for (int k = 1; k <= n; k++) {
          if (id[j][k] <= id[j][j]) {
            jb = max(jb, id[i][k]);
          }
        }
        zrr[i] = min(zrr[i], jb);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (zrr[j] >= id[j][i] && id[j][i] <= id[j][j]) {
          ans.push_back(i);
          break;
        }
      }
    }
  }
  cout << ans.size() << '\n';
  for (int i : ans) {
    cout << i << ' ';
  }
  return 0;
}

怪物猎人

背包dp 树形dp

考虑树形 DP。首先我们可以通过 $\mathcal{O}(n)$ 的复杂度快速计算出初始时的答案。

发现 $n\le 2000$，考虑将杀死的节点数量加入状态。设 $d{p}_{i,j}$ 表示在 $i$ 的子树当中杀死了 $j$ 个节点，可以对答案减少的最大值。但是会发现一个问题，既然我们杀死节点 $i$ 会对答案减少 $2\times a_i$（$i=1$ 除外）和 $\sum _{j\in \mathrm{son}(i)}{a}_j$，那么如果 $i$ 和其儿子 $j$ 都被杀死了，儿子 $j$ 减少的 $a_i$ 不应该乘 $2$，因为 $i$ 已经杀死了不需要求儿子的 $a_j$ 和，但是如果不加当 $i$ 没被杀死时仍然需要求儿子的 $a_j$ 和。

考虑增加状态。设 $d{p}_{i,j,0/1}$ 表示在 $i$ 的子树当中杀死了 $j$ 个节点，其中 $i$ 是否（$1/0$）被删除，所能对答案减少的最大值。这是一个 $0/1$ 背包问题，枚举当前节点的杀死节点数，然后对于所有儿子 $j$ 枚举其杀死节点数，最后转移（注意内外循环不能反，否则会导致同一个儿子 $j$ 的不同杀死数反复进入背包）。

直接转移是 $\mathcal{O}(n^3)$。不过令 $su{m}_i$ 表示 $i$ 在枚举儿子 $j$ 之前的子树和，$si{z}_j$ 表示 $j$ 的子树大小，转移时只枚举 $su{m}_i\times si{z}_j$，做扩散型，它的复杂度是 $\mathcal{O}(n^2)$ 的。

一定要注意，如果先把 $si{z}_j$ 加入到 $su{m}_i$ 后转移，做收集型，它的时间复杂度会退化。我就是因为这个原因导致 TLE 挂 $80$ 分。

正确转移的时间复杂度证明如下：

$$\begin{array}{rl}& =\sum _{i=1}^n\sum _{j=1}^{|so{n}_i|}\left(\sum _{k=1}^{j-1}si{z}_{so{n}_{i,k}}\right)\times si{z}_{si{z}_{i,j}}\\ & =\sum _{i=1}^n\sum _{1\le j<k\le |so{n}_i|}si{z}_{so{n}_{i,j}}\times si{z}_{so{n}_{i,k}}\end{array}$$

即求和对于 $i$，

$$si{z}_i^2-\sum _{j\in so{n}_i}si{z}_j^2$$

每个 $si{z}_i^2$ 都会加上一次，减去一次；除了 $si{z}_1$ 以外，因为没有节点的儿子是它。所以时间复杂度为 $\mathcal{O}\left(si{z}_1^2\right)$，即 $\mathcal{O}\left(n^2\right)$。

然后是我的那个算法，只是 $k$ 的枚举上界来到了 $j$ 而非 $j-1$，但是导致对于每个 $i$ 都额外增加了 $\mathcal{O}\left(\sum _{j\in so{n}_i}si{z}_j^2\right)$ 的时间复杂度，即最坏 $\mathcal{O}(n^3)$。

#include <fstream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2005;
 
ifstream cin("monster.in");
ofstream cout("monster.out");
 
LL a[kMaxN], dp[kMaxN], sub[kMaxN][kMaxN][2], siz[kMaxN], n, mx;
vector<LL> e[kMaxN];
 
void dfs(LL x, LL f) {
  LL sum = a[x];
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    dfs(i, x);
    dp[x] += dp[i];
    sum += a[i];
  }
  dp[x] += sum;
}
 
void solve(LL x, LL f) {
  siz[x] = 1;
  LL sum = a[x];
  for (LL i : e[x]) {
    if (i != f) {
      solve(i, x);
      sum += a[i];
    }
  }
  sub[x][1][1] = (x != 1) * a[x] + sum;  // 只删了自己
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    for (LL k = siz[x]; k >= 0; k--) {
      for (LL j = 0; j <= siz[i]; j++) {
        sub[x][k + j][0] = max(sub[x][k + j][0], sub[x][k][0] + max(sub[i][j][0], sub[i][j][1]));         // 自己不删，儿子删不删都不变
        sub[x][k + j][1] = max(sub[x][k + j][1], sub[x][k][1] + max(sub[i][j][0], sub[i][j][1] - a[i]));  // 自己删了，儿子没有删不影响，儿子删了就少一个儿子的贡献
      }
    }
    siz[x] += siz[i];
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  for (LL i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dfs(1, 0);
  solve(1, 0);
  cout << dp[1] << ' ';
  for (LL i = 1; i <= n; i++) {
    cout << dp[1] - max(sub[1][i][0], sub[1][i][1]) << ' ';
  }
  return 0;
}

集卡游戏

单调栈 线段树

我采用的是暴力。

暴力枚举在第一个数列当中选择的区间，那么对于后面的数列，有些位置是被禁用的，它们将数列分成了若干块，求每一块的和的最大值即可。时间复杂度 $\mathcal{O}(n^{2}m)$，直接通过 $40$ 分。