CTT 2023 游记

Posted on Disqus:

大部分是手机打的，可能有些错字。

萌新刚学 oi，第一次来 ctt（

提前一天入住，同校的三人在不同的房间，前台说查不到室友是谁，然后 Day1 一直到下午都没有人来，前台打电话说只定了一天，让我咨询会务组（）

然后过一会 crescent 来了（）

看起来是出现了一点失误然后就直接把两个人 merge 了。

下午去了 CCF 总部，看到门口巨大的 CCF 标志感觉很震撼（

酒店&早饭看起来很厉害的样子。

Day1

之前咨询了 cage 得知难度是乱序，但看到题感觉 T1 最可做于是就先开了 T1，mi mx\verb|mi|\ \verb|mx| 一定有一个经过的先后次序那么一定是有一边不用考虑的，而因为每条边最多被覆盖两次，所以另一边把有交的段合并后一定是终点前边若干段被覆盖三遍以让空隙只被覆盖一遍，而剩下的后缀直接被覆盖两遍，但感觉处理一些覆盖起点的段会有点细节于是先写了个 O(n2)O(n^2)，交上去 WA 了之后开始对拍，发现是少了一种全部覆盖两遍以上的比较平凡的情况，然后加了一些双指针、排序、和前缀和就过了（

然而此时已经过了将近 4 个小时,中间还修复了 T1 一定要有行末空格的问题，但我那时候连暴力都没写完所以没什么影响（

先看了 T3 但把代价看成小麦了，以为会了前两个 sub,于是写了个 dp 过不去样例，发现是绿宝石之后没想到代价依然是个关于收购价的常数，以为至少要二维 dp 于是就弃了（

开 T2 ，感觉直接搜剪一剪枝会跑的很快，于是写了个形似 dfs(l1,r1,l2,r2) 的记忆化，限制了另一段的长度之后就得了 75 分，感觉还能限制一下两端的深度，但已经没时间了（

100+75+0，rk 55

AK 了 10 多个人，但其实我觉得如果我看出代价是常数也做不出来（

下午的社会活动是参观楼下一个三个屋子大小的展览馆，于是 10 多分钟之后大部分人就上去打桌游了（

之前没打过这么长赛程的比赛，突然想到如果前几天打的特别差那后来会不会打的很绝望啊（

Day2

前一天晚上说过之后还真出了构造，还在 T1，发现目标就是让起始和终止状态每行棋子数一样，如果没有左右对齐那是平凡的，如果有的话那一定有一行变成了一个前缀/后缀 1，容易通过翻转行/列减少讨论的情况，而这个前缀一定可以是最长的前缀 ≥\ge 1，而剩下的位置也一定不能有 2 ，只剩一些有 1 的位置需要在另一行填充再发现棋子和空位是对称的，所以棋子数小于等于 n 的 sub 实际上没用，于是只需要分类讨论另一行被没被对齐过，被对齐过一定两行和在一起最优，把上面要填充的位置按照 max⁡(i,n−i)\max(i,n-i) 排序即可，另一行没有对齐的情况只是多了一些位置要放下来，类似做即可。

然后交上去 WA，在本地对拍也是改一次又出现新的错，对自己的算法越来越没有自信（在加了一个上边要填的位置如果下边一开始就有的话就直接交换的策略之后本地仍然过不去拍，但交上去发现过了就没再管（

这个时候大概过了 3 小时，起码比 Day1 有进步！

看 T3 发现一分不会， mod  264\bmod\ 2^{64} 复合可能有什么性质但我完全不知道 /ll

T2 发现固定中间那个后就是数一个序列的前缀和一个序列的后缀的有序点对个数，那么 O(n2)O(n^2) 和 O(nV)O(nV) 都是容易的，想了想发现可以莫队，但用线段树实现的话即使加了奇偶优化也就比暴力多了 10 分，在最后 30min 想到了可以用树状数组，拼到了 70pts。

100+70+0，rk 20

讲题的时候 T2 是莫队二次离线是没想到的，还以为是什么更厉害的东西

下午的社会活动就完全是桌游了（

Day 3

早上听别人说一种绿色的果汁很好喝，发现叫做是一种叫做“排毒果汁”，含有黄瓜和苦瓜，作用有解毒和开胃的果汁（但感觉都摆出来了就不会太难喝，于是拿了一瓶。

实际上嘛，嗯，有一种蔬菜汁的感觉，没有想象中那么难喝但也绝对不想再喝了（

来收杯子的服务员问我味道怎么样，我说：有点奇怪 /fn（

