模拟赛 32 题解

博弈论+剥叶子+思维+模拟+构造+背包+贪心+状压+动态规划

A.树树

手玩可以知道，先手一定是选一个叶子的父亲，那么后手肯定要堵叶子。

理由就是这样能尽快堵死后手，堵死的条件是至少两个叶子。

那么可以采用剥叶子的方法，一层一层向上找，这样留下的就是一条条链了。

不难发现挂在节点上的偶链是没有贡献的，那么只统计有大于 $1$ 个的奇链即可。

$n$ 为奇数时，先手必胜，因为堵不住。

B.网格

构造模拟，最终答案就是螺旋上升的走法。

注意特判一下位置就好了。

C.有手就行

考场切的一个题，但因为堆整体赋值而暴毙。

不难发现决策只有两种，一种是拿一个 $a$，一种是拿一对 $a+b$。

因为如果选择了当前不优的 $a$ ，那么目的一定是为了拿 $b$。

并且顺序是无关的，这就可以分别排序然后直接背包。

D.求余数

状压计数好题。

首先小于 $100$ 的质数有 $25$ 个，这启发我们状压。

但是直接状压显然复杂度爆炸，我们考虑更优雅的做法——根号分治。

把 $[1,m]$ 的数分成这样两类：一种只包含 $<\sqrt m$ 的质因子，一种还有更大的质因子。

根号分治，对于第一种，我们状压所含质因子的种类后，是可以取多个的（在保证没有交集）。

而第二种，我们一类中只能取一种，所以两种方案不是很相同。

但 $dp$ 的状态和转移一致，设 $f[i][S][j]$ 表示考虑了前 $i$ 类，质因子集合为 $x$，选了前 $j$ 个位置的方案数。

第一种是内部转移，枚举顺序是这样：

	for(int j=1;j<=P;j++) 
			for(int S=0;S<M;S++)
				if((S&a[x])==a[x])
					f[j][S]=pls(f[j][S],f[j-1][S^a[x]]);

而第二种要保证一类只选一个，所以要这样：

	for(int j=P;j>=1;j--)
		for(int S=0;S<M;S++)
			for(int k=0;k<rest[i].size();k++)
			{
				int x=rest[i][k];	
				if((S&a[x])==a[x])
					f[j][S]=pls(f[j][S],f[j-1][S^a[x]]);	
			}

差别就在转移顺序。