## 矩阵最大值
#模拟
首先我们可以通过 $\mathcal O(nm)$ 的复杂度预处理出每一行和每一列的最大值，然后求出初始时一共有多少个满足条件的元素。
现在考虑修改对答案的影响。注意题目中加粗强调了修改之后的元素一定比原来更大，这也就代表着原先是最小值的元素再修改之后不会失去其地位，相当于提示我们仅需维护最大位置即可。
1. 修改后第 $x$ 行的最大值发生改变：需要减去第 $x$ 行原先的答案，更新最大值下标数组。
2. 修改后第 $y$ 列的最大值发生改变：需要减去第 $y$ 列原先的答案，更新最大值下标数组。
然后是对答案的增加。判断第 $x$ 行的最大位置是否为 $y$ 以及第 $y$ 列的最大位置是否为 $x$ 即可。然后你就会发现样例挂了。
仔细思考，如果第 $x$ 行和第 $y$ 列的最大位置没有发生任何改变，那么最后一步的增量是完全无需的，因为我们根本就没有减掉原来的贡献（如果你要减的话面临减重的问题，同样需要额外进行操作）。所以开个变量记录是否发生更改即可。
时间复杂度 $\mathcal O(nm+q)$。
```cpp
#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$ 谁在某个细胞的易感程度更高，可以令 $id_{i,a_{i,j}}=j$，这样即可 $\mathcal O(1)$ 判断。
枚举病毒 $i$ 后，再次枚举细胞 $j$，判断 $i$ 能否在任意一个 $j$ 上留下后代。具体来说，$i$ 的优先级要比在 $j$ 最开始时自带的 $j$ 病毒的优先级要高；其次，定义门槛值 ${} zrr_i {}$ 表示细胞 $i$ 对于所有其排列中 ${} j\ge zrr_i {}$ 的病毒 $a_j$ 都可能会感染掉 $i$，需要满足 $i$ 在 $j$ 的排名不能超过 $j$ 的门槛值，这样 $j$ 就不会被其它病毒感染了。
至于如何求 $zrr$ 数组，可以使用 $\mathcal O(n^3)$ 暴力计算。枚举病毒 $i$，枚举细胞 $j$ 和病毒 $k$，如果 $k$ 可以感染最开始的细胞 $j$，那么求 $\max id_{i,k}$ 即 $k$ 在 $i$ 中的排名，然后对这个最大值求 $\min$，得到可以感染 $i$ 的最小病毒，也就是门槛值。
```cpp
#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$，考虑将杀死的节点数量加入状态。设 $dp_{i,j}$ 表示在 $i$ 的子树当中杀死了 $j$ 个节点，可以对答案减少的最大值。但是会发现一个问题，既然我们杀死节点 $i$ 会对答案减少 $2\times a_i$（$i=1$ 除外）和 $\sum\limits_{j\in\operatorname{son}(i)}a_j$，那么如果 $i$ 和其儿子 $j$ 都被杀死了，儿子 $j$ 减少的 $a_i$ 不应该乘 $2$，因为 $i$ 已经杀死了不需要求儿子的 $a_j$ 和，但是如果不加当 $i$ 没被杀死时仍然需要求儿子的 $a_j$ 和。
考虑增加状态。设 $dp_{i,j,0/1}$ 表示在 $i$ 的子树当中杀死了 $j$ 个节点，其中 $i$ 是否（$1/0$）被删除，所能对答案减少的最大值。这是一个 $0/1$ 背包问题，枚举当前节点的杀死节点数，然后对于所有儿子 $j$ 枚举其杀死节点数，最后转移（注意内外循环不能反，否则会导致同一个儿子 $j$ 的不同杀死数反复进入背包）。
直接转移是 $\mathcal O(n^3)$。不过令 ${} sum_i {}$ 表示 $i$ 在枚举儿子 $j$ 之前的子树和，$siz_j$ 表示 $j$ 的子树大小，转移时只枚举 $sum_i\times siz_j$，做扩散型，它的复杂度是 $\mathcal O(n^2)$ 的。
一定要注意，如果先把 $siz_j$ 加入到 $sum_i$ 后转移，做收集型，它的时间复杂度会退化。我就是因为这个原因导致 TLE 挂 $80$ 分。
正确转移的时间复杂度证明如下：
$
\begin{aligned}
&\textcolor{white}{=}\sum_{i=1}^n\sum_{j=1}^{|son_i|}\left(\sum_{k=1}^{j-1}siz_{son_{i,k}}\right)\times siz_{siz_{i,j}} \\
&=\sum_{i=1}^n\sum_{1\le j<k\le |son_i|}siz_{son_{i,j}}\times siz_{son_{i,k}} \\
\end{aligned}
$
即求和对于 $i$，
$
siz_i^2-\sum_{j\in son_i}siz_{j}^2
$
每个 $siz_i^2$ 都会加上一次，减去一次；除了 $siz_1$ 以外，因为没有节点的儿子是它。所以时间复杂度为 $\mathcal O\left(siz_1^2\right)$，即 $\mathcal O\left(n^2\right)$。
然后是我的那个算法，只是 $k$ 的枚举上界来到了 $j$ 而非 $j-1$，但是导致对于每个 $i$ 都额外增加了 $\mathcal O\left(\sum\limits_{j\in son_i}siz_j^2\right)$ 的时间复杂度，即最坏 $\mathcal O(n^3)$。
```cpp
#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^2m)$，直接通过 $40$ 分。