NOIP & CTT (& THUPC) 2020

ix35 · 2020-12-02 21:49:59 · 个人记录

正好联赛结束就是北大集训，之后还有线上的清华校赛，可能就一起写掉了。

从 11.30 开始停课，12.12 后回归。

感觉最近一段时间状态不是最好（北大集训联测几乎场场翻车，出过没调完题 200\to 40 这种事），也不知道会考成什么样。

11.30\ (\text{Day } -4)

主要就上午打了一场 CTT 的联测，结果炸惨了，因为一些奇怪的原因学习了电学知识。

比赛结束后 15\min 内拿了赛时分数的 4 倍分数...

12.1\ (\text{Day } -3)

打了场怪里怪气的 NOIP 模拟赛，就一道弱题没做出来，日常。

12.2\ (\text{Day } -2)

由于这次 CTT 模拟的题是我们出（搬）的所以没打。

打了两场 NOIP 模拟赛，好多数学题，不过订正起来舒服。

中午一看发现我们的题被 A 穿了，不过应该是预料之中的。

12.3\ (\text{Day } -1)

一天太容易水过去了，忘了今天有联测。

12.4\ (\text{Day } 0)

一天太容易水过去了。

12.5\ (\text{Day } 1)

暂时留坑，反正打得很炸，等 CTT 结束了再写。

现在心情好了点，就开始写吧。

这次主要是吸取了上次 CSP 的一些经验吧，上次看完了题基本全想完了才写，而且是从后往前写，不太妥当，虽然因为那次自认为题不难，但是这次应该不能再这样莽。

8:30

这次发密码的服务非常到位，是“选手加油”，非常清楚。

开场先看 T1，发现是个弱智题，根据赛前想的策略，直接开写。

写到 8:45 就写完了，当时其实并没有太注意该不该开高精度，因为题目中一堆限制条件摆明了就告诉你只要 long long 就够了，而且后来推了一下发现 2^{20}\times 3^{10}\times 5^{10} 并不超过 long long 范围，没想到出题人阴间。

8:50

看了下 T2 感觉题面长得很奇怪（？），就把后面三题都看了，当时的想法是这 T2 和 T3 应该都能做出来，T4 可以水一点分。

然后定睛一看这个 T2，第一步是排除不重要信息，当时我看来这个出现奇数次的字符就是一个用处不大的条件，所以先忽略掉了。

随后容易发现形如 \text{AAAAAAAB} 的拆分在枚举 A 的长度和数量可以做到 O(n\ln n)，据此加上对题目中 A,C 数量的前缀和后缀和，就可以做到 O(n\ln n) 了。

然而忽略那个条件的特殊性似乎就是限制我复杂度不能更优的原因，事实上形如 \text{ABABABC} 的 C 中出现奇数次字符数量和 \text{ABC} 是一样的。

关于判定循环，我用了双哈希，当时想的是不写哈希可能必须要 SA 或者 Z 算法，原来朴素 KMP 就可以。

9:30

测了一下 T2 的最大规模数据，本机 1s 能过，不过不是全 A 的情况。

9:45

这把 \dfrac{1}{3} 的时间做掉了 \dfrac{1}{2} 的题，感觉还挺好的。

wtf，这个 T3 怎么没有部分分？

T3 首先是有个一眼的 nm^2 做法（可以花 m 的代价交换任意两个球），接下来又有个一眼的 kn^2m 的做法，一开始推出来的 k 大概是 [\dfrac{3}{2},2] 这个范围里，没任何用。

然后定睛一看，发现是有部分分的，只是题面锅了，不久之后就通知了。

自己玩了玩，半天也只有一个 n^2m 无常数的做法，于是又去看了一下 T4。

10:30

一个人在一轮内不走出去的活动范围一开始被我误判成一个高维凸包，随后冷静了一下才发现只是一个超长方体，因此每一维是独立的。

推了一下式子是个形如 \sum\limits_{i_1=1}^{w_1}\cdots\sum\limits_{i_k=1}^{w_k}\min(F_1(i_1),\ldots,F_k(i_k))，这个是经典的拆 \min，要做 \max(F_j(i_j)) 是很显然的。

随后发现总共的 F_j(i_j) 只有 \sum w_i 种，只要全求出来后扫描即可。

