AtCoder Grand Contest 005 简要题解

比赛地址

STring

和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。
代码

Minimum Sum

单调栈板子题。
代码

Tree Restoring

首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。
设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下：

• 若 $d$ 为奇数，则应有

$$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d+1}{2}+1,d]\\ cnt_i=2,&i=\frac{d+1}{2}\\ cnt_i=0,&i\in[1,\frac{d-1}{2}] \end{cases} $$

• 若 $d$ 为偶数，则应有

$$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d}{2}+1,d]\\ cnt_i=1,&i=\frac{d}{2}\\ cnt_i=0,&i\in[1,\frac{d}{2}-1] \end{cases} $$
代码

~K Perm Counting

转化问题：给出一个 $n\times n$ 网格，其中 $(i,i\pm k)$ 是黑色的，其它格子是白色的，你需要选择 $n$ 个格子使得没有两个格子在同一行或同一列，求不选择黑色格子的方案数。
首先可以考虑容斥。设 $f_i$ 为选了至少 $i$ 个黑色格子的方案数，则答案为
$$ \sum_{i=0}^n(-1)^i(n-i)!f_i $$
考虑计算 $f_i$。容易发现一件事是每个黑格子最多只会与两个黑格子冲突。我们把每个黑格子向与它冲突的黑格子连边，则会形成若干条链。然后对于每条链 DP。设 $dp_{i,j,0/1}$ 表示前 $i$ 位选了 $j$ 个，当前没选/选的方案数。
这样子最后需要卷积合并；有一种简单的方法是将所有链连成一条，并在交接处特判转移，就不需要卷积合并了。
代码

Sugigma: The Showdown

考虑游戏怎样才可以无限进行。
假如先手能到达某个点 $u$，且第一棵树上存在一条边 $(u,v)$，使得第二棵树上 $u,v$ 的距离 $>2$，则游戏可以无限进行。先手只需要在 $u,v$ 之间反复横跳，则后手永远追不上先手。
否则，先手一定会走到能到达的在第二棵树上深度最大的点，然后等着被追上。
代码

Many Easy Problems

戳这里