这里是老是写挂题的WrongAnswer弱渣= =

作为一位无实力选手，当然要直播THU集训是怎么揭露本渣的辣鸡实力的2333

Day 0

很早起来赶飞机，到了以后赶去hotel，最后由于塞车等缘故还是没在报到结束前赶到hotel，啊好惨

尼玛，immortalCO整天都在说我是猫，啊我不是猫啊啊啊

Day 1

上午8:10开考。看了看题。

第一题，居然是TopCoder SRM 561的第二题，我的集训队作业啊= =然而原题数据范围是 $N\le 50$，这题是 $\sum N\le 200000$……

有啥好的性质吗？想了想并没有什么好的思路，敲了个60分暴力去写第二题。

第二题是个题面题……看了好久的题面才知道意思是啥……

发现题目是把 $b$ 求了个 $m$ 维前缀和，直接倒过来对 $c$ 做个差分就做完了，代码好短，让我一度怀疑做法是不是对的。

开始看第三题，怎么有种HNOI的既视感QAQ然而丧多了2333

没思路啊，只会暴力，连只有插入都不会做。那好吧还是写30分暴力，写完了交上去。

这时候10:00，开始研究第一题，准备打表找找规律，手动出了几组数据发现Grundy函数怎么有点奇怪？？才发现有个地方vis标记忘了打……

还好查出来了。接着又猜了几个结论都是错的。弃。去检查第二题。

写了个checker对拍，拍了数十组WA了一组，发现有个细节没处理好，及时改对。

想了想我到底该搞第一题呢还是第三题呢，第三题没思路，还是弃第三题搞第一题吧……既然没有啥性质难道就是暴力用个数据结构维护？看到时限2s空间1G似乎明白了什么。

剩1h，开始写Trie合并。

最后10min写完了，结果样例没过不知道哪里狗了……尝试最后几分钟debug出来然而失败了……

出考场估分60+100+30=190。

10分钟后进考场看结果，60+100+0=160。

第三题爆0啦~滚粗啦~然后听说大家都是230，CJK挂了10分，220。似乎挂得最惨的也比我高？

完了要垫底了QAQ退役愉快？

后来和CJK讨论了才知道第1题Trie合并哪里写错了。合并的时候子树大小没有从子树push up而是直接加，于是有重复节点就GG了。另外节点数组没清空。果然我功力不足啊。

下午讲题，果然前2题一堆人A。我的1和3都没到平均分。然后又得知第1题有原题。

惨。

大家都230，而我只有160，少的这70分如何拿回来？没有了，拿不回来了。

Day 2

今天运气比较好。

一开始看了三题，感觉第三题特别麻烦，第一题有点像模板题（？）感觉很多人都会A，第二题是个有趣的Manufactoria提交答案题。

想了想决定先思考第一题。感觉 $f$ 的次数很低的时候可以 $O(1)$，次数很高的时候似乎有和 $m$ 有关的做法？

于是打了个表……$m=1$ 的时候 $Q(f,n,x)=nx$，$m=2$ 的时候不知道是啥，不过是个关于 $n$ 的二次函数……那么 $m=3$ 的时候是个三次函数？一般情况是 $m$ 次函数？

假装这个结论是对的于是插值了一发，发现计算 $Q(f,0,x),Q(f,1,x),...,Q(f,m,x)$ 每个就要 $O(m)$，总共就 $O(m^2)$ 了……看了下数据范围有90分感觉很满足了就不继续想了

写完过了前两个样例，最后一个样例没过=-=仔细一看发现有个地方爆了 int，改完过了样例，感觉90分是稳了。

再看第二题，读了很久的题，试了一会儿怎么搞，发现不太好搞，还是先写第三题暴力回来搞第二题吧QAQ

第三题敲了个不知道复杂度是多少的树形DP，写的时候一堆 for 循环，很怕写错，不过写完样例居然一遍过了？测了下 $n=Q=1000$ 的随机数据，很快就跑出来了。然而还是有点虚。

继续分析了下，似乎正解是加个虚树的优化，然而要处理链上的连通块，细节好多啊，而且还有可能TLE。反正我肯定写不完= =果断弃。

开搞第二题。之前很快把测试点1、2、3搞出来了（2的KMP调了一小会儿，还好调对了），接着搞4发现很麻烦，等会再来搞~测试点5也很水，6呢……？能识别的串没几个？那我就把所有串建个Trie吧（雾）接着发现串长最大可以到 $377$，超过 $300$ 了，靠。

等我搞出测试点6的时候 sim 了一下，发现 a 忘了判- -及时改对。然而由于我太菜了测试点7没想到什么靠谱做法。

测试点8、9、10看起来就觉得很复杂，那好吧我先去考虑测试点4= =b

