@游记@ CQOI2019（十二省联考）

- 日理万妓 2021-11-09 13:28 441阅读 0赞

*  @day - 0@
 *  @day - 1@
 *  @day - 2@
 *  @后记@

--------------------

我只是来打酱油哒……

顶多能进个 E 类继续打酱油。

原本还在互奶 A 队，结果现在……铁定进不了队啦。

对初中生的歧视啊 qwq。

## @day - 0@ ##

试机日。

想起来我前几天有一道题还没过，于是继续调试。

每次想要打 \\ 总会按到回车，想要打退格结果又按到了 \\。  
这个键盘真的好令人难受啊（可能只是因为不习惯而已？上次 noip 的键盘也这个样子来着）……

一开始的时候好像没有网啊……还靠的是学长的手机开热点上网。  
也不知道最后网恢复没有。

试机完惊讶地发现这一个月以来我什么模板都没背（flag \* 1），都在补文化课。  
而且试机的时候也没有练习对拍怎么打（flag \* 2），那道试机的时候想写的题最后也没有调过（flag \* 3）。

初三学生还要抽出时间来省选，我真的是 TAT……难受 TAT……  
而且已经知道了结局，都没什么斗志考好 TAT。

不说了，我去练体育了。4 月 17 日就考体育。

## @day - 1@ ##

重启试了试保护，结果开机等了几分钟……  
我还以为出了什么问题。真的很吓人……

今天的密码好正常啊（具体是什么忘记了，至少比第二天那个好多了）。

因为老师叮嘱过，所以打开题目先看了编译选项。嗯，c++11 和 O2 都有。  
想起来我试机的时候把 -O2 打成了小写的 -o2，结果编译出来是“编译到 2.exe”的效果。  
还让我懵逼了半天……

然后开始看第一题：

> 给定一个序列，求前 k 大的区间异或和的总和。

噫？这不是可持久化 trie 的模板题吗？  
不对，可持久化 trie 是用来解决最大异或值，而不是前 k 大。  
为求稳先写了个 O(n^2) 的暴力，然后开始用暴力跑大样例。  
通看一遍题目先~

第二题大概长这样子：

> 给定一个字符串 S。给定若干 S 的子串 S\[l...r\]，记为 Ai；再另给定若干 S 的子串 S\[l...r\]，记为 Bi。  
> 给定若干支配关系 (i, j)，表示 Ai 支配 Bj。  
> 如果 Bi 是 Aj 的前缀，则称 Bi 支配 Aj。  
> 如果存在 Bi 使得 Ap 支配 Bi 且 Bi 支配 Aq，则 Aq 可以拼接在 Ap 之后。  
> 问最长可以拼接多长的字符串。无穷长特判。

第一眼……拓扑排序吧。如果 Aq 可以拼接在 Ap 之后就连边，判一下环，求一下最长路。  
稍微优化一下就是 A 类子串向 B 类连边，B 类子串向 A 类连边。  
A -> B 边数是有限的，考虑 B -> A 就可以了。

仔细分析了一下数据范围……有一个所有 Bi 的长度都 <= 任一 Ai 的长度的部分分。  
也就是说只需要判断 Bi 是 Ai 所对应后缀的前缀即可。  
难不成是……后缀数组。

还是看看下一题吧。万一更简单呢。

……

嘶……

啥玩意儿啊。省选怎么也开始考这种奇形怪状的题目了。  
我以为冬令营考就够了……没想到现在省选也这样。  
大致题意就是：

> 所有输入输出均已给你，并且给定了每个数据的类型名称。  
> 代码长度有限制，即你不能打表（后来发现每一组数据都超过了代码限制，出题人 nb）。  
> 类型名称越相近，需要实现的东西越相近。

果断回去玩第一题。  
发现可以通过逐位确定求出前 k 大：  
考虑异或过后最高位为 1 的数的个数，如果小于 k，暴力找出来；如果大于等于 k，则所有的数最高位肯定都为 1。  
暴力找最多找 k 次，所以总时间复杂度 O((n + k)\*32)。

写了一会儿感觉没问题，测完大样例，过了。  
突然想起来我的那个 O(n^2) 的暴力还在跑大样例……  
小老弟你怎么回事啊，正解都已经出来了你怎么还在跑。

然后仔细分析一下第二题，好像的确可以用后缀数组 + 线段树建图。  
如果不限制 A 和 B 的长度的话就用可持久化线段树搞搞。

……

但是……我好像……有点儿忘记后缀数组怎么写了。  
flag 开始灵验。

先玩第三题吧。

作为一个 OIer，对 361 = 19^2 这个事情非常熟悉（不要在意这个因果关系有没有问题）。因此很轻易就看出来这是一个快速幂。  
那么类型 1 就是快速幂吧。后面的后缀 998244353 就是模数吧。  
但是数据 2, 3 好像要写高精度……不管了先肝再说，不要浪费时间。  
一测。嗯，很好，过了。

后缀 ? 应该是模数未知的意思吧。枚举了一下把模数枚举出来了。  
后缀 ?+ 是……模数未知且很大的意思吗？感觉好像枚举不出来模数啊……先看下一个吧。  
后缀 wa，结合题目的注释，应该是溢出了吧。试了试。口意？跑出来这么多 0 是怎么回事？  
大概研究了一下，发现它没有用快速幂，是一个一个乘上去的。  
那输入数据这么大……是怎么回事啊

