2025蓝桥杯省A游记

· · 生活·游记

博客

这场真简单吧，为什么我到处挂分……

早上七点半就醒了，赖了会儿床，感觉要饿晕了才起来，结果下楼发现食堂周六不开门，真要晕过去了……

小卖铺拿了个面包往机房赶。

8:55 左右进机房，快速配了下 devc++，然后把模板、对拍器、随机数敲了。

9:02 左右能下载题面，上来看到一道找素数，心里一喜，哐哐写完直接拿下。

B 题棋盘，和去年的五子棋对弈基本一摸一样的写法，心里又是一喜，9:33 拿下两题。

写完 B 开始啃面包，顺便读一下后面的题面。看到貌似有道计算几何，直接乐开花了。

C 题读完发现直接模拟就做完了，又是直接拿下。

D 题给了一棵完全二叉树，一眼看上去就和二进制关系密切。联想到线段树的左儿子是 p<<1、右儿子是 p<<1|1，发现可以从高到低枚举二进制位，如果是 1 说明是向右下走，颜色反转，否则颜色不变。做法直接就瞪出来了，为了求稳再写了个 dfs 把 n\leq10 的情况全部求出来对拍了一下。10:09 拿下四题。

E 题上来一眼感觉稍微有点强度。然后理了下思路大概分成两步，先从所有数里找到两个相乘等于 n\times m，然后剩下的数字做多重排列。第一步显然需要特判两数相同的情况。第二步也是套路，要么组合数 DP，要么直接套公式 \dfrac{n!}{\prod_ip_i!}，详见 AT_abc358_e。我选了一个复杂度低的公式做法（另外一种貌似不可行，但我场上想都没想），预处理了一下组合数，多出来的两个数用先乘 c_x! 后除 (c_x-1)! 的方式处理，稍微写写就过样例了。然后写了个枚举全排列加 std::set 去重的暴力，11:46 过拍，拿下。

F 题不想读。直接跳去做 G 计算几何，大概是要求 [0,\dfrac{\pi}{2}] 的范围内有哪些极角区间，向外引射线会和给定的圆相交。显然可以通过 \arctan\dfrac{y}{x}\pm\arcsin\dfrac{r}{\sqrt{x^2+y^2}} 的方式预处理出每个圆的极角区间，然后就是区间合并，先按左端点排序，维护当前区间的左右端点，如果下一个区间的左端点落在当前区间内，则更新右端点，否则将当前区间计入答案，把左端点更新为下一个区间的起点。11:09 写完然后过了样例。

H 一眼基环树，先缩点再做。题面里说没有重边和自环但点数 n 却可以取到 1，有点不严谨，谴责一下。当时读完题感觉非常 ez，再加上前面做得太顺了，放松了警惕，直接想缩完点之后选两条链就做完了（其实是错的）。然后开始写代码，写完代码对拍，找环和 std 一直来回错，最后我直接手动生成了几组数据然后发现暴力错光了，然后直接就交了。12:20，自我感觉非常良好。

回去看 F，心里已经做好被牢住的预期了。读完题第一感觉可能是个 DP，先做一段非递减连续，再把两段合并起来搞个容斥什么的，然后发现想复杂了，根本不需要 DP，连续不降段内的贡献是 \dfrac{len(len+1)}{2}，相邻两段合并直接 len_1\times len_2 就做完了。搞笑的是，由于我忘了 substr 这个函数怎么用，我写暴力的时间甚至比写正解的时间还要长，暴力写完开拍，直接就过了。12:40 感觉自己 AK 了。

然后想着回去把 H 的暴力写了对拍一下，结果突然发现自己的做法错光了。看着只剩下 20 分钟的时间突然感觉心里一阵绝望，最后一段时间本来想写个环上的前缀和，求出“基环树直径”的，但因为太慌了也不知道在写点什么东西。

出来和别人嘴题，问了下第一题多少，其他人都说是 17609，但我很清楚地记得自己写的是 175 几几，直接就毁了……

感觉总体发挥还算正常吧，因为题目有点简单，这种没有思维难度的题（再加上计算几何）又是我的优势区间。但为数不多的挂分机会还是被我抓住了，实在是有点不当人了……