看到 T1 感觉很熟悉，发现好像是 cf 做过类似 k=1k=1 的东西，写了输出 n==1?1:2 的东西得了 20 分，然而是 sub 配错了，在一个小时左右的时候被重测了 QAQ

从原排列的逆排列考虑的话一个前缀出现过的条件是它们的位置构成一个连续段，而交换就相当于交换两个位置在不在前缀里，于是从原序列上考虑如果目前连续段 ≥4\ge4 就没救了，=3=3 当且仅当左边或者右边长度为 1 的时候有唯一一种交换方式合法，=2=2 的话讨论一下两边长度为不为 1 即可，如果为 1 的话那就是所有两边都在段里或者都不在段里的都合法。

除了被最后一种情况影响到的连续段都只有 O(n)O(n) 种，而最后一种情况的连续段也一定是不断扩展的，设一共有 s 段，每个位置第一次被覆盖的时间是 tit_i 那 (i,j)(i,j) 被覆盖的次数就是 s−(ti−tj)s-(t_i-t_j)，统计 numj=∑[ti=j]num_j=\sum [t_i=j] ，那统计出每种被覆盖次数的段数就是一个差卷积的形式，但心被卡常/卡精就先写了个 O(n2)O(n^2) ，时候肉眼 debug 发现了一个的段数 =2=2 时的细节错误，然后补了个 FFT 上去就过了（

这个时候大概过了 2 个半小时。

T2 没什么思路于是先开的 T3，一开始打了打表认为充要条件是奇偶位和相等，这样就可以把所有前缀和塞到状态里，但基于这个的 dp WA 了，于是找了找反例，然后基于求最大独立集的方法猜测如果正负交错的前缀和在某个位置 <0<0 那么后边有奇偶相等的也无所谓，然后之后压一压状态，首先发现把所有前缀和绝对值 ≥m\ge m 的都扔掉也无所谓，其次发现前缀和 <0<0 的因为后面无论如何都合法所以直接扔掉就行，这样状态就是 2m2^m 的了，这样就得了 80pts，继续优化无果后就去写了 T2 的暴力（并且在中途忘了左移是往哪面移并通过 __left_shift 找到了答案（

100+15+80，rk 29

终于每道题都有分了（

因为 T1 正常被降权重了，变成了 如果 Day4 没有锅的话 14 14 11 11，但个人感觉这场的问题没那么大（

社会活动是参观金砖博物馆，感觉实物还是很厉害的（

Day4

早上喝了西柚汁，感觉是这几天来最好喝的一种！

先看 T1 感觉把所有长度不为 1 的连续段合一起后就是反悔贪心，于是就先没写（事实证明这个决策很正确，之后又发了 t1 m=1m=1 有问题的公告于是就接着做 T2 了，宣布数据修复后场内出现了很多“嗯？”的声音，紧接着有人说 T1 把 std 发下来了（这个时候我认为这场权重是 0 了 QwQ，毕竟你怎么做也补偿不了做 T1 的选手，然而初步决定是只按后两题算分，这样感觉区分度会被拉到很大（

T2 一开始没想明白子图是什么意思，但好像对于这道题都等价于边取子集，然后最小生成树的条件就是不在上面的边比路径上的每一条边都要大，那一条边的限制就是小于等于它的边构成的点双中的所有的边，显然构成一棵树（其实一开始想成了边双，然后在草稿纸上画了“两个连起来的四元环”后想到了反例（

于是直接做就是 O(nm)O(nm) 的，但对于圆方树有影响的边只有 O(n)O(n) 条，于是容易 O(n2)O(n^2) 再想想其实等价于每次合并最小生成树两个点之间的路径，容易并查集优化。

这时候大概还剩两个多小时，感觉这样 T3 就很重要了，但 T3 除了 sub1 一直想不到什么有价值的做法，想到了一个分治但是询问次数没有保证而且恢复边的次数也不太对（

于是最后只写了个暴力（

100+14.5，rk 49

赛后听 LHF 讲了个比较简单的基于 n2n^2 次询问的随机化。

一个有意思的事是在我在开场时在草稿纸上写下了 14 14 8 14，然后在 T1 出锅了之后补上了 17 17 8 8，没想到真猜对了（

因为对 10 级知识点不太熟于是期望不是很高，这个排名看起来还不错（？

rk 37/100

关于这场比赛的锅，其实从这 50 人中随 30 个人出来不管对 IOI 的结果还是对选手的人生是不是也不会有什么改变，所以对组织方来说这真的有必要是一场非常严肃的比赛吗。

那该怎么让出题人对选手做到感同身受呢。