【这个标题被教练要求删掉了】|| 联合省选 2026 游记

· · 生活·游记

同样推荐在 cnblogs 阅读。那里可能会更新一些后续。

来玩的。

Day -inf

被教练告知要去省选，不过重在参与。

重在参与重在参与重在参与重在参与重在参与。

Day -(?+?) ~ -?

然后从 NOIP 2025 结束到省选，一共打了 3 场 abc，做了一个绿题三个蓝题。OI 课要不是在 whk 要不是在打摆，不想学 OI 喵喵喵。

Day -1

周五中午出发，耽误了点儿 whk，不过新课都不是很难，应该看看课本就能看懂的。而且这两天要讲试卷来着。

车上睡睡睡。

没住 NOIP 住的全寄酒店，--rp。

下午完全不想复习，去打摆了，刷刷 B 站水水群然后吃晚饭（点的外卖），然后就去试机了。

SD-010，看起来像是随机摇号？

试机写了个传统艺能线性筛素数，发现能跑 5e7 左右，比 NOIP 的机子强了好多。

对面的右边的右边是 wmh 巨手子，膜拜了。（左右以我的视角为准）

晚上继续打摆。

Day 0

我发现每个宾馆的早饭自助都有蛋炒饭、油条、鸡米花，前两个都很合理，但是为什么都有鸡米花呢？

day1

我记得压缩包密码中有 AK 子串。

读题。A 怎么一上来就是期望。BC 题面简短易懂好评。不过怎么两个构造 /jk

开 A，看了看大样例发现性质 A 全输出 0，推了下发现是对的，于是第一个 8pts 到手了。

是 dp 吗？令 f_{u,i} 为子树 u 重链长度 i 的概率？令 f_u 为子树 u 重链长度期望？觉得很离谱，甚至不知道转移该长什么样子，于是果断扔掉了。

然后发现 u \leadsto 1 的轻边数量其实就是 u \leadsto 1 这些点中没被选作重儿子的数量。这似乎有点作用，可以把贡献拆到每个点上了，点 u 的贡献就是 p_u \times siz_u，其中 p_u 表示 u 没被选作重儿子的概率，siz_u 表示 u 的子树大小。

我算概率 \frac {l_i} {\sum l_j} 的时候可以用 l_i 的期望去算吗？不知道，不过这看起来很合理的样子，推了推发现样例 #1 的前一半是可以过的，于是去写了，大概求个 f_u 表示 u 子树中包含 u 的重链长度期望，然后 f 就可以 dp 出来，贡献直接套公式算。

然后发现样例 #1 的后一半过不了，但是我不知道是我写错了还是做法假了，于是写了个代码枚举了下 549034400 到底是多少，当时算出来好像是个 20 分之几的样子，总之是我做法假了。

不会了不管了，安心去写暴力吧。

（怎么这么热，于是把羽绒服脱了，没地方放就放地上了。）

