RECALLector - 联合省选 2026 游记

· · 生活·游记

我常常 recollect 过去。

赛前学习了集合幂级数，SAM，FHQ-Treap，LGV 引理，复习了点分治，虚树，网络流，BSGS. 怎么一个都没用到？

Day 1

RECALLector : 开赛后 5 分钟由于大脑相当不清醒，认为 \mathbb{E}\left[\dfrac{x_1^2+x_2^2+\cdots+x_k^2}{x_1+x_2+\cdots+x_k}\right]=\dfrac{\mathbb{E}[x_1]^2+\mathbb{E}[x_2]^2+\cdots+\mathbb{E}[x_k]^2}{\mathbb{E}[x_1]+\mathbb{E}[x_2]+\cdots+\mathbb{E}[x_k]} 并对着这个写了 20 分钟。随后注意到了题目名中一个与 recall 近似的前缀。然后发现不对，尝试推一下这个式子，感觉不太行。那考虑维护每个点处重链长取到各个值时的概率。那就需要对每个 i=1,2,\cdots,k 和 d 求出 \sum\limits_{j\neq i}x_j=d 的概率。诶那这不就是个多项式乘法吗！感觉写 NTT 大概率调不动，考虑写 O(xy) 的乘法。嗯那怎么维护这个东西呢！肯定是计算前后缀然后每次拼两个啊！前后缀这个东西分析一下好像是 O(n^2) 的，那拼起来肯定也是吧！写写写。怎么只能过 n=500 啊，怎么 n=1500 需要跑 3200ms？感觉是常数问题，进行卡常。好，现在 n=1500 接近 2000ms 了！我们选择相信评测机！

我到比赛结束都没有怀疑过这东西是 O(n^3) 的。果然会被所有和 recall 沾边的东西用各种奇奇怪怪的方式创飞。

string : 小摩卡是什么？不管了。哇读懂题了。哇大量特殊性质。性质 A 好像就是个暴力，写掉！性质 B 是什么？依旧大脑不清晰，认为必须存在 x\ge n 使 k=(n-1)x-\dfrac{(n-1)(n-2)}{2}，一看样例输出发现不对。随后开始犯困。大概发现是求用若干个 f_x=\min(x,n-1)x-\dfrac{(\min(x,n-1)-1)\min(x,n-1)}{2} 拼出 k 的最小 \sum(x+1). 一个 dp 就好了。性质 C 是什么？考虑一个长度为 x 全为 1 的连续段后面还有恰 y 个字符会带来多少个字典序小于 n 个 1 的子串。进行一些猜和一些乱写，其实我自己也看不懂都写出了些什么，反正改一改过了。性质 D 是什么？不懂。随便写一些上面两个代码的结合，没时间测了，大概过不了。

night : 在写性质 D 前抓紧来拿点分。发现 n,m 和 T 不同时取到最大可能值。甚至去掉暴力的点也不同时取到。用 deque 轻松写掉暴力分。诶 m=1 是什么？好像必须全部拼起来，顺序随意。诶 m=2 是什么？好像每个拼完的数都对应原来的一个区间。可是这个区间好像还要满足一些性质，不懂，弃了。

期望 48+45+12=105. 出考场发现大家都过 RECALLector 了。好笑的是我出考场之后很长一段时间都以为自己是 80，不知道怎么算的。

Day 2

perm : 刚打开题面 pdf 就发现第一页上写着一个交互题。还好就写着一个。（埋下伏笔）不慌，先配置 Lemonlime. 嗯应该要勾选交互题。交互库路径？先打个 perm，匹配到了 perm/perm.h 等东西。库嘛，应该是 perm/perm.h。交互库名字？不就是 perm.h 吗？奇怪。什么什么接口？大概是 g++ grader.cpp perm.cpp -o perm -std=gnu++14 -O2 -static 那行东西吧。好先试试看。诶，编译错误，没有 __grader.cpp，这什么东西啊？把 grader.cpp 前面加两个下划线也没用。看不懂，算了。反正可以本地测试。看上去我们需要在 n 次询问内解决这个问题。我们把样例拿下来，算一下每个区间的 mex 拼出一个三角形。我们发现只有一个平行四边形内部是非零的，而且它的底部指示了 0 的位置，以及两条边长和是 n+1. 不过这两条边的顶部都是 [1,n]，这根本不用问。再多一次是需要询问出一个边界，会询问到一个 0，刚好 n 次，很有前途！我们发现这两条边上每次 mex 值变化就确定了一个数。那我们确定这些数之后剩下的是不是就随便填了？算了一下样例情况好像是这样。开写！不对大样例过不了。期望 [1,71] 的 mex 为 11，得到了 3. 怎么回事呢！哦看懂了，剩下的数不能随便插入，还需要保证一些前缀和后缀里必然出现了所有小于某个值，也就是 mex，的数。那从每个前缀的右端点向左依次填入小的数使其刚好符合要求，由于有解所以这样一定还有空间来符合后缀的要求。这些填完就可以随便填了，写的比较复杂。不对啊，我每次暴力往前查找是不是可以卡成 O(n^2) 啊！那我们用一个双向链表和两个并查集来维护每个点处上一个未填入位置和下一个未填入位置。这样就是 O(n\alpha(n)) 的了。但是我为什么写了个这么复杂的东西。随便吧。

