(Day?)
报名时间跨越了差不多一个星期多，这里打印一张那里上传一张，还挺麻烦的……最后申请还是通过了，看来(CSP)考得还不算太炸……
(Day0)
那么就坐飞机到北京去了。一起去的有同级的(Tiw)巨佬，高二的(MasterYi)和(Darkness)大佬，还有两个初三的学弟，也是大佬。嗯，全都可以把我按到地上摩擦（更强的(Freopen)甚至因为早就已经拿到最高奖根本没去(orz)），果然我最菜了。
上午的飞机下午才到，由于有人要去(PKU)，所以住的宾馆也不一样，(PKU)和(THU)说是很近，但是走路的话还是要走好一阵子（本来想像上一次一样骑自行车，但是据说天气太冷，会冻手）。天气很冷，但是室内到处都是暖气，反而没什么感觉。于是和(PKU)的同学们分开，住进了离(THU)相对较近的宾馆。
试机在第二天，所以晚上并没有去(THU)，也没有到街上逛，就在房间里复习多项式和生成函数的模板（然而最后发现并没有用上）。最后又打了一发半平面交的模板，洛谷上的模板交一发过了，没什么事可做，然后就休息了。
(Day1)
上午去报到，体感走了好久。(THUWC2020)的胸牌上还是(2019)年（大雾）。发了围巾，挺好的，就是最后都没开过封……
非正式选手莫得电脑，只能用自己的笔记本。既然用自己的，就没有试机的必要了吧……
于是试机(( imes))，模拟赛((sqrt{}))
第零题，(A+B problem)，大概是拿来测试网站的，不知道为什么我的笔记本登上(THU)的网站很卡，总是要加载很久……
然后看看一眼第一题，排序+前缀和乱切，大概(40min)搞定了。
第二题，树上有多少个块颜色不超过(2)种，这很树形(DP)。(O(n^2))挺好求，但是空间时间都会(GG)，先放着。
第三题，字符串，溜了溜了。
想第二题优化，没想出来。最后也没交（毕竟只是试机）。
题目挺好的，据说是(THUWC2018)原题。难度大概是递增，出来和(Tiw)大佬讨论了一下第二题，线段树合并维护一下值大概就行了，脑测了一下，细节较多。
中午回房间强制休息，咕掉了开幕式和合影（常规操作，我感觉我就没有哪次参加了合影）。
非正式选手比赛开始时间要晚(35min)，不知道是为什么。(THU)里的机房提供的网络只能登上提交网站，于是只好趴在桌子上休息等比赛开始。
不知不觉(35min)过去了，比赛开始，看题。
第一题
题面：(k)个人，每个人有初始工资(a_i)，(n)次操作，给定(p)和(b_1,b_2cdots b_k)，如果(b_p>a_p)，就把(a)换成(b)，(q)次询问，每次给定初始工资（就是(a)），求最终工资。
数据范围：(1leq n,qleq 10^5,1leq kleq 20)
感觉挺简单的，容易发现初始工资第一次被换掉之后的变化方式就已经固定了，那么我们可以枚举第一次被换掉是哪个人的工资涨了。先单调栈把每次替换丢掉一个数组里面，再二分答案就可以知道这个人涨工资是在什么时候，对所有人取最小值即可找到第一次变化时间。那么输出以这个时间为起点的答案就好了。
处理以某个时间为起点的答案不难，可以在单调栈时顺便求出，复杂度(O(k(n+q)log n))，理论上能过。从开始想到写完大概花了(1h20min)，交上去(Pretest)过了，就没管了，去看(T2)。
第二题
题面：一张有向图，(q)次询问，给定点(x)和步数(s)，每次选择(x)的编号最小出边走，问走(s)次后停在哪里（若还有步数时无路可走也会停下）。第(i)条边走(w_i)次后删除，询问时走过的边的次数会留给之后的询问。
数据范围：(n,qleq 10^5, mleq 1.5*10^5, sleq 10^9 wleq 10^{18})。
这个题第一眼看过去就觉得恶心啊(QAQ)。考虑任意时刻，可走的边形成的东西肯定是基环森林（其中可以有普通的树）。由于出度最多为(1)，那么每次询问其实就是先走到环上（路上如果走断了一条边得马上断开再接到另一个点上），然后在环上转圈，直到环断开或者走完步数。环断开的话也要再接上。怎么看都可以(LCT)优化，只是好恶心啊(orz)……
于是想着骗分，首先是(O(sum s))暴力跳边，若干小数据/随机数据都能跑过。然后(w_i)远大于(s)的，边不会断开，于是倍增就完事儿了。
这样加起来有(41)分。
还有树和基环树的情况，貌似很可做。
先考虑树，每次是从一个点开始向上爬一段距离，要求要么到达根要么到达一个断开的点（可以用爬升距离是否有(0)边判断）。然后给这一段的边全部(-1)，似乎就没了。诶诶，链的话岂不是要树剖+线段树？然后找到第一个没有(0)边的位置，岂不是要二分？这样算出来……(O(nlog^3 n))怎么搞……
刚了一会儿……最终决定还是打了这个算法，结果(O(nlog^3 n))果然爆炸了……
于是滚去看第三题了……
第三题
题面：一棵单位边权树，给定常数(X)，(m)次询问，问([l,r])的点构成多少个联通块，两个点相连定义为距离不超过(X)。
数据范围：(nleq 3*10^5,mleq 6*10^5)
神仙，不会，自闭……
慢慢翻看部分分有什么可以拿的，(4)分暴力，(4)分输出(1)，其他(GG)。
出考场
(Day1)大概是(100+41+8=149)，我好弱啊……和(Tiw)大佬讨论了一下，貌似就少了第二题的树，其他的大概是大众分。
晚上敲了一个网络流模板就休息了。
(Day2)
早上起来徒步走到清华，走了大概(15)分钟吧，可能有一公里远？
上午的比赛不知为何额外延迟了(20min)，比赛完后都要(2)点了。
第一题
题面：(n)份报告((ai,bi,ci))，初始兴奋值(s)，听一次报告兴奋值变成(a_i*|s|+b_i*s+c_i)，重新排序报告，求最大兴奋值。
数据范围：所有输入值绝对值(leq 15)（含(n)），答案可以用__int128存。
这个怎么看都是状压(DP)啊……似乎是(3^n)？但(15)跑(3^n)很卡的吧。而且看不出来有什么需要(3^n)的地方……
再考虑了一会儿，发现每个兴奋值都是个分段一次函数，具有典型的单调性。所以，最大的结果肯定是：最大正数、最小正数、最大负数、最小负数其中之一代进去的答案。然而问题可能有点大，我们要计算的不仅仅是最大结果，因为中途要用到正、负分别的最大值和最小值，而最小值由于规定了符号，相当于越接近(0)越好，无法单调。
这个时候猛然想到，(c_i)的值也很小，并且若(c_i=0)，就是两个正比例函数，只要代入的数符号不变，符号就不会变。
所以若兴奋值的绝对值达到一定大小后，让(c_i)再也无法让这个数变号，那么就不存在求最小值时可能出现的问题了。那么当绝对值小的时候暴力计算合不合法，绝对值大的时候记录正负分别的最大值、最小值即可。由于(n,c)都很小，只要当值在([-225,225])的时候暴力存就好了（更大的就算每次斜率为(1)，截距(15)都没有办法变号）。复杂度(O(450*n*2^n))，而且不严格，时限也宽松，能过。
大概花了(1h20min)码完了，一次过，去做第二题了。
第二题
题面：一个(DAG)，源点为(1)，按题目要求得到一个(DAG)的生成树，根为(1)。(q)次询问((a,b))，保证树上(a)为(b)的祖先，问删除树上(a)到(b)简单路径的边后，(DAG)上从(1)出发(b)的子树中有多少点不能到达，询问独立。
(n,m,qleq 10^5)
考虑到，(DAG)去掉一棵类(Dfs)的生成树还剩什么，交错边和前向边。
然后就分别看，前向边，在删除祖先的链时可能没用，要看具体删到哪里了；至于交错边，他们的起点不是终点的祖先，所以删掉祖先链没影响，好像任何时刻都能走到（此处(Flag)，之后发现是错的）？那么考虑询问是什么样子的。
最后能走到的点，显然是若干个子树，每个子树的根能用前向边和交错边走到被删除位置的上方（也即，(a)点的上方）。那我们应该尽可能使用他们跳到深度最低的位置。那么有交错边直接可以到根（此处还是(Flag)，之后发现是错的），有前向边就和前向边指的点能到达的深度最低的位置取更浅的即可。
然后求答案怎么求？可以对每一个子树维护一个线段树，(i)号点的线段树，下标为(j)的点存的值是：删除((fa[i][j],i))的时候的答案，其中(fa[i][j])表示(i)往上走(j)条边的祖先。
那么我们把询问离线放到每个点上，只需要求出每个点为根的子树的上述的线段树即可。考虑如何求？首先，若(i)无法到达（被删除的边达到了(i)用前向边和交错边能到的最浅祖先），答案应该是儿子的和，直接线段树合并！然后(i)能够到达的最浅祖先若没有被删除，整个(i)的子树都可以到达了，那么这部分可以直接全体赋值为(0)。
看起来蛮简单的，噼里啪啦就开始打了。测样例，全过，提交，刷新，(WA)，(0pts)。
当时我就傻了(QAQ)，写个暴力准备对拍。写完才突然发现我要造一个(DAG)？(1)号点还要能到所有点？询问还要保证是祖先？于是痛苦地打了一个勉强符合数据范围的弱生成器，(n)在(10)以内还真拍出来了。然后终于发现交错边并非一定能走，把(LCA)给删掉了就不行了。仔细思索，发现交错边((u,v))中的(u ightarrow LCA(u,v))这一条链可以随便走，那么其实和前向边完全可以统一起来。往上走的最浅祖先应该与这条链上的点们取更优。于是拓扑排序把最浅点求出来，倍增维护(LCA)和最小值，再重新套上线段树合并，要改的内容并不多。
于是最后打了(200)行，测数据全过后提交，(AC)了，舒服。
结果这么一折腾，没什么时间看第三题了……(GG)
第三题
题面：一颗点权树，点权组成(1cdots n)的排列，(m)次询问，给出一条路径，将路径点上的权值组成一个序列，问有多少序列满足冒泡排序k轮后等于这个序列，(\%998244353)。
数据范围：(n,m,k≤5*10^5)
没时间了加上题目太神仙，拿了(5pts)暴力就走了。
出考场
(Day2)是(100+100+5=205)，交流了一下好像算是大众分，回去休息了。
(Day2+)
工程题，(Cache)，看学习手册看了(30min)，还是基本一头雾水，大概就看懂了两个实现的部分，一个是(Cache)的替换算法，另一个是多个(Cache)的(MESI)算法。
第一题就是(MESI)的大模拟，看起来挺简单，准备做。
由于学习手册并没有告诉我读和写操作是读和写在哪里，我纠结了很久是改(Cache)还是改主存，最终大概知道了是改(Cache)。
以为自己基本理解了是在干什么，开始打了，大概就是跟着手册的操作做，但是它讲得很迷，并且对于第一题，有些步骤没有用。写完+调试花了接近(1.5h)，发现很多错误。首先是手册里面有些表述没有用英文函数表示，导致没看到。同时表述里面有(Flush)也有(Flushopt)，且(Flushopt)在题目里面没有传递数值，却依然要输出这个操作。而(Flush)则是题目加入的学习手册里面没有的操作。于是我把两个操作当成了同一个……样例却太水，没有显示出这些细节。自己都不知道是啥的东西，也造不出小数据。
最后(WA)了(5)发终于调对了，拿到(40)分。看第二题发现是大水题，(Cache)的替换操作多种同时实现。一个一个写，毕竟多一个就多(8)分，最后一个(16)分。
然而写完还剩(15min)，发现输入出了问题。原来输入的是(16)进制数，我用快读输入不进来。于是改成读一个字符串，结果脑抽了写成二进制，样例水还能过，但是交上去就(WA)。最后发现的时候只有(3min)了，要判断字母和数字两种情况，没写完……(GG)
出考场
发现就自己一个人只做了一道题，后面的题目都不难，而且很好理解……
(Day3)
非正式选手没有接到面试通知，在宾馆玩了一个上午，然后就坐飞机回去了。
其他同学都拿到了挺好的约，不过据说这次发约都是满天飞，有点担心约不值钱了。
这次表现还算勉强吧……前两天还算大众，最爆炸的是(Day2+)没有安排好时间，并且没有读懂材料就开始打代码，导致后面的简单题失分。