2h。开 B。观察大样例没有任何发现。 我认为我根本不可能在省选中过题，所以还是直接想暴力和特殊性质吧。 $n \le 15$ 的暴力足足 15pts，太良心了。 性质 B 的意思是只有长度 $\le n$ 的全 $0$ 串可以产生贡献，那么答案一定是类似 $000 \ldots 000100 \ldots 00010$ 状物，就是由几个 $1$ 分隔开的若干个全 $0$ 串拼到一起（根据大样例这是正确的）。同时显然只有一个长度 $\ge n$ 的全 $0$ 串，剩下几个全 $0$ 串满足长度为 $x$ 的串会产生 $v_x = x(x+1)/2$ 的贡献，拥有 $w_x = x+1$ 的代价（因为要拼一个 $1$ 上去）。 那么是不是可以直接贪心？发现不行，比如说 $n=6,k=26$ 的时候，如果不考虑 $\ge n$ 的全 $0$ 串，那么取 $x = 5,4,1$ 最优，但贪心就会选成 $x = 6,2,1,1$。所以这应该是个能重复选的背包，这么做就对了，同时因为要考虑那个长度 $\ge n$ 的全 $0$ 串，需要有一个 $v_0 = n-1$，$w_0 = 1$ 的物品。这样直接背包就可以了吧，构造就是记录历史路径，写写写，过样例了。 然后看性质 C，发现意思是一段长度为 $n$ 的全 $1$ 串（起始位置为 $i$）会导致子串 $[i,i+n-1] , [i,i+n] , \ldots , [i,m]$ 都不会产生贡献，也就是添加这个全 $1$ 串之后，原贡献和会减去 $m-(i+n-1)+1$。这样似乎就可做了，注意到长度为 $m$ 的串最大贡献为 $m(m+1)/2-1$（$-1$ 是因为要在结尾包含串 $s$，会导致子串 $[m-n+1,n]$ 不产生贡献），所以直接按照这个枚举一个最小的 $m$ 就可以了。构造的话因为不涉及长度变化，直接贪心地把长度为 $n$ 的子串换成全 $1$ 串即可，两段全 $1$ 串可以重叠并不会影响答案。 写写写过样例了。 然后忽然发现我似乎是假的，因为可能会出现以 $i$ 为起始位置放了一个全 $1$ 串，又以 $[i+1,i+m]$ 中的某个位置 $j$ 为起始位置放了一个全 $1$ 串的情况，这样就导致 $[i,j]$ 全变成全 $1$ 串的起始位置了，那就不对了啊！但是考虑到了我也不会改呀，而且现在只剩 1h 多一点了，不管了开 C 吧。只能祈祷数据和大样例一样水了。 观察大样例发现性质 D 全是 Yes，果断特判掉。如果对的话能有足足 10pts？这是真的吗？ $n,m \le 16$ 依然二进制枚举，8pts。 $m=1$ 就是判一下 $\bigoplus a_i$ 与 $b_1$ 是否相等就可以了，构造随便。 后面就都不会了，乱搞一下判了个 $\bigoplus a_i = \bigoplus b_j$ 就 Yes 否则 No，不过根据大样例这个东西是没分的。 写完还剩 10min+，查了查文件然后开始随机说话，已严肃准备上迷惑行为大赏。 ``` // 洛天依的省选成绩等于所有锦依卫的省选成绩之和吗？ ``` **估分：28 + [30,45] + [12,22] = [70,95]** --- 出来教练说 142pts 都是送的，虾仁。 去吃了麻辣烫，注意到我之前根本没有吃过这种东西，所以一不小心点多了，最终拼尽全力无法战胜麻辣烫。喵！ 下午晚上继续打摆。刷到了不少好听的新歌。 ## Day 1 。 ### day2 等下？交互题？认真的吗？ 啊？B 又是构造？构造占据省选半壁江山是吧（ 怎么是函数式交互我没学过呀，不过题面写的挺清楚的，应该可以现学一下。 C 这是什么东西，这么长一坨不读了。盲猜是压轴题。 开 A，这下没法用大样例做题了。 想了一会儿发现 $0$ 的位置比较特殊，不够仍然毫无头猪，果断放弃正解。 $n=10$ 直接暴力枚举每个排列是否合法，复杂度是 $O(tn!n^2)$，但是注意到可以通过 $q(0,n-2)$ 和 $q(1,n-1)$ 确定 $p_{n-1}$ 和 $p_0$，那么复杂度就是 $O(t(n-2)!n^2)$ 的了。 于是直接看特殊性质，$p_0 = 0$ 的话可以从左往右递推，因为 $q(0,0)=1$，那么找到第一个满足 $q(0,i) \ne 1$ 的 $i$，则 $p_i = 1$，这个显然。然后依次类推，找到第一个满足 $q(0,j) \ne q(0,i)$ 的 $j$，则 $p_j = q(0,i)$，于是就能确定一些位置了，然后剩下的直接从小到大填就可以了，没有限制，因为当询问的左端点不是 $0$ 的时候结果一定是 $0$。 然后看特殊性质 B，假设已知 $p_x = 0$，然后如果确定了区间 $[l,r]$（区间内包含 $p_x$），那 $q(l,r)$ 仅可能位于 $p_{l-1}$ 或 $p_{r+1}$，所以直接问一个 $q(l-1,r)$ 就可以确定了，这样归纳，那么每个数只需要一次操作就能确定。但是不知道 $x$ 呀，想了半天发现只会用二分来求，第一个满足 $q(0,x) > 0$ 的 $x$ 就是要求的 $p_x = 0$，看了看范围 $n + \log n = 30015$ 给了 7.5pts，于是就写这个了。 此时大概 2h 吧。发现还是给了不少操作数很多的分的，于是开始尝试乱搞，就先二分出 $0$ 的位置 $p_x$，然后再分别向两边二分 $q(x,x)$ 求出来 $p_y = q(x,x)$，那么 $(x,y)$（或 $(y,x)$）这些位置就随便填 $(q(x,x),q(x,y))$ 内的数，依次类推就可以逐步扩大确定的区间了，直到确定的区间有一个端点在 $0$ 或 $n-1$ 上，就和 $p_0 = 0$ 的情况一样了。这样操作次数理论上来讲是 $2n \log n$ 的，不过显然远远达不到这个上界。 然后写写写调调调发现这一坨东西异常难写，到了 3h 的时候调不出来于是就扔掉了。 开 B，观察大样例失败。然后发现暴力都不会打啊！特殊性质也没看出来有什么意思，先输出一个 $n(n-1)/2$ 放着，去看看 C 能不能做点部分分。 （看 B 的期间听监考员说改了个 C 的样例解释，怎么这还是会出错的。看来这题过于困难了。） 发现又有大样例变乱码了 lol，用 dev 打开再粘回去就好了（埋下伏笔）。 拼尽全力读懂了 C 的一部分题面，可以我还是不知道集合是怎么比大小的。不过发现当 $x$ 固定为根节点的时候，$a_{x,x}$ 一定是“最大”的，那性质 A 是不是直接大力分讨就可以了？哦 $r=1$ 更简单，答案就是 $X \cap Y$ 的大小，分讨一下 $o_x,o_y$ 然后写个 LCA 求 $s \leadsto t$ 的长度就可以了。 开始写，惊奇地发现我竟然还记得树剖 LCA 怎么写甚至一次写对了。 $r=1$ 大样例过掉了，但是性质 A 怎么 fc 没过？开头结尾都一样呀，反复检查也没什么错误，然后突然发现 .ans 和 .out 打开后，右下角显示的编码形式不同，一个是 UTF-8 一个是 UTF-16（疑似），再次粘到 dev 里再新建 .txt 粘回去就好了。浪费了大概 10min。 还剩大概 30min，B 依然不会暴力，我觉得这个爆搜复杂度是炸掉的呀，复杂度达到了可怕的 $2^{n \choose k}$。不过注意到第一问 report 是有分的，所以直接上退火了。 结束前 10min 再次突然改了 C 的样例解释，hyw，然后又延时了 15min，让我有充足的时间给退火调参。然后最终退火死在样例 #3 了，总是比答案小 $40$ 多，无能为力了，因为这个数据范围退火确实不怎么优秀。 快速查了查文件和大样例。最后 1min 在 C 的结尾写下了： ``` whk 加油。 ``` 就结束了。 这里赛后才发现，我不该对着样例 #3 调参的，因为样例 #11 才是 $n$ 范围小的那个。不过倒也不重要了。 **估分：32.5 + ? + 8 = 40.5 + ?** --- 遇到了 @[梦见云月](https://www.luogu.com.cn/user/920947)，他说他在赛时进行了 sleep，不过写了和我差不多的分数，不过反正我们都是来玩的所以这不重要（） 光速吃了个快餐然后就归程了。 车上继续睡睡睡。 悲报：晚上上数学，要充满电了。 喜报：我不在的这几天没上任何新课，老师们对我还是太好了 w ## Day 2 正常 whk。 ## Day 5 教练说出成绩了。我省选 rk100+，但是和 NOIP 放一起折合一下就 rk40+ 了，和 NOIP 排名差别不大。位于分数分布密集区。 暴力打满（指会写的都写了）是这样的。 总之这辈子不可能进队喵喵喵。 --- ## 彩蛋 我认为我一定能上迷惑行为大赏。 $6$ 个题里面分别塞了一句歌词，猜猜都是哪首歌。 ::::info[答案] - D1T1 「走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊」 ——[洛天依《蝴蝶》](https://www.bilibili.com/video/BV1A14Se6EHy/) - D1T2 「我要陪你 走下去 一直到无边天际 感谢我们无数次交付彼此的勇气」 ——[洛天依《珍珠》](https://www.bilibili.com/video/BV1ZuGgzgENF/) - D1T3 「最黯淡的一个 梦最为炽热」 「万千孤单焰火 让这虚构灵魂鲜活」 「至少在这一刻 热爱不问为何 存在为将心声响彻」 ——[洛天依《光与影的对白》](https://www.bilibili.com/video/BV1dZ4y1Y7bt/) - D2T1 「至少此刻我们的心意相连 愿那片纯蓝天空一般高远」 「因为你是我的慰藉 多么沉重的负担」 「好在你始终微笑着 浑然不觉」 ——[洛天依《纯蓝》](https://www.bilibili.com/video/BV1z64y1b7H4/) - D2T2 「机械的心律带动血肉的共鸣」 ——[洛天依《为了你唱下去》](https://www.bilibili.com/video/BV1ts411y7FY/) - D2T3 「无论如何谢谢你陪我踉跄走过」 「是一百种曲折 亦是热泪暗涌凋零的命题 本就无法被印证」 「因为无惧此刻 鲜花开出名号却难做赤诚」 ——[洛天依《I Believe》](https://www.bilibili.com/video/BV1y3SgBbEZ6/) （纯蓝并非打错了而是喜欢那几句喵喵喵。） :::: 然后也塞了不少其他东西进去。好玩。 --- 华风夏韵，洛水天依！