Day8

【日历游戏】
题意:对一个日期有两种操作:1.跳到日历上的下一天。2.跳到日历上的下个月的同一天(如果不存在,则不能这么做)。询问先手是否必胜。
博弈论+记忆化搜索,对于先手必胜的日期,它的下一天或下个月同一天先手必败。对于先手必败的日期,其后一天或下个月先手必胜。
【二叉查找树】
题意:求将n个数加入二叉树,并使其高度恰好为h的方案数。
考虑树形dp。设f[x][h]表示有x个节点的子树,并以x为父节点,高度为h的方案数,设g[x][h]表示有x个节点的子树,并以x为父节点,高度小于等于h的方案数。
那么f[x][h] = (f[x - 1][h - 1]*f[n - x][h - 1] - g[x - 1][h - 2] * g[n - x][h - 2]) * C(x - 1, n - 1);
由于f[x - 1]的相乘会计算重复的,所以要减去重复计算的,最后的排列组合是计算将剩下的数放入x的子树中的方案数。
【我们爱数数】
题意:规定第i人坐在i - 1、i、i + 1的位置上是开心的,询问使>=k的人开心的方案数。
DFS + DP + 容斥。令f[i][j][s]表示1-i位子有j个人已经坐下且这j个人一定开心,s表示i和i+1是否坐下。首先暴力枚举初始状态,即1、2位置是否坐人,坐的人是谁。
那么f[i][j][s >> 1 ] += f[i - 1][j][s];
f[i][j][(s | (1 << d)) >> 1] += f[i - 1][j - 1][s](d=0,1,2,分别表示第i-1,i,i+1个人坐第i个位置)。
最后判断一下初态和终态是否矛盾。
设ans[n][j]表示j个人一定开心的方案(存在重复)。ans[n][j] = f[n][j][s] * (n - j)!。
因为ans中剩下的n - j不一定是不开心的,所以在统计中会出现重复的状态。
最后用容斥来求方案数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注