BZOJ1413[ZJOI2009]取石子游戏

取石子游戏

Solution

由于本人水平极低,所以觉得此题难死了。

通过看题解不难发现,对于一段区间[L,R],若L+1R每堆石子个数确定,那么使得这段区间上先手必败的a[l]有且只有一个。

证明非常的容易。首先假设没有先手必败的a[L],那么所有的必胜态都会到一个必胜态,显然是不可能的。如果有\geq 2个必败态,考虑其中任意两个x,y,x>y,那么先手显然可以把x取成y,那么x就是一个必胜态。矛盾。

于是,我们定义left[i][j]表示在[L,R]区间左边添多少个变成一个必败态,right[i][j]表示在右边添多少个。那么答案就是left[2][n]!=a[1]。现在考虑如何求left[l][r]。设L=left[l][r-1],R=right[l][r-1],X=a[r]我们可以分以下几种情况讨论。

继续阅读

CF814E An unavoidable detour for home

An unavoidable detour for home

Solution

由最短路唯一,不难发现以下性质:

1、原图可以通过对于1号点的最短路长度分层,成一棵树的形式,每一层的最短路长度相同。

2、剩下的边只能在树的同层内的点加。

3、由于要求对于i>jdis_i>dis_j,所以每一层是一段区间。

于是,我们就可以DP了。显然有一个暴力的做法,f[i][pre_1][pre_2][now_1][now_2]表示上一层剩下的度数为1的点有pre_1个,度数为2的点有pre_2个。这一层的对应分别有now_1,now_2个。转移讨论一下i号点的连边情况。当pre_1=pre_2=0时,这一层就填完了,该填到下一层。

显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为2的点的方案数要提前除2

同时注意到,数据范围只有50,所以好写n^5暴力就可以愉快通过了。真好写