题解鸽子了。所以先公开一下原题。

• B: https://artofproblemsolving.com/community/c2532359h2747309_heyawake_part_2__penalty_theory?srsltid=AfmBOornaIF0pSFtf6SWjdha_Uw4RBl67XEYxMySjrwyvmybc-y-dNRO
• C: https://uoj.ac/problem/293
• D: Evil Subsequence
• E: All the way left
• F: Autostrada 2

Public Easy Round #4 将在 2025 年 3 月 14 日 ~ 3 月 15 日举行！比赛将进行 5 小时，共 6 道题，IOI 赛制。

本次模拟赛的题目难度约为省选难度。每道题分值为 7 分，大部分题目都有部分分。

本次模拟赛的组题人 & 搬题人为 TBD，验题人为 TBD。

比赛链接：https://pjudge.ac/contest/1937

选手可以在若干时间窗口中任选 5 小时参加。

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

谢罪环节：

这次题目疑似组难了，码量也不太平衡。总之祝大家省选顺利（

最小表示法

来源：

• https://qoj.ac/problem/1855

拆成若干次计算 $[f(a_i) = f(a_{i+1})]$。

对于长度为 $n$ 的串，若循环节为 $d$，则 $f(s) = 1\sim d$ 的概率都为 $\frac{1}{d}$。

设 $g(n)$ 为循环节为 $n$、长度为 $n$ 的串个数，可以容斥得到 $g(n) = \sum_{d|n}26^{d}\mu(\frac{n}{d})$。

$P(f(n)=k)$ 可以分为 $d_0(n)$ 个值相等的连续段，对每个连续段算概率即可。

时间复杂度 $O(n d_0(V))$。

注意特判 $n=1$。

二叉搜索树

来源：

• https://qoj.ac/problem/971 加强版

首先把询问离线。考虑在链上怎么做：

考虑差分，维护两棵相邻 BST 之间的变化。扫描线，在 $[l,r]$ 加入插入操作，相当于 $l$ 时加入了一个插入操作，$r+1$ 时删除了一个插入操作。

考虑对于一个 $x$，哪些点是 $x$ 的祖先？

对于所有比 $x$ 大的数 $y$，把 $y$ 按照值从小到大排序，一个一个扫，设 $now=t_x$，如果 $t_y < now$ 则 $y$ 记入 $x$ 的祖先，并且 $now \to \min(now,t_y)$。也就是所有使 $now$ 变小的点的权值。

以权值为下标、时间为值建线段树，那上面要求的信息就是套用楼房重建，前缀最大值线段树的做法。

对于比 $x$ 小的 $y$，就是 $y$ 按照值从大到小排序，一个一个扫。于是维护两棵前缀最大值线段树即可。

在树上的做法：

直接树链剖分，对每条链套用链的做法，时间复杂度 $O(q\log^3 n)$，期望得分 72 或 100，被 hos_lyric 卡过去了。

既然在链上的做法是差分，那也可以套用到树上做树上差分。发现维护的信息就是在线段树上做，可以做树上差分+线段树合并。时间复杂度 $O(q\log^2 n)$，期望得分 100。

算法 2 by gqh

先发现答案的形式比较简单，只和x<=query的tim后缀最小值有关，x>query同理。

然后离线下来对x排序用吉司机线段树对time去checkmin即可。

虽然是 $q\log n$ 次区间checkmin，但是复杂度仍然是 $O((n+q)\log^2 n)$。

黑白球染色

来源：

• https://qoj.ac/problem/9438

相当于有一个直方图，图内的格子必须是 $0$，外面的格子可以是 $0/1$。（这里把 $a_i$ 翻转了，变成 $\le a_i$ 的必须是 $0$）

每个 $0\to 0$ 之间必须 xor 偶数次，$0$ 到末尾 xor 偶数或奇数次都行。

假设对于这每个绿色的区间都求出一个多项式 $f(x)$，$f(x)[x^i]$ 表示在区间内操作了 $i$ 次的方案数。

从下到上做，每个区间就是下面一层子区间一堆多项式乘起来，然后再乘一个变换。

这个变换在多项式上是 $F(x) \to \frac{(F(x+1)+F(x-1))}{2}$。

由于最终答案是最上面那个多项式的 $F(0)$，所以最下面多项式维护点值 $F(-m...m)$，往上一层能求出 $F(-(m-1)..(m-1))$，直到最上面一层能求出 $F(0)$，就行了。