由于求的是 \sum\limits_{d}\Big(\sum\limits_{i_1=1}^{w_1}[F_1(i_1)\ge d]\Big)\cdots\Big(\sum\limits_{i_k=1}^{w_k}[F_k(i_k)\ge d]\Big)，需要排序还需要逆元，于是先写了个 sort 的版本，发现连大样例都要接近 1 秒，感觉不太行就改写了 1e6 一段的基数排序和线性逆元，跑得挺稳。

11:45

只有一个小时多一点了，不过感觉自己之前已经拿了 280 所以不太慌。

准备开始码 T3 我的做法时忽然发现自己不会 n=2，然后想到这不有个现成的大样例吗，一看大样例会了 n=2，又一看发现 n>2 也可以这么做而且巨好写，于是改写这种写法，还算顺利的过了样例。

12:30

开始检查，之前 Windows 下写的现在放到虚拟机里测，测完样例都没问题，开始手造极限数据，T1 觉得不知道还能造什么数据就没造，T2 的全 a 在虚拟机里 T 了但感觉还能接受，T4 一开始段错误吓了我一跳，然后发现是数据生成错了。

奇怪的部分来了，测 T3 的时候生成了个大数据结果告诉我方案不合法，有点慌，调到考试结束也没调出来（但是回家测试发现都是对的，可能单纯是自己数据又造错了）。

回来后不久发现自己 T2 炸了，可以卡到 0 分。

分数

总分是 300，好像是 90+60+70+80。

似乎还可以？挂的分并不算多。

虽然这个绝对分数看起来肯定不算好看，应该算是一个较低的分数，但感觉也尽力了，就这样吧。

12.7\ (北大集训 \text{Day } 0)

注：因为不明白题目公开度，恕我不能直接发题面。

前一天就来到了中关新园，这一天上午报道。

报道完过了一段时间就出去吃饭了，回来发现室友是铃酱（

下午一小时的开幕式开了二十分钟，然后一小时的试机试了 1.67 个小时。

试机题应该算是两个比较简单的题，但是因为想去吃饭所以写了 T2 以后没写完 T1 就走了，其实这个 T2 是我做过的第一道通讯题。

晚上水了很久的群。

12.8\ (北大集训 \text{Day } 1)

垫底场来了。

比较早就到场了，也没打任何板子，就是调了一下 IDE 的设置。

然后看题，题目真了不起，三道题里九个树。

首先是 T1，题目名字叫 shushushu，看了一眼感觉它是 sb 题，然后又看一眼感觉我是 sb 人。

然后是 T2，题目名字叫 shushushu，看了一眼感觉它是一个普通的数据结构。

最后是 T3，题目名字叫 shushushu，是个交互题，看完了啥都不会（本来以为交互题我可以做做）。

最后感觉 T1 还是最水，就打了一下，以前没打过 k 进制线性基这种东西，好家伙一打就是一个小时，又调了一个小时，结果只拿了 50 分。

然后又无能狂怒了一个小时，但是也调不出来问题在哪（关键是无法对拍，因为没有暴力的办法）。

感觉不能 50 分离场，又去开了 T2，半小时冲了一个复杂度带一堆 \log 的做法，结果爆零了。

然后又调了半个小时也没调出来，真就直接离场了。

标准分：250

感觉做题过程和本文开头描述的那场电学比赛十分相似。

下午听讲题，T1 果不其然就是我想的那个做法，但是似乎我辗转相除写的比较糟糕就没过掉。

T2 其实和我想的也差不多，但是有神奇技巧可以 1 个 \log。

T3 因为没思考过，听起来第一个点还是相当容易的。

然后 Day 1 就基本垫底了（六七十名），感觉我打过的几乎所有比赛都是 Day 1 打得远差于 Day 2...

12.9\ (北大集训 \text{Day } 2)

早上起得比较晚，大概 7:50 才到场。

由于昨天打得太过垃圾，所以还是很想翻一下的。

然后看题，题目也很了不起，看起来挺全面的（？）。

首先看 T1，1 min 过后发现是真正的 sb 题。

因为 T1 实在太太太简单了，所以我也没管另外两道题，花了 20 分钟写了个主席树就过了这题。

然后看 T2，懵逼了，好像一分不会。

最后看 T3，看上去应该是我比较擅长的图论领域，决定怼这题了。

分析了 1h，主要发现了一堆和竞赛图哈密顿路有关的结论，结合竞赛图 SCC 的结构，可以得到一个 O(n^3) 的做法。