开始研究类型 2。首先大致观察了一下后缀 p 的数据，确认了输入的是区间左端点和右端点。  
然后开始……差分？（脑子傻了吧）发现并没有什么规律。  
开始研究差分之间的倍数关系，于是联想到了质数。发现最初两个相邻的 p 对应的恰好是 2 和 3。  
并且 p -> prime（质数）。  
（当时激动地一拍脑袋，好像把旁边的人吓了一跳 www）

那么 2u 就是莫比乌斯函数吧。一看，输出的是 +0- 三种字符。肯定是这样跑不脱了。  
那么 2g 就是原根吧。一看，998244353 的 3 位置是 g。肯定是这样跑不脱了。  
2g? 就是模数未知的情况。一看，woc，竟然有出题人的讯息？！还真是这样。

但是……我考前也没复习数论啊。  
flag 再次灵验。

大概写了写 miller-rabin（不敢写 pollard-rho 因为完全忘记了……），发现要跑 20 多秒。写了会儿线性筛走人。

然后开始正面肝 T2 的后缀数组……凭着微弱的记忆大致写了一个轮廓。  
一测大样例（因为小样例的数据都不是特殊数据）。woc，对不上。  
内心开始慌张。

构造的小数据……好像没有问题的样子啊。  
怎么办啊……  
难不成我就这样死在一道已经想出（？）正解的题目上了吗？

慌张到无法构造数据，只好静态查错。

……

woc 我 ST 表记录的是最小值的下标而不是值。  
改改改。一测。还是对不上。

……

woc 我访问 height 数组是用的原下标而不是 rank。  
改改改。一测。对上了。

谢天谢地。  
再构造了几组小数据走人。

最后剩 30 分钟。决定还是再来玩第三题，能多骗分就多骗吧。  
发现印象里，可以通过线性筛前根号个质数，就可以筛出一定范围内的质数。  
同理可以筛出一定范围内的莫比乌斯函数。

连样例都没测就直接写写写。最后 5 分钟，静态查错发现我的莫比乌斯函数有个地方好像写错了。  
改改改。也不敢去测。

然后就打铃了。

然后还没出去就听到 yhn 学长说他爆零了。

骗人的吧。

——自动分割——

下午回去体锻了，所以并没有听到讲评。

晚上回去看成绩，被吓了一跳。惊了，我居然全场第二。  
D1 分数 220 = 100 + 80 + 40。不过还是比 lhc 大佬菜。

骗人的吧。

回去核实了一下，发现 yhn 学长 D1 真的爆零了。

凭他的实力，D2 翻盘没什么问题的。我在心中默默祈祷。

## @day - 2@ ##

提前发游记，引起恐慌，竞赛三年。

现在不会被禁赛了。

明天慢慢补（然后就咕咕咕到了 6 月 NOI 集训）。

虽然咕咕咕到现在不过我还是凭记忆写写

看到密码的一瞬间，一句 woc 差点喷出来。  
不行抓紧时间打开题目看。

第一题，皮配。  
woc 虽然没有做往年的省选，不过对于“pi pei”这一个题目莫名印象深刻。  
难不成今年和前几年一个套路？  
发现题目有些长，读了几遍还是一脸懵，跳。

第二题，春节十二响。  
题面说的什么内存块根本没什么用啊，这就是一个树上的问题啊。  
研究了一下一条链的情况，发现可以通过一直找最大的值然后贪心匹配链另一端最大的值。  
然后大概猜想了一下推广成一棵树的情况。找到这棵树最大的结点然后从大到小依次贪心匹配。  
手写了个 O(n^2) ，一测差不多可以过。

第三题，希望。  
。。。  
看完我整个人都绝望了。  
想了大概半小时，没思路，滚回去玩第一题。

再好好想了想，发现第一题有点儿背包的模样。  
可以将有偏好的人单独提出来分类讨论，搞一个大暴力（误）。  
理想很宏大，但是看了看时间，决定还是写了一个初学 dp 的人都会写的代码。

最后剩下半个小时，决定还是尽力 T3 得一个 5 分。  
然而并没有写完。。。  
D2T3 爆零啦。

——自动分割——

今天没有体锻，所以可以愉快（自闭）听评讲。

第一题是个神仙背包加神仙优化。不会。自闭。

第二题的确是个贪心，不过我想的方向和正解的方向不同所以只有暴力分。  
正解是个启发式合并。  
原题目定的是叫作 “清明十二响”。现在我真的感觉是 “清明十二响”。  
据说题面是为了迎合第三题才改成了那副模样。

第三题。。。只能说爆零无憾。  
一开始来什么连通块的边和点分开考虑，然后作了个什么换根 dp，然后开始什么可持久化可回退化什么奇奇怪怪的数据结构。  
反正倒在第一步。就没有认真地听。  
题目描述的开头引用了鲁迅作品中的一段话。还行。

D2 全程自闭。。。

评讲完一出去就看到成绩出来了。  
嗯。D2 成绩 135 = 60 + 75 + 0。（虽然现在记不大清了不过应该是这个分）  
果然清明十二响了。

yhn 学长 190 = 70 + 100 + 20 D2第一吊打全场，太强了 orz。  
不过。。。D2T3太难了，始终拉不开差距啊。。。  
哎。。。

## @后记@ ##