一开始想到了在模意义下做，于是设计了一个模 $m$ 从 $m-1$ 到 $0$ 的时候cricket一个 [，从 $0$ 到 $m-1$ 的时候cricket一个 ]的做法，结果发现复杂度是错的——如果在 $m-1$ 和 $0$ 附近一直转移就呵呵了，看了下离比赛结束只有1h左右了，好虚啊要是搞不出来真的要GG了……然后经过思考，想了一个把 $m$ 个节点扩展成 $2m$ 个节点的做法，令 $m=100$ 然后把这个结构复制 $3$ 份就做完了？然后发现节点数爆了，就令 $m=20$ 然后把这个结构复制了 $5$ 份……测了一下数据990000+。好险。

这时候时间不多了就把第二题交了。交了以后继续看发现表达式和括号序列一样做法= =就把测试点4的结构稍微调整了一下得到测试点8的答案，再把测试点8的答案原样复制了一份作为测试点9的答案就交了，想想81分也不错了，就不继续搞了。

最后十分钟在检查，对拍了第三题感觉没什么问题，比赛就结束了。

n+e过来说我今天206，过了一会儿看到成绩果然是95+81+30=206。第一题 $m^2$ 居然多过了一个点？（虽然标程也是 $m^2$ 的）第二题搞的点全A了。终于没有挂了。

问题是，昨天少了70分，今天多20分仍然翻不回来啊QAQAQAQ

immortalCO是猫！WrongAnswer不是猫！

Day 3

只剩两天了，希望能不留遗憾吧。

一开始看了下三个题。

第一题：我会暴力！很快把暴力码完了，然而……暴力才10分……

第二题：我会暴力！很快把暴力码完了，然而……暴力也才10分……

第三题：字典序最大……这不是个最大生成树吗？看起来有反例的样子，如果不是简单路径的话……题目意思应该是简单路径，那就是个加边维护MST？可是我不会啊TAT

于是码了个MST的暴力，看子任务，有一部分数据是 find 都在 move 之前的，这样的话只要把MST建出来，转成子树加深度来搞？看起来很有道理，于是就花了大概1h写LCA+树状数组。看了下也有70分了，剩下的感觉是LCT之类的麻烦东西，实在搞不动。（感觉CJK这题要AC了）

拍了下感觉没问题。回去搞前两题。

第一题可以矩阵乘法，可惜也才20分。剩下的 $3^m$ 有点大感觉很恶心，不太会。

感觉第二题似乎更可做一点？那好我就搞第二题吧。想了下如果枚举了特殊牌的顺序接着怎么搞？看起来就是每个元素都有一个最右边的位置，然后问有多少种排列方法。这个似乎可以用一个多项式复杂度的递推完成，然而要枚举排列……经过思考决定改成状压DP，然而复杂度实在太糟糕还是只有30分……

接着开始考虑优化状压DP，结果是越想掉坑越深，更可怕的是我并没有意识到想法方向错误。决定换个思路想想：答案会不会是关于 $w_1,w_2,...,w_n$ 的多项式呢？好像有道理，来我推个式子，好像式子有一定对称性？接着想用一个递推来计算系数。接着意识到由 $w_i$ 构成项的个数也是指数级的，弃疗了。

11点多回头搞第一题。由于花了一个多小时搞第二题却只得了30分，心态不好，有点急躁，于是推第一题的时候很紧张，就怕是个水题，然而我时间不够了啊QAQ

通过打表找规律，发现矩阵中不同的数好像只有 $\frac{(m+1)(m+2)}{2}$ 项，而且好像有循环性质。再分析了一下意识到矩阵只要存第一行。以为这样能多不少分（虽然后来发现只多了15分），于是花了一会儿把第一题改成只存矩阵第一行，再交。接着在想能不能把矩阵优化到 $\frac{(m+1)(m+2)}{2}$？然后就做完了？

果然我还是太naive。缩完矩阵以后似乎要做个奇怪的求和变换，不会了。

最后滚回去检查第3题，和暴力拍了好几组 $n=1,001$，$m=3,001$ 的数据没出问题，接着出了一组大数据RE，于是非常感人地发现我改暴力的时候有个 $3,000$ 的数组忘了改成 $300,000$，及时改好。好险啊差点70分就没了。

看了一下今天只有35+30+70=135，哎好惨要滚粗了啊。

最后就这么135分滚粗了。出考场CJK说第3题不就是个裸的LCT吗？卧槽，看来要被甩30分了=-=接着看到第2题被yjqqqaq想了个线性做法A过去了

rank1 yjqqqaq 240，rank2 HalfSummer11 195，还有一堆170+、160+……看了下榜连前15都没进TAT

讲题的时候发现我真是无比傻逼。第1题我没搞出来的那一步是个FWT，然而我并没有深入研究。

更可惜的是，第2题！我！后！来！的！想！法！是！对！的！——唯一不对的！就是以为指数级一定过不了！实际上40的划分数很少！

一个多小时的努力，已经十分接近正解，却在最后弃疗了，失去了得70分的机会。

（UPD：据说这个做法会被卡常数成50分，看来丢的分没那么多）