starmap : 极有趣的题目。怎么题面第一页上第二题写成了传统题。（回收伏笔）我们发现这其实相当于要维护一个线性基。把每条边按照编号更大的点为第一关键字，编号更小的点为第二关键字，枚举 invert 操作包含的点集采取从大到小，插入线性基，看看这有什么规律。我们稍微尝试一下，发现对于固定的 k，不同的 n 似乎没有什么结构上的区别。并且我们发现 k=4t+2 时线性基每一维都有数，这意味着答案就是 \dfrac{n(n-1)}{2}. 还有 k=4t 时线性基只有最高位为第 0 位的那个基没有数，这样也很容易根据 m 和 \dfrac{n(n-1)}{2} 的奇偶性看出答案。k=4t+3 有最后 n-1 个基没有数，k=4t+1 有最后 n 个基没有数。但是太乱了。我们考虑用低位的基消元高位的基，得到一组等价的线性基。发现 k=4t 变为 p_i=2^i，等价于随时加一条边，k=4t+2 变为 p_i=2^i+1 和 p_0=0，等价于每次会加固定的一条边，同时加任意一条边，k=4t+3 变为高 \dfrac{(n-1)(n-2)}{2} 位每个存在的基分别一个，低位恰好每个存在的基两个。很容易猜出是所有带 n 号点的三元环。k=4t+1 的高 \dfrac{(n-1)(n-2)}{2}-1 位一样，但是低位挺奇怪的。大概还是能看出是每个存在的基各两个的形式，但是从低到高第 0,1,n-1 位被反转了，分别对应 (n-1,n),(n-2,n),(n-1,n-2) 这三条边。发现这就是固定一个三元环和任意一个带 n 号点的三元环。前两种情况已经解决了。考虑怎么做任意带 n 号点的三元环。我们发现可以无视所有和 n 的连边，先把 1,2,\cdots,n-1 构成的完全图点满，然后每次找两条没有的和 n 相连的边，连上并牺牲一条小完全图中的边。这样就做完了，发现能过 k=3，应该是对的。再考虑最复杂的一种情况，先待定那个固定的环是哪个，然后一样做。如果做的次数是偶数就任取一个固定的环，对答案没有影响。否则如果最后全部点满了就必须牺牲三条边，如果没有全部点满就必须牺牲一条边。于是就全部做完了。维护线性基可以考虑 \dfrac{n^4}{4\omega} 左右的 bitset. 大概能过 n\le 400，可能能拿满分，但是没调出来，最后赶紧回档到 k=3 加答案分的代码。可惜了。

industry : 这题维护的集合真有意思啊！我们发现只需要维护所有儿子节点的儿子节点的大小关系就可以比较出儿子节点的大小关系，就可以为这个节点的可重集内部排序了。随便写一下，不会分析复杂度，竟然过了 n\le 2000,o_x=0,o_y=0 的点。菊花的性质很简单因为 f 值可以轻松算出来。还有一个 r=1 必须有 x=y，只需要两点之间距离，随便写一下就好了。别的没想。

期望 100+34+24=158. 如果谁听到我说的不是 158 那我大概藏了下分吧。这次没有算错。

两天加起来但凡挂点分就低于同学一天的分数了，怎么回事呢。我到底为什么没切 RECALLector. 切了也进不了队。我这一年都干了些什么。暂时获得退役倾向。