题解:考虑限制条件在什么时候会生效,那么肯定是 $n$ 个班级只剩下某个班级既有学生没喝奶茶,又有奶茶没被喝掉.枚举每一个班作为这个班级的可能性,再算上一般情况.
题解:考虑限制条件在什么时候会生效,那么肯定是 $n$ 个班级只剩下某个班级既有学生没喝奶茶,又有奶茶没被喝掉.枚举每一个班作为这个班级的可能性,再加上一般情况就是答案.
题意:判断一个图是否可以是正方体的展开图.
题解:首先根据面积算出可能是正方体的边长,再以每一个方格作为正方体上特定的一个位置尝试把图铺在正方体上.按 dfs 序模拟在正方体上移动的过程,注意方向.如果没有冲突就可以是正方体的展开图.
剩下的,奇数行从大到小走偶数位置,偶数行从小到大走奇数位置就好了.
Problem E
题意:求字符串中有多少子串满足均分成 $k$ 段以后,每一个子段都相同.
所以我们只要找到所有的长度 $\ge kx$ 的循环串即可.
向右最多的拓展长度,显然就是求 $lcp(ii+x)$ ,向左的就是在反串上类似的求.
Problem F
题意:在一棵树上,A 决定棋子的初始位置,两个玩家轮流移动棋子在树上移动且不能经过走过的点,玩家 A 把棋子移动到第 $i$ 个点时获得 $a_i$ 的权值,B 移动时则会获得 $b_i$ 的权值,若两名玩家都选择最佳策略,求两名玩家获得权值的差.
题解:如果这是一个 DAG,我们可以在 $O(n*k)$ 的时间里算出答案.但由于 $k$ 很小,我们发现,如果我们每次都对所有点随机排序,那么假设最短链存在,最短链在这个图上是顺序的概率是 $\frac{1}{720}$,我们只要随机排序 $3000$ 次就基本能保证最短链上的点一定在其中某次是顺序排列的,而如果是顺序排列,那么 dp 一定能给出正确答案.所以对所有点的顺序随机排列 $3000$ 次,把其中所有的逆序边删除,计算每一次的答案,对所有答案取最小值就是最终答案.
Problem I
题意:给出两个平面上的矩形,求矩形将平面分成了多少区域.
题解:开始的时候尝试枚举情况,但是枚举情况太复杂了,所以放弃,转为离散化 BFS.
Problem J
温暖的签到.靠着开题直觉和手速,抢了一血.