2025 蓝桥杯 C++ A 组省赛游记
CuiZhenhang
·
·
生活·游记
致谢
首先拜谢 minstdfx 的文章，提前让我知道最后一题也坠机了（悲。
赛前日
没怎么准备，仅仅周三、周四抽了 2h + 2h 的时间打了去年的比赛。\
因数计数 没想到容斥；成绩统计 没想到二分答案，其它都会写。\
然后写挂了一道半 qwq。\
一个是忘了一行修改体力挂整道题，另一个是 stderr 输出太多爆了 output limit 挂半道。
于是总结：稳住，能赢。
周四下午熟悉一下考场，但是登不了系统，无所谓了。
比赛当日
要求 8:30 到考场绝对是今天最大的考验！
凌晨 1 点，定好从 7:00 到 8:30 的 4 个闹钟后，安详地睡去。
幸运地 7:12 醒来，本学期起床最早的一天。
磨磨蹭蹭出了门，却立刻被寒风推回寝室，把夏装换成了春秋装。
眼前的风甚是喧嚣——狂风把山脚的碎屑吹的满天飞舞，但我无法为它睁大双眼。
策略为顺序开题，有时间再对拍。
解题
A. 寻找质数
略。
答案是我梦到的。（你信不？）
B. 黑白棋
考虑到蓝桥杯相当暴力，于是先看棋盘大小。共 36 个格子，暴力为 2^{36}，稍有点多。
然后注意到可以状态压缩，立刻敲代码得每行只有约 10 种情况，六次方可以接受。\
于是枚举并判断得到答案。耗时约半小时。
离开前再次肉眼检验了合法性。
赛后发现，别人怎么都是当成数独游戏做的啊！还比我快得多呜呜呜。
C. 抽奖
对这道题简单的程度不敢相信，担心自己是不是看错了。\
截止目前（比赛当日 17:00）也不敢相信。
解法略。
未验证（这还能写错的话，根本救不了）。
D. 红黑树
众所周知，标题越高级，题目越简单。
解法略。
验证了前 4 层的所有结点，均正确（如果 `RED`、`BLACK` 没写错的话）。
### [E. 黑客](https://www.luogu.com.cn/problem/P12142)
又是我最不擅长的求方案数，甚至不是 dp 而是组合数学。
简单分析得答案仅仅是类似 $\sum{ \dfrac{ (\sum c_i)! }{ \prod{c_i !} } \cdot \dfrac{ c_i! }{ c_i'! } }$ 的东西。
预处理一下 $x!$ 和 $\dfrac{1}{x!}$，使用 `map` 求出现次数 $c_i$，$O(nm \log (nm))$ 完成。
因为方案数目增长过快，所有没有验证这道题。
### [F. 好串的数目](https://www.luogu.com.cn/problem/P12143)
注意到好串的子串也是好串。因此考虑对于所有左端点，寻找其最大的右端点。
找第二个连续非递减子串的右端点即可。
时间复杂度 $O(n)$。
对拍程序为 $O(n^3)$ 暴力枚举，先得到所有子串 $[l, r]$ 是否为连续非递减子串。然后枚举 $l \le mid \lt r$ 计数。
### [G. 地雷阵](https://www.luogu.com.cn/problem/P12144)
易得可转化为极坐标角度 $\theta$ 范围，然后合并区间，时间复杂度 $O(n \log n)$。
我的踩坑点：
- $\arctan\dfrac{y}{x}$，因为很容易用 `int` 保存 $x, y$，所以 `atan(y / x)` 也要先转成 `double`（第二个样例发现）。
- 合并区间 $[l_i, r_i]$ 成 $[L, R]$ 时，我按 $l_i$ 排序后，$R \gets \max (R, r_i)$ 错写成了 $R \gets r_i$（对拍时发现）。
然后就和对拍一样了。
对拍程序将第一象限分为 $10000$ 份枚举 $\theta$，逐个判断是否与圆的极坐标角度范围重合。
### [H. 扫地机器人](https://www.luogu.com.cn/problem/P12145)
因为连通，所以是一个基环树。
dfs 找环，然后考虑不同的路径即可（说的轻松）。
于是我只考虑了起点和终点不在同一棵子树上的情况 qwq。
再次拜谢 [minstdfx 的文章](https://www.luogu.com.cn/article/x5cbrqlv "蓝桥杯小丑坠机实况")，提前让我知道最后一题也坠机了（悲。
其实我对拍了的。\
但是，因为 `vector` 存边不方便记录边是否走过，所以我思考了一下，认为环上点的度只可能是 $2$ 或 $3$，达不到允许重复走过的 $4$……\
于是我的对拍其实也写错了，hhh。
但是对别人来，可能说有一个好消息——注意到我甚至没考虑不经过环的情况，而暴力对拍程序可以正确处理这种情况。
我的对拍数据是这样生成的：
1. 选定 $n$，测试了 $500$ 和 $2000$ 的情况。
2. $t_i$ 是随机的 $50\%$ 的 $1$ 和 $50\%$ 的 $0$。
3. 选定不同的两个结点 $p, q$，作为额外的一条边。
4. 对于每个结点 $u$，把它和 $1 \sim u-1$ 中随机一个点相连。（这条边要与 $p, q$ 不同。）
5. 打乱结点编号。
经过约 $30$ 次测试（我怎么测的这么少 QAQ），对拍均成功。
这意味着，**如果考虑到了经过整个环**，但没有考虑到不经过环，那么还是很有可能测不出来的，不会挂多少分。
而我……哎。
## 总结
大家也都说这次出的简单，所以我可能要寄了。
但愿还能进国赛吧，给孩子多点补贴（）