CTSC/APIO 2018 接着爆零记。
（爆零三连。。。）
【数据删除】
May 6th - Day 0
前往 PEK，G20 列车好的呀。复兴号 350km/h 好的呀。
( 然而之后的东西不怎么好。。。)
随机分配房间（似乎按照报名表？）
两个人挤~~（gay）~~在单人间。
话说有些人能睡双人间。。。（真 人品竞赛）
不知道 CCF 在搞些什么名堂。。。能退半个房间的钱吗。。。
到北京 12:30，坐地铁（噪声好大）到酒店 1 点半多，拿到房间快两点半了。赶紧（跑好远的路）去吃饭，然后试机。
感觉键盘还行。去每个试场溜达了一圈之后突然想起 gdb 的事情（见ZJOI2018 Round2）（听说 NOI 系列比赛会先 apt update && apt upgrade 一下），冲进一个试场试了一下，确实 gdb 的锅修好了。（ZJ 特派员就是不会用 NOI Linux）
成就：两个半小时吃两顿饭。
（宾馆网好差。。。）
（话说八十中的环境和硬件设施好好哦，饭的种类也很多样）
May 7th - Day 1 (Contest Day)
开题。T1 题面好长，怎么占了一半。。。
T1 看完题面（好久才发现原来第二个操作只是询问。。。）发现期望值只要背包一下（和 0 取 max 好麻烦）。推了询问的 DP（），发现可以先把考虑所有点的 DP 值求出， 去除一个的贡献（反向转移）。1h 多一点写完。挺好的签到题（但是依然有许多人没签上到。NOIP 以上的比赛经常如此）
T2 似乎按题面算法模拟就有很多分，LCA 变成 有 45 分。链好像不会写。先看 T3。
T3 数数题，有点不会。看看部分分， 很好推， 死活推不出（后来得知这就是本题最难的地方）。先写前面 10 分暴力
然后回来打 T2 暴力。
还有好久。。。开始四处找分。
T3 的暴力没有打，赶紧写一个预处理。
T2 很有某锟的风格，很像 WC T1（考前立过 flag，碰到他的题一定要写乱搞），来写一个随机。想了一下链的情况，加了计算 1 号点到各个点的答案，叶子节点到各个点的答案。
以上做完还有 40 分钟。
仔细看题面，T2 可以 ，补上。（似乎有人因为这个没考虑 FST 了少部分点）
然后检查了若干遍文件。调了一下参数。然后坐等考试结束。
吃完中饭，坐等评测结束。wzz 连着 5 轮 21 点。。。
评测结果蜜汁 Delay 1h。
100+65+25=190。T2 后面边权 >0 的点多过了 4 个。（话说我校似乎没几个人写乱搞的。）
（大家出成绩前分析了一波，觉得有负权乱搞过不去的。。。其实我也一个负权都没过。。。）
然而到讲题的时候，发现我的乱搞还是 naive。使用 WC 上的（高级）乱搞得分可以在 95 ～ 100。甚至其它近似化算法都可以得到 90 分。
（其实大家都做好了被卡的准备，但是就是没有卡掉。。。）
听说候选队区分度堪忧。。
确实今天的题 T1 签到，T2 乱搞出奇迹（半年内 2 道相似的题目用相似的乱搞。。。），T3 题目倒挺不错的（然而是 OEIS 原题。。。）
（听说 T2 有白色字体的刮刮乐？）
嗯，就是这样。。。
晚上各种手残，乱删考试时的源代码，正在恢复中。。。
Day1 分数看起来至少没有亏，Day2 继续努力吧。
May 8th - Day 2
上午候选队论（神）文（仙）答（打）辩（架），只能算凑热闹：
你这不符合汉语的表达
你讲的 DFT 和 wys 讲的 DFT 有什么区别（OIer 对电音物理和信号处理不大感兴趣）
莫队算法不是什么常见的算法。
你们写的论文要让初学者能看懂
（Day2 有提答题？！）
下午离场率 $ > 60 %$，首先是某 MIX LAB 来打广告，介绍了他们在做的事情。接着是流氓软件360 的安全工程师介绍 AI 与安全。
（假定我们是八十中的学生。。。）
有几点挺有启发的：
原来爆栈也是不做越界检查的，是因为爆栈后的内存空间非法才导致 segmentation fault 的。（如果不非法就可以搞事情了。。。）
在工程上也要 hack 人。也是随机造数据叉。（使用遗传算法造数据。。。覆盖越多 case 的估价越高）
网络安全竞赛不懂。。。
晚上测了一下 T2，发现就是最后加的计算 1 号点和叶子节点得了 20 分。（话说换了乱搞姿势变成了 80 分。WC 上的标准乱搞长啥样呀。。。）
May 9th - Day3 (Contest Day 2)
下午事情太多了，先讲早上的事情：
先吐槽电脑。时间不对，修改要管理员权限，被搞晕不知道几次，gdb 好像又残了。。。
（实际上 gdb 没残掉的电脑可能就是出锅的考场。。。）
开题先看提答题。（先怼着样例手玩了一分钟。。。）写了暴力和随机，好像效果不是很好， 怎么跑了这么久。。。（实际上，跑到比赛结束估计都跑不完。。。），怎么非标准答案只有 2,3 分。。。
一个多小时过去了。。。好像只有 20 多分。。。（现在回想起来，感觉我当时已经不知道时间了。。搞不清看的是电脑上快 20 分钟的表，还是墙上正确的表）
开始看 T1。
第一眼可以二分，二分完了（一开始想建网络流。。。），只要按价格从小到大排序，贪心就可以了（再加一个前缀和 + 二分）。目前是
后来想到遥远的论文集中有一个叫整体二分的东西，不知道有没有用，先写了再说。一遍过样例，结果大样例 T 飞。冷静分析发现排序要从中点到序列末尾，总的是 的。。。
把排序变成线段树维护 + 二分，区间右侧的信息不删除。总复杂度 ( 反正 同阶。。。)
11 点调完（线段树各种写错。。。）写了对拍，又各种写错。。。
这道签到题比 Day1 签到题的难度稍微正常了点。。。
感觉时间来不及，赶紧看 T2。
真正的猫锟题。。。Tommy。。。一脸来不及，不管复杂度，写一个 的东西。。。（这样的题目不好乱搞了吧。。。）
赶紧回来看 T3。。。鉴于随机只有十几分，第二个点暴力跑不出，开始观察性质。
第 6 个点好像运算代价远大于传输代价，输出运算代价的较小值，居然 A 了。同样的方法，又将两三个点的分数增加了 1 分。
然后看第 3 个点（DAG 为空，只有 3 台机子）。写了一个 的 DP 输出方案，不知道哪里写错了。。。
然后实在忍不了第二个点的效率，开始手玩，从 123/120（out/std）开始（就是前面的方法），怼着输入随机修改，都找不到。最后不知道怎么把最后一个 7 改成 6 就过了。。。（话说这时我才发现随机程序已经跑出来了。。。）
回来看第 3 个点，重构了一遍 DP 过程，居然过了。。。（现在重新盯了一遍，发现记录方案写错了。。。）
这时还剩十几分钟，感觉写不动了。查了一遍输入输出，快速地吃完点心，差不多就结束了。
最后 T3 连写带 rand 和手玩 : 10+10+10+2+2+10+2+3+2+1=52
好像好多人 T3 70+。
等成绩 <!— 看坎巴拉（小绿人摧残计划） —>。。。
100+0+52=152。猫锟为什么不把暴力范围改小呢。。。我只是没有加剪枝。。。（话说 zzy 的假算法 70。。。结论：猫锟 4 次出题（THUWC，WC，九省联考，CTSC），3 次被 zzy 乱搞，1 次 zzy 没参加。。。）
到礼堂等讲课。等到 4 点没人来，之后大家都在讨论咕咕咕的事情，听说楼上的机房还没公布成绩。还听说有程序丢失的现象。。。
一直咕到 5 点，终于一群专家走了进来，直接切掉讲题，进入激动人心的6 进 4 面试。
（选手们的英语口语水平相差悬殊。。。）
你们长郡中学为什么这么多年都没有出过成绩
那么就是我们的错了（不用 IOI 赛制）？（提到某选手因非 IOI 赛制 FST 一题而退役）
你为什么不感谢 CCF？（提到感谢家长，学校，同学之后） （花絮：半小时前大家还在批判 CCF 变成咕咕 F）
你们（南京）外国语学校外语一定很好
我知道你不会韩语，我就刁难你一下。
（愣是听出任校长面试的感觉。。。）
晚上确定咕掉了，要到 APIO 才能颁奖。（听说程序被咕掉的选手要重赛，那怎么评奖？）
（作为前两天刚刚进行恢复文件操作的人表示，怎么程序会不见的？恢复一下很大可能能回来呀）
（所以 wys 上台是来干什么的，真的要将超声波电音进行到底吗？）
APIO 的练习赛。IOI 赛制，话说 UI 好丑呀。
May 10th - Day 4
早上很晚起来（8 点），出去走了 20 分钟路去吃早餐，回来还在处理网络问题，突然打电话说换房间。。。
下楼等了若干个两分钟后（中间还开了一次会），终于换到了房间。小床房终于变成了大床房。。。
（听说今天早上 Day3 考 Day2 原题？这不是全场 AK 的节奏。。。）
下午一直在折腾虚拟机。
May 11th - Day 5
早上第一节是二分专题。第一次听说 wqs 二分（或称凸优化二分）。针对一类物品需要选 个的情形。给这种物品增加额外代价并二分这个额外代价，显然随着额外代价的增加，最优方案中选的这类物品数量的变化是单调的。那么我们可以二分出选 个时的额外代价，然后在答案中减去即可。唯一需要注意的是注意处理物品数量的 sudden change（即出现可选可不选的情况）。
第二节课是图的匹配。证明了增广路算法和带花树算法的正确性（以及三分图匹配的理论。。。）。虽然就是这么一个意思，但我总觉得带花树算法好难写呀。。。
（上午讲课挺清真的。。。）
下午第一节是神奇的折纸算法。从头开始掉线，各种 NPC/NP-Hard 问题。。然后介绍了 ASSP 的 O(\frac{n ^ 3}{2 ^ \sqrt{\log n}}) 理论成果。（不如写 floyd）
第二节课是神奇的图像~~（角点检测）~~和 AI 算法。挺 233 的，线性方程组可以迭代求近似解。图像处理的水平好高深啊。搜索的理论不错（有一部分 WC 讲过，但没听懂），THU 的 AI 竞赛好高级呀。讲课人突然打开游戏。。。
NOILinux 没有 c++14，希望除了 gets() 以外没有其它 major change。
居然考场离开图书馆，来到了出锅考场，好害怕呀，我不想考 APIO Day2。。。
May 12th - Day 6 (Contest Day 3)
APIO。
开题发现 T1 显然的数据结构。然后就马上开始试图推，然而未果。（中间看了 T2，T3，一眼没发现 T3 的性质）。先交了前面 12 分。（这时 50 分钟过去了）
然后看了看 T2，感觉没有头绪，怎么优化找圆的交呀。。。
想不下去了，开始看 T3。好像跟点双有关，赶紧建圆方树（感谢猫锟的科技），类似树上的作法，只要分别考虑圆方树的叶节点和割点，推一下式子。然而一发式子推错，一发非连通写错，一发数组开小。
这时比赛还有一半多的时间。想先写 T2 的部分分，然后回去搞 T1。
结果第二个 Subtask 以为想出来了，最后叉掉卡 T 了。
然后在 T1 和 T2 中间徘徊了好久。。。T1 标算也没有想出来。。。
（实际上已经感觉和 +1 和 -1 的斜率直线有关，但没有细想，而且感觉实现极翔无比。。。）
最后只剩下一个小时了。没办法，只好写了 Subtask3。
22+7+100=129。看起来并不是个很好的分数。
（听说 T2 KDtree 或者其它乱搞能骗很多分？）
感觉后半段每个点都有一点思路，但都没有确切的解法。自从 A 了 T3 之后，脑中一片混沌。。。
May 13th - Day 7
上午讲的是个经典的主题：计算机系统（俗称松松松）
讲松松松还把松松松给批判一番（缓存优化是不科学的）
将一些卡常技巧明确了一下（主要是寄存器优化和循环展开。。。），有说明了一下关于数据范围，浮点数运算的注意事项。
居然会有垃圾编译器把 static 像局部数组那么开。。。但 static 确实挺好用的，怎么办。。。
下午讲 SAM，终于又理了一遍后缀自动机的神奇性质。而且发现自己还不会用那个 DAG。
（相对于 WC 和 ZJOI，APIO 的讲课好像更科普向）
晚上闭幕式。
松松松终于成为正式主持人了。。。
CTSC 的线涨到了 12%，好像从被线卡变成了卡线。
APIO 参赛人数再创新高。
APIO 的评测机运行稳定，俄罗斯方面一共有 76 台评测机，能够提供及时的反馈。
APIO 期间机器运行一切正常。
APIO 考了数据结构，几何，动态规划，但是实际上三道题本质上都是数据结构（如果把圆方树看做数据结构的话），说明数据结构是现在竞赛的趋势。
但是这次竞赛也有不足，俄罗斯方面竞赛准备不足，没有备选题，题面一直改导致我们没法印纸质题面，题目没有很好的区分度。（将锅全部推给俄罗斯）
然后开始颁奖。心疼主持人，读这么长的名单。（填海中学。。。）
CTSC 贴线 Au，APIO 似乎只要 A 题就有 Au。看起来也是一个不错的结果。（好像吊打集训队了）
最后，感谢 CCF。
（听说 THUPC8 题手速场。。。）
May 14th - 总结和随想
为期一周多的 CTSC 和 APIO 结束了。
从成绩上来看，这确实是一个不错的成绩。但是，我也发现了，CTSC 主要的得分贡献在了两道 T1 签到题上，而真正把分数拉上来的好像是 D1T2 的 20 分乱搞分（提答题也有贡献）。（我个人感觉暴力分应该在 100+45+25+100+0+35=305 左右，是一个非常稳的 Ag），至于如果遇上了省选这样没有这么多暴力分的比赛，那就 GG 了。这就说明在保证基础分之后向高分走对于我来说就显得有些困难。
至于 D2 是否应该搞提答题，现在想想，好像也只能这样做。实际上 T2 不存在“最裸的暴力”，必须要一些剪枝才能过。当然，做提答题以后不能再 rand() 了，要观察数据性质。（当然，还要学一下模拟退火等算法（逃））
至于 APIO 的话，KD-tree 不会就是不会，没有办法；至于 T1 的数据结构，也是思维，包括考试状态上的不足。在 A 了 T3 之后，就急于想 T2 的特殊性质点和 T1 的标算。最后两个都没有出来，导致后面两个小时的混乱。所以以后可能要更有侧重一些。
以下是一些观察和随想：
关于北京：一直感觉北京人从北京话开始就自带一种热情好客的调子，这次加深了我对这个观点的印象。（可能这个想法的来源是来自《家有儿女》）
关于八十中：我们所在的望京校区听说是新校区，但好像也应该投入使用有一段时间了。但整一个硬件环境感觉都非常 high-level。（当然，南门的保安也是非常神奇的），最神奇的是，学生们居然可以 freely 地使用手机，这在 HZ 的大部分学校都是不敢想的吧。
关于 CCF：不做过多评价，但是依然要感谢 CCF。但是 NOI Linux 应该升级了，Ubuntu 都已经 18.04 了，总该升级到 16.04 了吧。（这次的版本甚至连计算器都没有。。。）
关于 Music：从雅礼到八十中，每逢休息时间，总能从某个角落传来钢琴声。也总能吸引一群人的围观。毕竟许多人都是考过十级的，弹出来的曲子也非常好。当然 OI 和钢琴有一点共通：都需要灵巧的手指（雾）。在赞叹和 %%% 的同时，也有人感叹“为什么 dalao 们都有时间练琴呢？”其实 OI 和钢琴也有另一点共通：都需要艰苦的努力。But indeed, it is really a good time to listen to dalao playing piano.
其他：珀丽（第一个字念 po）有许多外国友人下榻，但是为什么这么对待我们呢？ <!— 松松松【数据删除】了。—>
在回杭的高铁上（感觉和谐号还是比不上复兴号。。。）。6 月份还有两场大仗：THUSC 和学考。继续加油吧！
