FJOI2021 游记

> FJOI 就没走过。——luhong 今年省选 FJ 还是独立命题。  富有特色的 FJOI……一言难尽啊，懂的都懂。~~心疼河北人一秒钟。~~ --- 惨遭 CSP 和 NOIP 爆炸的血泪史后，我深刻地认识到：比赛千万不要有任何的功利心理。你越想得到什么，你就越得不到什么。 完全放松，抛开一切压力，这是最好的。 --- 同届的巨佬们都好卷啊，特别是 Linshey。我是在他们的鼓动下才开始认真做题的。 $\Large{\text{Day }-13\ (3.27)}$ NOI Online，明明会 $185$ 却只写了 $145$，T3 的部分分还写挂了，于是挂到了 $130$。自闭了。 $\Large{\text{Day }-12\sim -11\ (3.28\sim 3.29)}$ 补完了兔队和宏队的模拟赛 ~~（当然，[五种操作题](https://www.luogu.com.cn/problem/AT5752)除外）~~。 $\Large{\text{Day }-9\ (3.31)}$ 交了停课申请，从此每天在机房做题。 $\Large{\text{Day }-8\ (4.1)}$ 谢队出了 FJOI 模拟赛，一眼不可做，直接弃赛。 下午讲评，从一点多讲到了将近三点，太珂怕了。 终于补完了去年的联合省选题（保序回归和两道水题除外）。 晚上打 CF 愚人节比赛，被吊起来捶。 $\Large{\text{Day }-7\ (4.2)}$ 今天还是有 FJOI 模拟赛，在谢队的怂恿（？）下认真打了。 T3 是 $n\le 10^5$ 的[树上的数](https://www.luogu.com.cn/problem/P5659)，太珂怕了。 T1 快乐暴力。T2 写了个辛普森套辛普森，Linshey 和 hhoppitree 也是这样写的，结果我们全部 TLE。 傍晚回家前又让 Linshey 给我推荐了几道省选联考题~~然而我一题都没写~~。 晚上 $10$ 刷《你的名字。》。 $\Large{\text{Day }-6\ (4.3)}$ 做 cyx 的模拟赛，T1 单调栈 sb 题不会，我好涝啊。 $\Large{\text{Day }-5\ (4.4)}$ 今天还是 cyx 的模拟赛，T1 A 掉了真香，T2 和 T3 快乐暴力。 晚上快乐打洛谷愚人节比赛。hhoppitree 太强了！!1 $\Large{\text{Day }-4\ (4.5)}$ 补了谢队模拟赛里最简单的两题。 晚上搞模拟费用流。 $\Large{\text{Day }-3\sim -2\ (4.6\sim 4.7)}$ Linshey $4.3$ 就开始卷 FJOI 真题了。我也要卷！!1 于是做了相对可做的几道题。 $\Large{\text{Day }-1\ (4.8)}$ 这几天总感觉还有好多东西没复习，于是列了一张长长的（？）复习单。 写了 wqs 二分的板子题，然后复习在洛谷上写过的所有模板。为什么你们都写过这么多模板啊 qwq……我被吊打了。 越复习越自闭，于是开始循环《你名》BGM，感觉极度舒适。 $\Large{\text{Day }0\ (4.9)}$ ~~你们怎么都开始看番了啊……~~ 简要地翻看了自 NOIP 起在洛谷上做过的所有题，越看越自闭，于是开始划水。~~PVZ 真好玩。~~ 去试机，先敲了 NTT，还写了对拍。然后写费用流，但没调出来，van 了。 放学时 Konnyaku_LXZ 说每个省只有两个 E 队名额（真的假的？），我这个 sb 就别想进队了，放轻松吧。 于是晚上 $11$ 刷《你名》，感觉极度舒适。 > _无论你在世界的什么地方，我都一定会再去见你。——《你的名字。》_ # FJOI2021 RP++！！！！！!1 $\Large{\text{Day }1\ (4.10)}$ Kita！!1 早饭吃太急然后全吐了（？） 到学校时发现人基本到齐了，但幸好我不是最后一个到的。最后一个到的是 18Michael，他走进校门时，引起了一阵膜拜。 大家一起谈论一些神奇的东西，比如网络流不要加反向边（？） 进考场，感觉非常放松。这就是我要的感觉！！!《你名》nb！!1 开题，果不其然是 FJOI 而不是联合省选。 敲代码，不要停！先敲了 T1 的 $30$ 分暴力并过了样例，但它跑得有亿点点慢……卡常这种东西当然要留到后期再做啦，于是先扔在一边。 看 T2，艰难地正确理解了题意。开始找规律，想到贪心地排列，但直接手推好像有点麻烦，于是敲了个暴力来验证。然后就得到了一个简单的结论，打个表然后二分一下就行了。 看 T3，不会，写暴力。想到枚举 $x$ 的每一个区间然后更新答案。直接用 `multiset` 维护可以做到 $\mathcal{O}(n^2\log n)$，但是显然可以改成用链表维护，做到 $\mathcal{O}(n^2)$。 突然发现题目没说 $x$ 中元素互不相同、$y$ 中元素互不相同。不过没事，要是真这样的话我直接问候出题人。 回过头来看 T1，想了想，好像会做了！！!于是检查了下 T2 和 T3 的代码并交了上去，然后就没管 T2 和 T3 了，硬刚 T1。 考虑把本质相同的 $C$ 处理成同一个字符串。枚举 $A,B$ 的每一种取值，计算出 $A+B$ 的结果，用一个字符串表示：若结果中的某个数字在 $A$ 或 $B$ 中出现过，就用对应的字母表示；否则从前往后依次分配当前没用过的最小的字母。把这些字符串塞进哈希表或 `map` 里。 查询时，用同样的方法处理 $C$。由于我们把本质相同的 $C$ 处理成了相同的字符串，所以直接在哈希表或 `map` 中查询即可。 我比较懒，没写哈希表，直接用了 `map`。写完过了样例，很好。造了组极限数据，发现它跑了 $16$ 秒……我好涝啊。排查一下发现是 `sprintf` 太慢了，于是改成手写。好，现在它只要 $6.8\sim 6.9$ 秒了，学校的机子比较慢，应该可以过。 算一下空间，似乎只要 $80\text{ MB}$ 左右来着？打开任务管理器（我第一次用这东西看空间！!1），发现竟然要 $380\text{ MB}$ 左右，好危险啊。 然后一直检查代码，直到考试结束。 小插曲：考试时我们上的厕所是女厕所（？） 考完发现好多人在讨论 T2 题面中的“自由”两个字是什么意思，以及到底是两个人的乘积还是三个人的乘积。 > $9$ 号倒着坐变成 $6$ 号。——Rainy7 不过我要相信自己的语文能力（逃 然后我得知考场的机子是不久前刚换的，跑得很快。那我 T1 不是大危！!1 于是：  回家吃完饭，在床上躺到了三点多。起来后发现：  $100+100+40=240$，初中组/同步赛 Rank 1！！! 不过我不能高兴得太早，会影响到明天的考试的。 但我还是有点慌，感觉自己的状态不大对劲。于是晚上二刷《天气之子》，感觉极度舒适。现在感觉之前我认为《天气之子》不好看是因为《你名》太好看了？ ~~考前看番对调整心态真管用。~~ 看完后发现 Linshey 找到了 [T3 原题](https://www.luogu.com.cn/problem/P7484)。FJOI 搬题这么迅速（？） ~~**UPD：** 这才是[真正的 T3 原题](https://loj.ac/p/2773)，是 Zenislt 找到然后告诉 Linshey 的。~~ **UPD：** 学长找到了真正的 T3 原题，连样例都没改！!1 > _为了那个梦我们扬帆起航，为了理应到来的那天跨越无尽黑夜。——《天气之子》_ $\Large{\text{Day }2\ (4.11)}$ 进校门时大家已经在往考场走去了。此时 Rainy7 转过头来看见了我，大叫一声“队爷”。van 了啊。 进考场，感觉状态保持得还不错。《天气之子》nb！!1 开题。这都是些什么鬼玩意啊……T2 三维计算几何，T3 推式子！！!这对我这个数学菜鸡非常的不友好 qwq。这就是 Day 2 吗？ 感觉 T1 是最可做的，但想了一会儿发现不会，于是写暴力。哈希没有前途，直接上 SAM。然后 SAM 一开始还写挂了，幸好找到错了。写完过了样例就没管它了，多测清空什么的后期再写。 瞄了一眼 T2，直接弃掉。看 T3，盲猜答案是个关于 $n$ 的多项式（？）于是写了个高斯消元算了一下，发现并不是。 只好开始推式子，发现模数不一定是质数，要把组合数消掉。推了好久，发现总是消不掉组合数……推了跟没推一样，自闭了 qwq。于是就当作模数是质数，写了发暴力。 回头想了想 T2，发现自己不会球体的表面积公式（别跟我说积分！!1），更何况它还带着一个圆心角……没事，这题肯定没什么人有分，不写也罢。 又想了想 T1，还是不会，自闭了。于是开始造样例，随了一个 $3\times 10^5$ 的数据，发现它跑得飞快。应该是 Parent Tree 的树高不太大就可以水过吧（？）~~希望数据水一点，让我水过。（bushi~~ 又造了组小数据检查 DP 的转移，似乎没有问题。感觉无事可做，于是造了 $n$ 个数据乱测。感觉答案的大小和模式串长度的关系是玄学？ 最后一小时用瞪眼法检查代码。发现 T1 的用时和 Parent Tree 的树高没有太大关系，文本串全是 `A`、模式串数量多一点就被卡爆了，而只跳 Parent Tree 而不转移却跑得很快。 突然脑子一抽，想着我 T1 为什么不写广义 SAM 啊（？）哦原来只有前后缀啊，那没事了。 最后三分钟打开了扫雷，但是一局都没扫完就不想玩了。 今天去了两次女厕所（？） 出考场时自闭了，感觉昨天的优势荡然无存。 Linshey 说他 T1 切了，T2 有 $20$ 分。这是什么神仙啊！！!我只能被吊着打 qwq。 然后 18Michael 说他 T1 也切了，还推出了 T3 的式子，但 T3 由于不会快速阶乘只有暴力分。这就是数竞内鬼吗！!1 问 Linshey 他 T1 是怎么做的。他说“广义 SAM”，我震惊了，告诉他不是子串而是前后缀（？） 18Michael 说他 T1 写的是 KMP，我震惊了，这怎么 KMP 啊？但想一想好像挺有道理的，我为什么没想到啊 qwq。回家路上 18Michael 说我要进队了，但他今天吊打了我 $n$ 分，肯定把我挤下去了 Orz。 回到家仔细想了想，发现这 KMP 做法好像有点不对啊……首先是后缀的匹配有点假，其次是多个模式串和文本串匹配的复杂度假了~~别跟我说 AC 自动机~~。 今天两点多就出成绩了，$40+0+0=40$，竟然还有 Rank 3。T1 多水过了 $10$ 分！!1 一看 Rank 1，是 18Michael，他 T3 竟然 A 了！！!赶紧跑去问他是怎么 A 的，他说他 $\mathcal{O}(p)$ 水过了 $10^{10}$（时限 $10$ 秒）。18Michael nb！!1 只不过 18Michael T1 保龄了，真可惜。后来他和暴力对拍了一下，发现又 T 又 WA，看来这 KMP 做法确实假了。 Day 2 好多人都保龄了。T2 初中组这边没人有分，完全符合预期。 感觉 T3 就是个找规律题啊~~推个 der 的式子~~……我为什么没有认真找找规律呢？ --- 算一下我的标准分，是 $41.03$ 分，惊险地压进了省队线，看来是进 E 队了。~~没法控告 Rainy7 fAKe 了。~~ 我可以说是走运的，要是 D2T1 没有多那 $10$ 分我就没了。 18Michael 可以说是遗憾的，但凡他 D2T1 拿了一点分他就进队了。 不过事已至此，就不要再多说什么了吧。反正我除了乱搞啥都不会，去了 NOI 也是爆零对吧。 现在我非常担心 $4.20$ 的体育中考。加油吧。 **UPD：** 体育中考挂了，我垫底了，好耶！!1