省流
快速出 \(4t\) 跳去看 F 一直在实现错误的方法结束比赛。
10.11
内含剧透,请vp后再来。
不是题解!!!!!!!
赛前
忘了干了什么了,总之什么也没干,处在低谷状态。
赛时
AB 快速模拟不谈。
C 题给了 \(n \leq 10\) 个点和一些边,没有重边和自环。要求给所有点涂上黑色或白色,有边相连的点不能是同一种颜色,问最少要删几条边。这道题很容易感觉如果变成树的形状会比较好想,于是试着画一下生成树,发现生成树的同一层之间的边就要删掉,进而可以想到奇数层和偶数层的中间的边都要删掉。所以只用枚举每个点的奇偶状态,然后把相同颜色的点之间的边删掉就行。其实我绕远路了,但仍旧是相对很快的搞定了这题,\(14min\) 解决。
D 题给了一个 \(2e5\) 的图,每个点都有一个颜色。两个人轮流走,从一个起点走 \(k\) 轮后如果在 A 颜色则 A 赢,否则 B 赢,问两个人绝顶聪明最后谁赢。很标准的博弈论,从已经确定的每个终点开始,往前退一步时如果这个人在这个点能走到的所有点中有一个点能使这个人赢,那么这个点是这个人的必胜点。往回退 \(k\) 轮看起点是谁的必胜点即可。
E 题看了一眼感觉要麻烦的分类讨论,于是看 F,感觉更可做一些。
F 题给定一个长度为 \(n \leq 60\) 的序列,要求两个相邻的数不能选,有多少种选法能使和为 \(m \leq 1e9\) 的倍数。因为 \(m\) 很大所以想着不能正常的 \(DP\),折半搜索也不是常见的 \(40\) 的范围,所以需要想别的。我在压力下搞了一个把 \(m\) 拆成质因子,然后再统计每个质因子的指数个数,实际上错的离谱因为是加不是乘,结果我后面一直在写这个玩意就比赛结束了。
赛后
下来后看题解,发现是折半搜索。因为两个相邻的数不能选,所以种类总数是斐波那契数列,而 \(Fib(30)\) 并没有那么大所以直接折半搜索就行。写完了之后交上去 TLE,改了一会发现是 \(unorderd_map\) 又被卡了,改成 \(map\) 就行,我之前一直以为只有 \(cf\) 会有人卡这个。
2025年10月12日