【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:
继续阅读【纪中】Day10+

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不一定是不开心的,所以在统计中会出现重复的状态。
最后用容斥来求方案数。