给一张 $N\times N$ 的围棋棋盘，初始时只有黑子没有白子，然后黑方一直不动，白方一直下，问最多能吃掉多少黑子

数据范围 $N\le 1000$

围棋基本规则看题面，这里不讲

黑子被吃的话一定是一个联通块一起被吃，这里称一个完整的联通块黑子为黑块，除了占满整个棋盘的黑块，每个黑块一定都是能被吃的，即每个黑块都有着一个吃掉它所需的白子包围集，稍微思考下可以发现随着棋盘上部分黑块被吃，其余黑块的包围集是不会变的

类似黑块，称空地的联通块为空块，空块的意义在于，只要不填满空块，这个空块内可以随意下白子，如果要填满空块的话，则会发动一次自杀式攻击

总结一下：

• 一个黑块不能被吃当且仅当这个黑块的包围集需要占满 2 个及以上的空块

• 另外一个空块如果因为部分黑子被吃而扩大，它将不再限制那些本来需要占满它的黑块，因为黑块的包围集是不会变的

用并查集处理出所有黑块与空块，并处理出每个黑块受哪些空块限制，然后在上面进行跑拓扑，一个黑块被吃时，对所有与其相邻的空块，解放原本被这些空块限制的黑块（限制数-1）。

给一张 $N$ 点的图，每个点的点权$a_i$在 $[L,R]$ 内随机生成，在上面连边$(i,j)$ 需要花费$\gcd(a_i,a_j)$，求最小生成树。

数据范围 $N\le 2\times 10^5$

当 $N$ 大了之后答案基本就是 $N-1$ 了，需要特判 $L=R$ 的随机数据

$N$ 小的时候直接$N^2$条边暴力求就行

对一棵树上的点进行黑白染色，要求黑点的所有子树均是黑点。

现在给一个$K$，要求构造出一颗 $N\le 10^5$ 的树满足其染色方案正好为 $K$ 种

数据范围 $K\le 10^{18}$

考虑两种构造方式

• 对于子树 $i$，给其连两个儿子，分别为一个单点和另一棵子树 $j$，考虑 $i$ 分别为黑白点，可得染色方案 $f_i=2\times f_j+1$。

• 对于 $i$，单挂一个子树 $j$ ，则可得 $f_i=f_j+1$

使用方法2将 $K$ 处理成奇数后再使用方式1，重复进行就可以构造出来

给 $N$ 个串，问其中有多少对串 $(i,j)$ 满足 将 $s_i$ 与 $s_j$ 拼接后得到一个长度为偶数，前半后半完全一致的串（如 $aabb$）

数据范围 $N\le 4\times 10^5, \sum|s_i|\le 4\times 10^5$

满足条件的 $s_i$ 和 $s_j$ 有两种情况：

• $s_i=s_j$
• $s_i$ 存在长度为 $k$ 的，完全相同的前后缀，并且去掉前后缀后剩下的中间部分与 $s_j$ 相等，即 $s_i=a+b+c,a=c,b=s_j$

因此将所有串按长度排序，对每个串枚举前后缀，字符串比较以及计数可以用Hash实现。

在 $[1,N]$ 上每个整点有一个人，且有 $M$ 个基站分布在轴上，基站 $i$ 有 $p_i$ 的概率被连上，每个人会按照先近后远，先左后右的顺序连接基站，如果全部连不上则从头再连一遍，每个基站的贡献为连接人数的平方，求期望和

数据范围 $M\le N\le 10^6$

方便起见可以将没有基站的点看作 $p_i=0$ 的基站

先考虑重连的影响

用 $F_x$ 表示考虑连接到基站 $x$ 的概率，$F_x’$ 表示第一轮就连上的概率， $Z$ 表示一轮里全部没连上的概率，则有：

$$F_x'=p_x\prod\limits_{y比x先连}(1-p_y) \\ Z=\prod\limits_{i=1}^n (1-p_i) \\ \begin{align} F_x &= F_x' + F_x'\times Z + F_x'\times Z^2 + F_x'\times Z^3 + \cdots \\ &= F_x'\times (1+Z+Z^2+Z^3+\cdots) \\ &= F_x'\times \frac{1}{1-Z} \\ \end{align}$$

