记游 4202TTC

· · 生活·游记

既然都交了这么多钱了，还是写一下吧。

Day 0

很早就得起床，赶火车。火车的位置是第一排最靠走廊的位置，导致前面没有小桌板，没法放电脑，只能 /shui。

中午到北京南站，做了 1h 地铁终于到了酒店，签到，入住，马上就去 thu 试机了。

thu 机房电脑有点大，分辨率很高，字很小，调了一下分辨率好受了一点。试机还是这三个题，中途忘了元旦激光炮咋做了，重新推了一下，35min ak。然后开始坐牢。发现这个电脑不是 noi linux，没有 /usr/bin/time，没法测动态内存 /oh。

随便敲了两个板子就开摆了。机房去报告厅中途要坐电梯，排了一百年的队，唐完了。开幕式就是几个领导讲了 eps 句话。晚饭是盒饭。回酒店，摆了一会儿大概十点半就睡觉了。

Day 1

前一天 fcc 还是谁说六点半就有早餐吃，导致定了六点的闹钟，六点半准时下去吃早餐，发现来早了，吃完七点没到，回房间摆了一会儿才下去坐车。

开题，T1 是一个神秘算期望题，一眼应该不是 poly 复杂度的，不急着做，T2 是个神秘数据结构，T3 是个神秘交互。

感觉 T3 很有头猪，先胡一个随机化做法，把 0 位置和 V 位置的值区间问出来，然后每次随机一个中间的位置二分，建出上界和下界的两个凸壳。询问次数用完之后直接找一条在这两个凸壳之间的直线即可。虽然正确性不知道，但是感觉至少能那一点分。

开写，突然发现不太会找两个凸壳之间的直线，编了一个二分斜率然后求非法点在最大值左侧还是右侧的做法，正确性感觉保真，但是二分分数得用 sbt，我并不会这个东西，只好先编一个钦定分母为 10^9，二分分子的做法。

这个东西并不好写，写 + 调了大概 1.5h 才把小样例过了，交上去不出所料 0 分。本地赶紧造了几个大一点的数据，发现根本过不去。搞完大概 2h 了，心想不行了，得开前面题去了。

想 T1，先套路地把期望拆开，每个位置选一个操作，每个操作合法的放置位置就是一段区间，很容易地编了一个 O(2^mn^2m) 的做法，分析一下大概有一个很小的常数，赶紧开始写，把前三个包过了，25 分。先放了。

然后开 T2，发现完全没有头猪，甚至连 m=0 都不会。突然想到是个流的状物，赶紧先写个费用流拿了 10 分，然后就开始疯狂分析性质尝试模拟费用流，还是无果。3h 了，总分只有 35 分，感觉要倒闭了。

再想 T3，发现仅仅用我随机撒出的这些位置根本没法确定这条直线，于是我开始着眼于解决 V\le 10^5 的包，也就是问出所有位置的区间。还是用刚才的那个做法，把原来的每次随机一个位置换成把 1\sim V-1 直接 shuffle 依次询问之后，本地的随机数据是可以通过的！赶紧交一发，0 分？？？修了一下 gen，把值域加大，发现过不去了，难道必须 sbt 二分吗？想着开始乱搞，随机分母，二分分子，本地能过，交了，20 分。感觉 T3 差不多了。

回来看 T2，突然发现自己之前是个唐氏，写了一个很烦的贪心把 m=0 的包过了。

最后半小时再回到 T1，发现 2m>n 时，有一个 O(2^{2n-2m}poly(n)) 的做法，平衡一下，得到了一个 O(2^{2n/3}poly(n)) 的做法，赶紧写 + 卡常，终于在最后 10min 把 n\le 30 的包过了，喜提 60 分。

总分 60+45+20=125。出来问了一下大众分，发现也是 125，但是是 25+100+0，感觉自己唐完了，T2 存在一个更加简洁的贪心方法，然后就可以直接维护括号匹配了，哎，玉玉了。

讲题，T1 在 3m\ge n 时有 poly(n) 做法，有点厉害。T3 感觉不是人类可做的。除了 T2 蠢了，其他感觉还行。明天不能这么频繁换题了！！！