开 $m$ 棵线段树，维护每一层的每个区间的 $F$ 值，以及 $F$ 值的区间乘积。修改一个 $a_i$ 时，只会有 $O(m)$ 个区间的 $F$ 值要重新计算。

时间复杂度 $O(qm^2\log n)$。

另一个做法：https://www.cnblogs.com/275307894a/p/18450179

省选 2025 即将来临，Public Round #15 将在 2025 年 2 月 15 日 ~ 2 月 16 日举行！比赛将进行 4.5 小时，共 3 道题，OI 赛制。

本次模拟赛的题目难度约为省选难度，所有题目都有部分分。

本次模拟赛的组题人 & 搬题人为 Crysfly，验题人为 Galex, gqh, seanlsy, xfrvq, xujindong, qiuzx 等。

比赛链接：https://pjudge.ac/contest/1914

选手可以在以下时间窗口中自由选择 4.5 小时参加（UTC +8）：

• 2025-2-15 08:30:00 - 2025-2-15 13:00:00
• 2025-2-15 10:00:00 - 2025-2-15 14:30:00
• 2025-2-15 13:30:00 - 2025-2-15 18:00:00
• 2025-2-15 19:00:00 - 2025-2-15 23:30:00
• 2025-2-16 08:30:00 - 2025-2-16 13:00:00

赛后会公开原题链接和题解链接。

特别提醒：本次比赛的题目均为原题，但为了比赛的公平性，请勿在比赛时尝试查找原题地址。如不幸见过原题，请向管理员报告。

粉兔本纪

陈亮舟者，闽人也，号小粉兔。少机敏，善算学，尝以弱冠之年入国集训队，列第五十有一，保送清华，名震天下。然其行止不羁，轶事遍传，世皆奇之。

少年峥嵘，锋芒初露

亮舟少时，以算法为剑，纵横OI（信息学奥赛）江湖。NOIP初赛，众皆折戟，独舟得九十又五分，冠绝同侪。后战NOI，虽列五十有一，然其志愈坚，誓曰：“吾必马踏常州，手刃劲敌！”终与同分者共入集训队，保送清华，领四载新生之赏，一时风头无两。

清华岁月，跌宕浮沉

及入清华，选人工智能实验班，课业繁重，晨起夜寐。然舟性疏阔，尝挂科二门，普物期末得廿二、卅七，四级试因晨食一包逾时缺考，毕设未竟，遂延卒业。然其勤学不辍，每至深夜，直播课业，虽错谬亦坦然示人。或问其故，答曰：“操……此乃抽代之玄奥也！”

舟好饮康师傅冰红茶，日啖二升，后易为白液（旺仔牛奶），自称“最强奶龙”。尝饮奶漏于裆，遗内裳于逆旅，为世所笑。

赛场纵横，毁誉参半

舟战Codeforces，尝负百四十七、百五十四，又因弊行负二百二十，洛谷公赛弊，名棕。然其志未堕，战CCSP得铜首，复言：“吾必马踏哈尔科夫，手刃优姆尼克！”世或讥其狂，或叹其勇。

阿赛一役，舟列三百五十七，败于涟水中专生，得号“败姜”。或戏曰：“涟氵与清华同源，舟败非战之罪，乃天命也！”

性情轶事，世所罕闻

舟好白丝女仆之服，尝于NOI之际出柜，裸照遍传网络。直播时遇弹幕指谬，或沉思良久，终叹曰：“此乃新错法，诸君慎之！”

其行率真，尝于图书馆观美人，不慎被困；又于自习室疑电脑失窃，实为旁人挪移。或问择偶之标，答曰：“操我要洗澡！”闻者绝倒。

太史公曰： 亮舟者，奇才也。其算法之精，可比项王扛鼎之力；其行事之诡，犹若鸿门宴之变。然刚愎疏狂，若项羽失韩信；挂科延毕，似霸王弃关中。然观其直播课业、答疑后进，亦存赤子之心。嗟乎！世之奇才，多毁誉参半。若舟能敛锋芒、修内省，则传奇宗师之业，可期矣。

赞曰：

算法为剑破长空，冰茶作酒笑疏狂。

裸照女装皆轶史，败姜挂科亦传章。

直播夜深星月黯，答疑年少意气昂。

若问传奇何日就？且看粉兔踏沧浪。

（注：文中轶事多引自洛谷、知乎诸帖，虚实杂糅，聊博一哂。）