FJOI2021 游记

chen_03 · 2021-04-11 16:40:20 · 个人记录

FJOI 就没走过。——luhong

今年省选 FJ 还是独立命题。

富有特色的 FJOI……一言难尽啊，懂的都懂。心疼河北人一秒钟。

惨遭 CSP 和 NOIP 爆炸的血泪史后，我深刻地认识到：比赛千万不要有任何的功利心理。你越想得到什么，你就越得不到什么。

完全放松，抛开一切压力，这是最好的。

同届的巨佬们都好卷啊，特别是 Linshey。我是在他们的鼓动下才开始认真做题的。

NOI Online，明明会 185 却只写了 145，T3 的部分分还写挂了，于是挂到了 130。自闭了。

补完了兔队和宏队的模拟赛 （当然，五种操作题除外）。

交了停课申请，从此每天在机房做题。

谢队出了 FJOI 模拟赛，一眼不可做，直接弃赛。

下午讲评，从一点多讲到了将近三点，太珂怕了。

终于补完了去年的联合省选题（保序回归和两道水题除外）。

晚上打 CF 愚人节比赛，被吊起来捶。

今天还是有 FJOI 模拟赛，在谢队的怂恿（？）下认真打了。

T3 是 n\le 10^5 的树上的数，太珂怕了。

T1 快乐暴力。T2 写了个辛普森套辛普森，Linshey 和 hhoppitree 也是这样写的，结果我们全部 TLE。

傍晚回家前又让 Linshey 给我推荐了几道省选联考题然而我一题都没写。

晚上 10 刷《你的名字。》。

做 cyx 的模拟赛，T1 单调栈 sb 题不会，我好涝啊。

今天还是 cyx 的模拟赛，T1 A 掉了真香，T2 和 T3 快乐暴力。

晚上快乐打洛谷愚人节比赛。hhoppitree 太强了！!1

补了谢队模拟赛里最简单的两题。

晚上搞模拟费用流。

Linshey 4.3 就开始卷 FJOI 真题了。我也要卷！!1

于是做了相对可做的几道题。

这几天总感觉还有好多东西没复习，于是列了一张长长的（？）复习单。

写了 wqs 二分的板子题，然后复习在洛谷上写过的所有模板。为什么你们都写过这么多模板啊 qwq……我被吊打了。

越复习越自闭，于是开始循环《你名》BGM，感觉极度舒适。

你们怎么都开始看番了啊……

简要地翻看了自 NOIP 起在洛谷上做过的所有题，越看越自闭，于是开始划水。PVZ 真好玩。

去试机，先敲了 NTT，还写了对拍。然后写费用流，但没调出来，van 了。

放学时 Konnyaku_LXZ 说每个省只有两个 E 队名额（真的假的？），我这个 sb 就别想进队了，放轻松吧。

于是晚上 11 刷《你名》，感觉极度舒适。

无论你在世界的什么地方，我都一定会再去见你。——《你的名字。》

FJOI2021 RP++！！！！！!1

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 题面中的“自由”两个字是什么意思，以及到底是两个人的乘积还是三个人的乘积。

不过我要相信自己的语文能力（逃

然后我得知考场的机子是不久前刚换的，跑得很快。那我 T1 不是大危！!1

于是：

回家吃完饭，在床上躺到了三点多。起来后发现：

进校门时大家已经在往考场走去了。此时 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