当时的想法是对于不在哈密顿路上的边可以在找出哈密顿路后 O(n) 求，对于哈密顿上的边由于只有 n-1 条所以暴力搞。

接下来就是把两边都优化掉，首先是不在链上的边，通过哈密顿路可以把 SCC 的问题转化成区间并的问题，通过一些很 trivial 的操作就可以在 O(n^2) 预处理后 O(1) 回答一条边。

接下来是在链上的边，这里实在没什么办法，情急之下想到乱搞：找两条不相交的哈密顿路，那么一条路上的边可以在另一条路上算。

实际上不一定能找到，但是我写了一下结果就 AC 了。

最后看 T2，觉得只能做做 n\leq 3 的部分分，样例里送了 n=1 和 n=3，所以只要做 n=2 就可以了。

但是我实在实在是不会做，然后就准备利用 IOI 赛制，通过观察样例猜测两个结论：

1. 答案随 n 递增；

2. 答案分母是 (2n+1)!。

以 120 为分母，夹在 \dfrac{1}{3} 和 \dfrac{239}{420} 之间的分数并不多，一题可以提交 32 份代码，算了算是可以枚举出来的。

实际情况很不错，才交了第 7 次就过了。

标准分：300

似乎暂时翻盘成功了？

至于四场总分就算了吧，那个从第一场打完我就输了。

下午讲题，T1 果然是四天之内前无古人后无来者的最水之题，到场 90 人中只有 4 人没有 AC，1.5 分钟就讲完了。

T2 是数数神题，其实我想到了转坐标轴那一步，但是后面的积分就不太会拆。

T3 讲了一个“强连通竞赛图的哈密顿回路”，但是我只会求路径，讲的我都听懂了就是不懂怎么找回路。

讲完 T3 我上去吐了个槽，讲了一下我用了两条不交哈密顿路的做法，毕竟我能过说明数据不太强，出题人也说是随的......

12.10\ (北大集训 \text{Day } 3)

今天旁边坐的又是 dengyaotriangle（Day 1 也是），好座位表。

首先看 T1（编不出其他句式了），看了大概有五分钟没看出任何东西，然后就一题题往下开，T2 看了个大概，但是没得出什么具体的结论，T3 是个比较神的数据结构，应该不会在我的知识范围内。

然后还是决定先磕 T1，自闭一段时间后好像突然变聪明了，和逆序对有关还只有 300 的数据范围，让我考虑完预处理出的一个矩阵后就想到了行列式，通过简单的赋值可以求出所求值为偶数减去所求值为奇数的排列数量，再结合排列总共 n! 个，这题就做完了。

然后看 T2，我做 T2 的过程大概就是幸运猜猜猜。

首先猜了个结论：对于一个序列，如果最大值两侧的两个区间都是好的，而且最大值位置的奇偶性与最终位置相同，那么这个序列就是好的。

不过这个结论似乎有点小锅。

然后重新猜了个结论：对于一个序列，每次找到当前最大值，如果每次位置的奇偶性与最终位置奇偶性相同，那么这个序列就是好的。

这个好像是对的，打了个 O(n^3) 交了上去得了不少分。

之后又猜了个结论：答案有单调性。

于是我把枚举换成二分，复杂度 O(n^2\log^2 n)（用了树状数组），不过没过去 5000。

接下来没有猜，根据已有猜出的结论整合一下可以知道：一个序列是好的当且仅当每个位置后面比这个位置小的数的个数是偶数，于是可以去掉二分有个显然的 O(n^2\log n) 做法，写了一下过了 5000。

之后的问题看着像一个简单的数据结构，可惜好像并非如此，我直到比赛结束也不知道怎么优化。

大约最后 1.5 h 的时候，我决定先做 T3 后想 T2 的优化，这是因为 T3 把暴力打满大约有 60 分，超过了 T2 剩余的 40 分。

码了一个随机数据下也许是 O(n\log^2 n) 的常数巨大做法，结果交了一下只得了 25 分，有点悲伤。

然后发现是 n\leq 1000 的两个子任务没过，就又重新写了个 O(n^2) 暴力专门跑这个，调了很久很久，大概 11:55 才调出来，拿了 40 分。

标准分：240

今天打得应该说也不错，不过由于 Day 1 打得垃圾所以目前总排和后两天的情况还是不太匹配。