不过也没什么好说的了，毕竟自己确实没有前15的实力，也许考场上就算想到这一步也不一定能写对。

Day 4

最后一天。希望能不留遗憾吧。

首先看了下三道题。第一题NOIP加强版，裸数位DP，估计全场AC。第二题看起来像个点分治，估计半场都要AC。第三题是个几何题，看起来是个要么基本没分要么拿高分的题。

于是先切了第一题，由于实力实在太菜，写错了好几个地方，调了好久才对。

犹豫了一下到底第二题和第三题要先写哪题，觉得第二题部分分比第三题简单些？先敲了第二题的20分暴力。打算先写完第三题再看情况是写第二题100分做法还是部分分做法。

写的时候感觉很有压力，毕竟几何题容易挂。大致整理了一下就是 $S$ 和 $T$ 连边，$S,T$ 和每个圆连切线的边，每两个圆连公切线的边，每个圆的切点按顺序连成一个环，求最短路。随后感觉没那么简单，因为切线不能和别的圆相交。

所以还要和圆判交，暴力是 $O(n^3)$……算了就写这个吧反正就算不能A应该还是有很多分的。

开始写。先定义了点和边的 struct，定义了几个基本函数，敲了输入部分（经过思考决定把所有几何量开 double），敲了个Dijkstra最短路，然后把主过程一个个打好。打到一半的时候发现我的线段和圆判交写成了直线和圆判交，日哦……改改改，改完了。

全写完后测一发样例，什么鬼第一个样例WA了？有点慌，把图打出来看，发现一个 y 打成 x……过了第一个样例，再测第二个，尼玛又WA了？好紧张啊都10:30了……没时间做第二题了啊……

还是把样例一的图再打出来看看吧，接着对着样例说明的图看了看，发现外公切线求对了，内公切线求错了- -调好以后过了样例二。交上去了。

这时候只剩1h+，开始研究第二题，推出一种做法：二分一个 $M$，判断是否存在一条路径满足 $|\frac{sum}{len}-k|< M$，即

$$(k+M)\cdot len-sum>0$$

$$sum+(M-k)\cdot len>0$$

就把每条边的权值 $w_i$ 改成两个权值 $(k+M-w_i,w_i+M-k)$，判断有没有两个权值都为正的路径。接着想到了用点分治解决，对每个点记到根的路径上的两个权值和 $a_i.b_i$，把权值序列取相反数以后和原来的权值序列归并排序，转化为对每个原序列 $i$ 判断是否有 $j < i$ 且 $j$ 属于相反数序列且不在 $i$ 同一个子树内，以及 $b_j < b_i$。每个子树记一下 $b_i$ 最小值。也不知道有没问题。

然而点分治写不动啊……曾经在省选的时候花了3h写了一道点分治导致时间不够于是爆炸，UR14第一题也掉坑花了90+min写了点分治导致时间不够挂了第二题，前段时间打Codeforces写点分治也写了好久没写出来。看着只有1h的时间，决定放弃正解，写几个部分分。

先写了 $(i,i+1)\in E$ 的点，二分完就是个离散化树状数组。交上去之后又写了 $(1,i)\in E$ 的点，做法差不多。写完后和暴力拍了若干组没啥问题，交了。

最后检查了下第一题，又检查了下第三题样例构的图没问题，就弃疗了。

最后出成绩——尼玛我第二题怎么才40？！炸了呀，点开一看发现只A了前8个点，后面那一档部分分全WA了……

还好T3数据水送了我90分。于是今天就100+40+90=230了。

出考场发现大家分数都比我高，immortalCO 260，philipsweng 235……然后听说C_SUNSHINE大爷AK了。

这是滚粗的节奏啊……

看了总榜，前6名分别是C_SUNSHINE、matthew99、philipsweng、yjqqqaq、syf、immortalCO。

immortalCO FJ全省rank1，全国rank6，劲啊。

还好我由于Day2的优势并没有掉出前15。希望WC能稳一点吧。

回去调Day4的第二题，测了几组小数据没问题，为啥会挂？

难道是我数组没开够？

……果然，我把 $a$ 和 $a$ 的相反数放在一起离散化一共 $100,000$ 个数，然而有个数组只开了 $50,000$，于是挂了……

附一段对话：

WrongAnswer：问题是没有RE而是WA……

JOHNKRAM & yjqqqaq：正常

JOHNKRAM：你开的数组刚好是连续的

再调Day1的第三题，看了一会儿还出了几组小数据都觉得没啥问题，怎么就爆0了呢？

仔细一看我的暴力求LCA是这么写的：

while(dep[i]!=dep[j]){ // 正确应该是 while(i!=j)
    if(dep[i]>dep[j])i=fa[i];
    else j=fa[j];
}

while(dep[i]!=dep[j])！！！我怎么连暴力找LCA都写狗了啊QAQ

最后打算把这几天把集训的题都搞懂。希望UOJ能加上清华集训题。