ISIJ 2020 游记
Froggy
2020-07-11 21:39:33
注：这里的 Day 1 是 7月1日（原本的报到日），但是第一场比赛是在 7月3日的。
比较长（我这个菜蛙比较闲~~而且只会写流水账~~），但是一定不要错过 Day 8 （Math Tournament），~~见识一下毛子的数学题~~，**非常好玩**。
附：[**官网公告**](http://www.noi.cn/newsview.html?id=1305&hash=BA1C6A&type=1)
# Day -53
csp考成那个样子也竟然进代表队了。。。
---
# Day -46（第1场模拟赛）
还好不是特别难。
开场 20min 切掉 T1 和 T2（还是过逊，人家 ntf 不到 15min 就切了）。
然后开始自闭。。
发现了 T3 的“六个一循环”的性质，盲猜可以三分，但是不会证明，所以干脆码了个模拟退火（IOI赛制嘛。。珂以乱搞），一直徘徊在 77pts 左右。。。
然后 sxyz 的神仙同学 zyk 交了一发模拟退火就 AC（我人 tm 都傻了）。
~~然后借鉴了一下参数~~，才卡过去。
T4 是个嘤文阅读理解题，读了 1h 才读懂。
是个挺裸的优化 dp，快速码一波，显然珂以倍增优化，交一发，MLE。
空间 $\mathcal{O}(a\log a)$，$a$ 的范围达到了 $2\times 10^6$，空间只开了 $\mathrm{122MB}$ ！！（毒瘤出题人）
最后 $100+100+100+66=366pts$ 滚粗，苟上 rank6，丢人。
## 简要题解：
### T1：
胡乱枚举
### T2：
好吧我说一下题意（毕竟比较裸）：求 $[l,r]$ 中有多少个数是“上升的”，（“上升的”意思是从高位到低位不减，比如数字 $1145$，或 $23333$ 之类的。）。
$\mathrm{Data\ range}:1\leq l\leq r\leq 10^{100}$。
显然的数位 dp，不啰嗦了。
### T3：
发现一个六个一循环的规律，然后把数列前两项三分出来。
（然鹅我用模拟退火艹过去了2333。。）
### T4：
T4 的做法好神仙啊qwq，不会不会qwq。（貌似珂以直接用 `deque` 艹过去？%FZzzz）
---
# Day -39 （code+）
丢人，最后 1min 写完 D 题，然后把 $n$ 和 $m$ 写反了（样例tm是 $n=m$ 的）。
不好意思说分数了。
---
# Day -32 （第2场模拟赛）
由于要外出，在车上打代码，晃得难受。。
djq 出的题目，依然~~凉~~心。**（裸题大赛）**
T1 一开始看错题目了（嘤文阅读理解题，IEE）。快 1h 才切掉，心态直接爆炸。
T2 动态维护树的直径的板子题，算是[这题](https://www.luogu.com.cn/problem/P4271)的加强版吧。
直接上 LCT，~~复制过来魔改一发~~，结果还是因为一个细节错误调了半天，555。
T3。。。就是[这题](https://www.luogu.com.cn/problem/P5247)了（原封不动）。~~tm我复制 std 怎么过不了？！~~ 嗯还要判重边，好恶心。
我不信我 2h 还切不掉 T4！！
T4 一眼就是个二分+扫描线，调了 1h+ 才出来（还是代码能力过逊）。
交一发，$84pts$，TLE 了。感觉线段树写得太丑，再卡一卡，结果变成 $80pts$ ？！我人tm直接傻掉。卡到最后也没多一分。（结果重测的时候评测机变慢了又少了 $4pts$。。）
最后 $100+100+100+80=380pts$ 滚粗，和第一场一样，依然 rank6，依然丢人。
## 简要题解：
### T1：
无脑离线然后线段树维护。
### T2：
无脑 LCT。（怎么这么多人写启发式合并。。）
### T3：
无脑 ETT。（然鹅我用双向 bfs 跑得飞快）
### T4：
无脑二分 + 扫描线。（墙裂谴责卡常行为，好歹开 2s 。。）好吧我人傻常数大，%djq神仙，%xtq神仙。
---
# Day -31 ~ Day -18
木有任何比赛，刷完 eJOI 2017~2019 的题目。
## [eJOI 做题总结](https://www.luogu.com.cn/blog/1445353309froggy/ejoi-zuo-ti-zong-jie)
---
# Day -X ~ Day 0 （Trial Round）
原本是放在 7.2 的试机赛但是现在是线上赛所以提前了，~~然后这场比赛进行了一个月~~。
T1：$a+b\ \ \mathrm{problem}$
T2：$a^2+b^2\ \ \mathrm{problem}$
T3：~~比前两题不知道神仙到哪里去了。~~
写了 1h 调了 1h 然后发现复杂度是错的，只得了 $84pts$。
~~然后 zyk 给我说了说我才做出来。~~
T4：降智题，暴力能拿到 $84pts+$。
过了两天，zyk 瞎枚举就过了，我拿模拟退火艹过去了。真的降智啊！
考前几天让选AB组（A组难，B组简单，去年的A组是IOI难度，B组是 eJOI 难度。）
我问了一圈，FZzzz 还给我发个：
>虽然我非常菜，但是我觉得还是有一点点实力的，我应该为更高的目标至少做一点尝试。即使拿不到金牌，甚至打铜也并没有什么关系，我不愿为此特意换组。毕竟我也不是为了一块牌子而放弃中考后宝贵的娱乐时间来遥远的俄罗斯的。 ——EA
害，管他呢，就选 A 组算了。
---
# Day 1
既然是线上，那就省略了很多步骤，不需要报到了。
这里放个大概日程：
| 日期 | $14:00\sim18:00$ | $19:00\sim20:00\ \ $ | $20:00\sim 21:00$
| :----------: | :----------: | :----------: | :----------: |
| $7.3\sim7.7$ | 练习赛 | 讨论时间 | 订正赛 |
| $7.8$ | 数学考试 （只考到 $16:00$） | ~~颓废~~ | ~~颓废~~ |
| $7.9$ | 杯赛（正式赛） | 讨论时间？ | ？？？ |
| $7.11$ | 评奖 | ~~颓废~~ | ~~颓废~~ |
即：5 场练习赛 + 1 场正式赛。
IOI 赛制，可以看榜，每题有 $100$ 次提交。
这比赛最坑人的是部分分需要自己猜，不在题面上写。（啊这
P.S. 练习赛和杯赛分开评奖，订正赛也算分。。（当然，锕氪了就不需要参加了。）
>djq：不会真有人需要订正吧 不会吧 不会吧
---
# Day 2（开幕式）
晚上 $6:00$ 开始开幕式。
一会儿嘤文一会儿俄文，总之，一个字都没听懂。
---
# Day 3（Round 1）
这场最尴尬的是我不知道怎么变嘤文所以我全程拿 google 翻译俄文。。
咦？怎么就 3 道，去年不是 4 道么。。（预感题目难度会增加）
先开 A。憨憨题，随便构造一下就好了，5min 之内秒掉。
交一发，然后 TLE？？tm 的还要文件输入输出。。
再开 B。憨憨题，胡乱数位 dp 一下。
交一发，然后 MLE？？tm 的出题人怎么这么凉心，就开 $64\mathrm{Mb}$。。
然后发现 dp 的时候可以省去几倍空间。
再交一发，然后 WA？？（*&……@%!￥&#￥%……
噢，自己太慌了，把 `1` 打成了 `i` 。
还 WA？？？。。。崩溃了啊。。。
淦，原来我写的憨憨做法会把方案算重。。。然后删了重写了个新做法。
最终花了半个多小时才 A 掉，慌慌慌。。
开 C。
还有 3.5 h 我不信我就做不出来了。
想了半天没思路，交个 $\mathcal{O}(n^3)$ 的只有 $60pts$。
然后我迷茫了。。最优化题嘛。。我 tm **模 拟 退 火**！
效果不是很好，所以干脆改成爬山算法。
交一发，$94pts$，再交一发，$98pts$。嘿嘿！
然后。。。。。。。。。。。。。。。。。。。。。。。。。。
我交了至少 50 次 $98pts$。。。
一会儿 WA37 一会儿 WA38 一会儿 WA41。。。
满脸写着 mmp。
最后我彻底裂开了，就自己指定随机种子，最后把两个种子拼一起在结束前 30min 才 A 掉。
**C 题一共交了 87 次！！**
心态完全爆炸，感觉自己被降智得厉害。应该是自己太急了，希望明天状态能好一点。
**中国队A组 17 个人有 12 个人 AK。**（我是倒数第 2 个 AK 的，没脸了。）
djq 神仙用了 48min 就 AK 了。 stO djq Orz。
C 题正解是 $\mathcal{O(n^2\log n)}$ （现在我还没搞懂怎么做呢。。）
晚上把前两道题的数据造了造。（我人生中第一次 spj。）
---
# Day 4 （Round 2）
~~还是有点慌。~~
A 是个又是憨憨结论题，直接输出 $\left\lfloor\sqrt{\min\{a_1,a_2\}+\min \{a_3,a_4\}}\right\rfloor$ 即可。
坑人的是用 `sqrt` 函数之后还要微调，否则会被卡精度卡到 $90pts$。
B 来个憨憨 dp 题，10min 码完，交上去 WA 了？！
又读了两遍题目，还写了个 gen，最终发现我才是憨憨，又是手滑。半个小时已经过去了。
希望 C题 比昨天良心一点。。
### 希望破灭，这场 C 题更加降智！！
奇怪的分类讨论细节题。。
先 rush 一波，然后 WA。（意料之中）
手捏了七八个小数据，WA 了N多发，终于把所有错误都调出来了。
$48pts\rightarrow 92pts\rightarrow 96pts\rightarrow 100pts$。
还算顺利，虽然调了 1h，但还是提前 1.5h 锕氪了。
stO djq 1h1min 锕氪。
stO ntf 1h14min 锕氪。
#### 本无同竞！
**最后中国队 14 人锕氪，而我又是倒数qwq。** ~~（今天还有个俄罗斯人锕氪了？震撼！）~~
晚上把三道题的数据全都造了（C题数据真tm难造。。）
---
# Day 5 （Round 3）
紧张.jpg
A 依旧憨憨，弄个前缀和即可，秒掉。
然后评测机 crash 了。。。（原因是数据出锅了）教练就让我们先往后做。晕。
B 一看平衡树裸题，直接上 $\mathrm{FHQ\ Treap}$，rush 一波，然后就过了。（赛后 djq 分享了一下他的神仙线段树做法。）
C 题看起来肥肠的神仙，然后我更神仙，没看见题面上写的段数 $\leq5$ 的限制。
想了一个肥肠复杂的做法，此时 ntf 已经 AK 了，我顿时有点慌了神。（啊，原来这就是神仙！）
思路挺清晰的，直接在 Trie 树上找区间然后扫描线，感觉写起来好麻烦。不管了，开始码！
码码码，**码了 3h，码了 6k**，中途想要放弃，但是最后还是写完了（我当时就好奇 ntf 为毛写那么快。）
还要我大海捞针，没调多久就把一个 **6k** 的代码调出来了。
AK 以后生无可恋了，第一次考试的时候写这么长的代码。。
还是倒数第二个 AK 的，我菜是原罪，嘤嘤嘤。
赛后 ntf 和 zyk 告诉我直接 hash+map ，代码 1k 不到。
嘤嘤嘤，肿么 **段数 $\leq5$** 啊啊啊啊。
我顿时炸开。（不过好像 djq 和我的做法一样/cy）
无论怎样，总算 AK 了。
感觉难度每天在递减，**今天中国队一共 15 人 AK**。还有两个俄国人也 AK 了，奶一口明天 3 个歪果仁 AK？（雾
C 题我准备造了加强版，放心不会鸽子的！！！（恼
---
# Day 6（Round 4）
最自闭的一场。
因为恶臭的主办方拉了 IOI 原题。
>A: [IOI2007 D1T2](https://www.luogu.com.cn/problem/P4646)
>B: [IOI2007 D1T3](https://www.luogu.com.cn/problem/P4647)
>C: IOI2006 D2T2 (目前luogu上没有，不过可以去官网上找)
A 题打破了常规，变成了个神仙题。
不过没多久我就发现把平面图转对偶图一下就完事了，然鹅我不会转，所以就先扔一边了。
B 题就肥肠可做了，想了个朴素的贪心交一发就有 $55pts$ 了，然后用平衡树随便维护一下大约在 1h 的时候就过了。
C 题一脸不可做，就又转 A 了。
不会转对偶图啊嘤嘤嘤，~~最后无奈开个小窗网上剽了个板子~~，魔改一下，疯狂 WA 成 $55pts$ ？？
还剩最后半个多小时的时候发现图还可以不连通？！太毒瘤了，不过过了之后就很舒适了，由于有订正赛所以 C 做不出来也没关系了。
最后乱写了个还骗了 $24pts$。
最终 xtq，djq，crn 三人 AK，我排 rank 4。虽然没有 AK，但是排名还是很好的。（毕竟题目很难）
老师组织了一下讲解，发现 C 并没有想象中那么难，订正赛的时候就切了（算分的时候还是和 AK 一个得分的/cy）。
感觉还好。
---
# Day 7（Round 5）
今天感觉太累了，上午就睡了 3 次觉。希望下午不会萎掉。
炒鸡紧张.jpg
开题。
咦，这个 A 怎么似曾相识？
咦，这个 B 怎么似曾相识？
咦，这个 C 怎么似曾相识？
这 tm 不是作业（eJOI）么？？！！
>A：[eJOI2017 D](https://www.luogu.com.cn/problem/P6291)
>B：[eJOI2017 E](https://www.luogu.com.cn/problem/P6293)
>C：[eJOI2017 F](https://www.luogu.com.cn/problem/P6294)
i了i了，这场就看你有木有好好写作业了。
55min AK。
中国队一共 14 人 AK。
是时候再宣传一波 [做题总结](https://www.luogu.com.cn/blog/1445353309froggy/ejoi-zuo-ti-zong-jie) 了 /cy。
~~zyk 好像因为没写作业这场凉凉了。~~
---
# Day 8（Math Tournament）
### [题目](https://www.luogu.com.cn/paste/j7kklnvx)（blog 里无法显示表格所以就放剪贴板上了）
### 比赛经历+题解？
虽然只有 2h，但是能写 cpp 就方便许多了。
而且是 IOI 赛制？？！！不过只能提交 $3$ 次。
T1 相信是个人都会，直接输出 $\lfloor (6^2-4^2)\pi\rfloor$。
T2 相信是个人都会，答案：$(3,3)$。
T3 直接拿[几何欧拉公式](https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%85%AC%E5%BC%8F/92066?fr=aladdin)算一下就好了。答案：$30$。
T4 懒得算，直接敲个 $\mathcal{O}(n^2)$ 的 dp （当然爆搜也可）就好了，答案：$162$。
T5 考察 `for` 循环的使用（雾），答案：$44$。
T6 注意到 $\sqrt[3]{x}=x^{\frac{1}{3}}$，左边可以表示成 $x^a$ 的形式，显然 $a$ 无限趋近于 $1$，所以答案就是 $100$。
吐槽：T6 出题人没写省略号，想要当场做出此题必须与出题人心意相通。
T7：不太会下国际象棋嘤嘤嘤，不过用那个网站（题面上的那个链接），自己跟自己下，每个可以走的点都试一下就出来了（大雾）。答案是 $\mathrm{G6}\rightarrow \mathrm{C6}$。
T8：不知道有木有大师能手推出来？写个 bfs/迭代加深 就完事了。答案：$14$。
T9：懒得算了所以就 `next_permutation` 一下，答案就是 $3999960$。
T10：$x_1$ 一定在分子，$x_2$ 一定在分母，剩下的随便，答案就是 $2^{10-2}=256$。
T11：不会，希望有神仙教教我这个菜蛙。其他各路神仙有写程序的，但是 GG 了。（这程序难写死了。。）
T12：原题面没写点不能重复经过，~~这时候就需要和出题人心意相通。~~
所以交了 $3$ 发 “正解” 都 WA 了，彻底吐了。
答案：$1\rightarrow6\rightarrow11\rightarrow16\rightarrow12\rightarrow3\rightarrow2\rightarrow9\rightarrow13\rightarrow10\rightarrow7\rightarrow4\rightarrow8\rightarrow15\rightarrow14\rightarrow5$。
最后我只 A 了 $\mathrm{T1}\sim \mathrm{T10}$，并列 rank11。（有个俄罗斯人竟然 AK 了！本无同竞。）
考完有点裂开。。。
明天杯赛加油吧！！
---
# Day 9（Cup）
给自己说这 ISIJ 并不是很重要，然后就没有那么紧张了。（雾
4 道题目的分数比较鬼畜，是：$120+120+100+134$。
我也不知道我怎么想的就先开了 B，不会，再看一眼 C，有趣的串串题，但是感觉没那么简单，又扔了。这时候 xtq 已经切 A 了，我赶紧拐回去看 A。
发现是个憨憨贪心，但是细节很恶心，需要用点几何知识。
用相似搞了搞感觉很对就开始码了，然后果不其然 WA 了。
开始手造小数据调，调到最后发现 `x` 和 `y` 打反了 （捂脸。
过掉 A 的时候快 1h 了，有人已经过了 T2，我更加慌了。
快速码个暴力然后打表找规律，找了两个假规律，交上去 WA WA 乱叫。
最后终于找对了但是感觉要写高精度（没想到还可以取对数）就弃疗了，$110pts$ 滚粗。赛后发现 B 和 [这题](https://www.luogu.com.cn/problem/P1128) 几乎完全一样，zbl。
然后开始淦 C 的暴力。直接码个 SAM + 线段树合并，WA 惨了。
调了半天发现由于我是在线回答询问的所以线段树合并的时候需要新开节点，还是自己没把线段树合并学好啊，晕。
过了 C 的 $60pts$，只剩 1h 多一点了，目前 rank15+，感觉要跟 Au 说再见了。
剩下准备全面淦 D，说不定能翻盘。
啊这个 D 就输入一位数，但是是 $10^{10^5}$ 级别的，感觉有点 NB。这时候已经有人的 D 拿到了 $70+$ 的高分。
突然间灵光一现，想到了一个拓扑排序的 $\mathcal{O}(n\log n)$ 做法。能拿多少分听天由命吧，$n$ 的范围为这么大感觉也拿不了多少分QAQ。
写写写，调调调，WA WA WA，可能脑子有点浑，导致调不太动，但我强制使我保持冷静，最终在结束前 5min 调出来了，交一发竟然得了 $70pts$ ？！然后就翻盘进前 10 了？！
剩下的时间一直在看榜，**亲眼目睹 ntf 翻盘翻进 rank 2 然后吊打 djq**，我有被吓到。我就比较逊了，rank 8 滚粗。
---
# Day 10 （closing）
下午紧急通知闭幕仪式提前到晚上 $6:00$ 了。
两个人唱了半天二人转，还是一句嘤语一句俄语，全程只听懂了 IOI，IOI，IOI…… （估计又是在打什么广告）
实际 A 组 Au 数量比预想的多很多，有 14 个。可笑的是我就算没翻盘也是 Au （笑。
最后我全球 rank 8，A 组 rank 7，综合全球 rank 4 滚粗。
**无论如何最后 Au 了。** /cy
zyk 虽然考炸了但还是卡线 Au，感觉他可以去买彩票了。
stO xtq Orz 捧杯，（然后主办方还把名字打错了，打成了 `Xu Tinghang`，xswl。）
stO ntf Orz rank 2，综合 rank 1，本无同竞。
晚上官网就出公告了，佩服 CCF 的效率。（不过人脸网上乱剽，素质够高！）
---
# Day 11
还有不到 1 week 就中考了，滚回去学万恶的 whk 去了。QAQ。
大家祝我中考顺利吧。/qq