先不考虑平方，求一下某个基站 $x$ 的连接人数期望 $G_x$

$$\begin{align} G_x &=\sum\limits_{i=1}^n F_x \\ &=\frac{p_x}{1-Z}\times \sum\limits_{i=1}^n \prod\limits_{y比x先连}(1-p_y) \end{align}$$

式子左边都是常数，考虑式子的右边怎么计算。

左右分开计算，用 $L_x$ 表示只考虑 $x$ 左边的人，$R_x$ 类似，即：

$$L_x + 1 + R_x = \sum\limits_{i=1}^n \prod\limits_{y比x先连}(1-p_y)$$

考虑计算 $L_x$，从 $L_{x-2}$ 转移到 $L_x$ 时，基站右移2格，前面整体右移1格，有：

$$\sum\limits_{i=2}^{x-2} \prod(1-p_y)=(1-p_{x-2})\times (1-p_{x-1})\times \sum\limits_{i=1}^{x-3} \prod(1-p_y)$$

再补上 $i=1$ 和 $i=x-1$ 这两个点即可，因此有转移式：

$$\begin{align} L_i &= L_{i-2} \times (1-p_{x-2})\times (1-p_{x-1}) \\ &+ (1-p_{x-1})\times (1-p_{x-2}) \\ &+ \prod\limits_{j=1}^{i-1}(1-p_j) \end{align}$$

计算 $R_i$ 类似，到这里就算出了所有基站的 $G_i$，接下来考虑对每个基站处理平方期望 $H_i$

这个模型相当于给 $n$ 个 $0/1$ 随机变量 $a_i$，变量 $a_i$ 为 1 的概率为 $p_i$，求 $E((\sum a_i)^2)$

期望的基本性质：

如果 $X, Y$ 独立，则有 $E(XY)=E(X)\times E(Y)$ 和 $E(X+Y)=E(X)+E(Y)$

$$\begin{align} E((\sum a_i)^2) &= E(\sum\limits_{ij}a_i\times a_j) \\ &= \sum\limits_{ij} E(a_i\times a_j) \\ &= \sum\limits_{i\ne j} E(a_i)\times E(a_j) + \sum\limits_i E(a_i^2) \\ &= \sum\limits_{i\ne j} p_i\times p_j + \sum\limits_i p_i \end{align}$$

本题的平方期望则类似转化，用 $F_{i,x}$ 表示第 $i$ 个人连接到基站 $x$ 的概率：

$$\begin{align} H_x &= \sum\limits_{i\ne j} F_{i,x} \times F_{j,x} + \sum\limits_{i=1}^{n} F_{i,x} \\ &= (\sum\limits_{i=1}^n F_{i,x})^2 - \sum\limits_{i=1}^n F_{i,x}^2 + \sum\limits_{i=1}^n F_{i,x} \\ &= G_x^2 - \sum\limits_{i=1}^n F_{i,x}^2 + G_x \end{align}$$

其中 $G_x$ 是已经求出的，而剩下的 $\sum\limits_{i=1}^n F_{i,x}^2$ 实际上有：

$$\sum\limits_{i=1}^n F_{i,x}^2= \frac{p_x^2}{(1-Z)^2}\times \sum\limits_{i=1}^n \prod\limits_{y比x先连}(1-p_y)^2$$

用和 $G_x$ 类似的转移方式计算

给一个$N\times M$ 的01矩阵$C$，构造两个相同大小的01矩阵 $A$ 和 $B$，要求 $C_{ij}=A_{ij}\&B_{ij}$，且$AB$ 矩阵上的所有1成联通块

保证 $C$ 的边界均为0，$N,M\le 500$

$A$ 的边界全染为1，内部的子矩阵奇数行全染为1

$B$ 的边界全为0，内部的子矩阵偶数行全染为1