专栏文章

2025 蓝桥杯 C++ A 组省赛游记

CCuiZhenhang
生活·游记参与者 7已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@mhze686q
此快照首次捕获于
2025/11/15 05:50
3 个月前
此快照最后确认于
2025/12/03 14:43
3 个月前
查看原文

致谢

首先拜谢 minstdfx 的文章，提前让我知道最后一题也坠机了（悲。

赛前日

没怎么准备，仅仅周三、周四抽了 2h + 2h 的时间打了去年的比赛。
因数计数 没想到容斥；成绩统计 没想到二分答案，其它都会写。
然后写挂了一道半 qwq。
一个是忘了一行修改体力挂整道题，另一个是 stderr 输出太多爆了 output limit 挂半道。
于是总结：稳住，能赢。
周四下午熟悉一下考场，但是登不了系统，无所谓了。

比赛当日

要求 8:30 到考场绝对是今天最大的考验！
凌晨 1 点，定好从 7:00 到 8:30 的 4 个闹钟后，安详地睡去。
幸运地 7:12 醒来，本学期起床最早的一天。
磨磨蹭蹭出了门，却立刻被寒风推回寝室，把夏装换成了春秋装。
眼前的风甚是喧嚣——狂风把山脚的碎屑吹的满天飞舞，但我无法为它睁大双眼。
策略为顺序开题，有时间再对拍。

解题

A. 寻找质数

略。
答案是我梦到的。（你信不？）

B. 黑白棋

考虑到蓝桥杯相当暴力，于是先看棋盘大小。共 36 个格子，暴力为 2362^{36}，稍有点多。
然后注意到可以状态压缩，立刻敲代码得每行只有约 10 种情况，六次方可以接受。
于是枚举并判断得到答案。耗时约半小时。
离开前再次肉眼检验了合法性。
赛后发现，别人怎么都是当成数独游戏做的啊！还比我快得多呜呜呜。

C. 抽奖

对这道题简单的程度不敢相信，担心自己是不是看错了。
截止目前（比赛当日 17:00）也不敢相信。
解法略。
未验证（这还能写错的话，根本救不了）。

D. 红黑树

众所周知，标题越高级，题目越简单。
nin_i 居然甚至只给到 3030，不可思议。
解法略。
验证了前 4 层的所有结点，均正确（如果 RED、BLACK 没写错的话）。

E. 黑客

又是我最不擅长的求方案数，甚至不是 dp 而是组合数学。
简单分析得答案仅仅是类似 ∑(∑ci)!∏ci!⋅ci!ci′!\sum{ \dfrac{ (\sum c_i)! }{ \prod{c_i !} } \cdot \dfrac{ c_i! }{ c_i'! } } 的东西。
预处理一下 x!x! 和 1x!\dfrac{1}{x!}，使用 map 求出现次数 cic_i，O(nmlog⁡(nm))O(nm \log (nm)) 完成。
因为方案数目增长过快，所有没有验证这道题。

F. 好串的数目

注意到好串的子串也是好串。因此考虑对于所有左端点，寻找其最大的右端点。
找第二个连续非递减子串的右端点即可。
时间复杂度 O(n)O(n)。
对拍程序为 O(n3)O(n^3) 暴力枚举，先得到所有子串 [l,r][l, r] 是否为连续非递减子串。然后枚举 l≤mid<rl \le mid \lt r 计数。

G. 地雷阵

易得可转化为极坐标角度 θ\theta 范围，然后合并区间，时间复杂度 O(nlog⁡n)O(n \log n)。
我的踩坑点：
  • arctan⁡yx\arctan\dfrac{y}{x}，因为很容易用 int 保存 x,yx, y，所以 atan(y / x) 也要先转成 double（第二个样例发现）。
  • 合并区间 [li,ri][l_i, r_i] 成 [L,R][L, R] 时，我按 lil_i 排序后，R←max⁡(R,ri)R \gets \max (R, r_i) 错写成了 R←riR \gets r_i（对拍时发现）。
然后就和对拍一样了。
对拍程序将第一象限分为 1000010000 份枚举 θ\theta，逐个判断是否与圆的极坐标角度范围重合。

H. 扫地机器人

因为连通，所以是一个基环树。
dfs 找环，然后考虑不同的路径即可（说的轻松）。
于是我只考虑了起点和终点不在同一棵子树上的情况 qwq。
再次拜谢 minstdfx 的文章，提前让我知道最后一题也坠机了（悲。
其实我对拍了的。
但是，因为 vector 存边不方便记录边是否走过，所以我思考了一下，认为环上点的度只可能是 22 或 33，达不到允许重复走过的 44……
于是我的对拍其实也写错了，hhh。
但是对别人来，可能说有一个好消息——注意到我甚至没考虑不经过环的情况，而暴力对拍程序可以正确处理这种情况。
我的对拍数据是这样生成的：
  1. 选定 nn，测试了 500500 和 20002000 的情况。
  2. tit_i 是随机的 50%50\% 的 11 和 50%50\% 的 00。
  3. 选定不同的两个结点 p,qp, q，作为额外的一条边。
  4. 对于每个结点 uu，把它和 1∼u−11 \sim u-1 中随机一个点相连。（这条边要与 p,qp, q 不同。）
  5. 打乱结点编号。
经过约 3030 次测试（我怎么测的这么少 QAQ），对拍均成功。
这意味着，如果考虑到了经过整个环，但没有考虑到不经过环，那么还是很有可能测不出来的，不会挂多少分。
而我……哎。

总结

大家也都说这次出的简单，所以我可能要寄了。
但愿还能进国赛吧，给孩子多点补贴（）

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...