CVBB ACM Team

$n*m$个网格点，两人交替操作，每次连接一条长度为$1$的边，且连接后不能形成环，不能连就输，问先手的胜负。

因为长度为$1$的边不管横向还是纵向滑行都不会影响是否成环，所以能连接的边数必为$n*m-1$，奇数先手赢。

赛场上数错边数卡了一会

模拟

模拟

数组$a$生成单调栈$b$，已知$b$的其中$k$个位置上的值，构造出$a$。

从左往右构造$a$数组，将相邻两个要求$b_{p_i}, b_{p_{i+1}}$抽象为：使用$x=p_{i+1}-p_{i}$个数让单调栈的长度增加$y=b_{p_{i+1}}-b_{p_i}$。

分情况解决：

1. x<y，无解
2. x>y，填入y个数后，x变为x-y，y变为0，转为第三种情况
3. y⇐0，将当前单调栈前y+1个数增加x，此时后面x个数比这y+1个数小，因此将x个数从大到小放置，会剩下一个数，总长度增加(y-1)+1

区间加采用打标记，记录单调栈中每个数在原序列$a$中的位置即可，每次更新。

两球体积交，积分一下

将$n$个区间分为$k$组，每组的交不能为空，最大化$k$组区间交的和。

如果区间$i$包含$j$，那么要么$i$自己一组，要么对答案没有影响，将所有包含其他区间的区间分开考虑。

剩下的区间可以用dp做，$dp_{i,j}$表示前$i$个区间分为$j$组的最大值，决策单调。

最后循环枚举$i$个大区间自己分组，加上其他区间分为$k-i$组的最大值，选择和最大的$i$。

赛场上没想到单独处理大区间，发现没有单调性，就不会了

按更新的权值从大到小枚举，每个点记录上次更新的时间和上上次更新的时间，考虑在时间$i$上被更新的点。

按度数大小分类，对于度数小于$sqrt(m)$的点，直接从周围的点获取答案，对于度数大于$sqrt(m)$的点，在更新其他点的时候更新(每个点记录它连了哪些大点)

赛场上某人读错题否认了队友的正解