比赛地址

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

戳这里


版权属于:M_sea

本文链接:https://m-sea-blog.com/archives/agc005/

转载时须注明出处及本声明

最后修改:2020 年 01 月 22 日 10 : 15 PM