晚饭吃麦。太干了，水根本不够喝，去对面便利店买了一大桶水会房间。晚上打摆，十点半睡觉了。

Day 2

吸取昨天教训，六点半才起床。精神还行。

开题，先把所有题看了一眼，T1 神秘交互，T2 数数，T3 神秘构造。

先开 T1，第二个包是容易的，写了三行过了，顺便把第一个包也过了。然后开始观察一些性质，画了一会儿发现最小答案不是 \le 2？？搭了个排子发现确实是这样。然后类似分治的，每次随机一个点，问其他所有点到他的方向，分成左右两边递归，即可实现一个类似排序状物，最后第一个点就是答案，次数 O(n\log n)，交了一发，没 wa，获得了部分分数。

然后一想，为啥要分治来着，不是只要求第一个吗？改了一下就是一个期望次数 2n 的做法，过了。大概 1.5h。

T2 感觉像是 ei 题，不太能做，去看 T3。第一眼是一个拓扑序能够确定一条边，所以直接构造 n-1 个拓扑序即可，获得 eps 分数。然后想着乱搞，但是前提是我得会写 checker，想了很久发现自己根本不会写 checker！

突然发现正向方向两边可以确定一条链上的所有边！写了个链覆盖，次数两倍叶子数，分数还是不多。

又突然发现好像每个子叶开始搞一个 dfs 序倒序一下大概就行，写了一个确实是对的，喜提 61 分。此时 2.5h。

回去看 T2，先想着爆搜怎么写，怎么判定呢？编了好几个做法，修了很久终于在半个小时后学会了判定并通过了暴力分。op=1 的链似乎是好做的，17 分了。再想 op=0 的菊花怎么做，根据极长链的判定方法，发现是一个任意 1,x,y 都得在一条链上，那么就是 1 挂若干条链，但是得数等价类，分析了一下发现是好做的，大概是一个贝尔数，然后还要容斥掉只挂两条链的情况，21 分。

感觉 T2 剩下没有好做的了，再想 T3，还是没有本质优化。

总分 100+21+61.8=182.8，该拿的分也都拿了。听讲题，T3 好像一堆挂在一个点上的叶子能一起处理，T2 不是人类可做题。没有很唐。

晚上会酒店和 shaojia 和笋玩超级鸡马，被 shaojia 打爆了。十一点才睡。

Day 3

还是六点半起床，精神没昨天好，埋下伏笔。

开场先看题，T1 是个数数，T2 还是个神秘题，T3 又是交互，怎么每天都有交互！！！

开场先想 T1，有个很简单的 poly(n) 做法，直接记录每种连续段个数，但是感觉不太能优化（买下伏笔），于是开始想这容斥。枚举连续段个数后钦定若干个 R>B 和 B>R，就被分成了若干个钦定递减的段，但是每段概率并不独立，开始玉玉症。1.5h 了还是毫无结果。

想着该写暴力了，先把 O(n^6) 写了，由于空间 O(n^5)，只能过 n\le 30。然后去看 T2，会了一个 O(n!poly(n)) 的爆搜，调了一会儿判定过了 40 分。

再看 T3，好像只会一个 O(n^2) 次交互的做法啊！怎么办？这个最大连通块大小真的只有判定两个点之间是否有变的用处吗？？？

突然发现可以用来找独立集，开写，写完 60 多分。本地测了一下，比限制多了两倍左右，开始疯狂优化，写了好久终于卡进了 10^6 次。然后开始调参，调了好久才进了限制，终于过了，但是只剩 20min 了！！怎么回事！！

写新做法应该来不及了，把 T1 开成 vector 过了 30 分。

总分 30+40+100=170，垫底了。T1 发现其实一开始那个 dp 有若干位状态是可以压缩的，能被优化到 O(n^4) 并卡常通过 500，事实上大多数人都是这么做的。T2 直接倒着建二叉树结构，然后状压 dp 就好了，感觉比较常见的一个套路，但我也没啥时间做这个题了。

打的最唐的一把。下午闭幕式。

Rank

🐕近前 30 线了，能去 WC 了（）。