11.6场

　　开场先读题，T1感觉像搜索，T2图论没思路，T3题没读懂。再分析了一下T3的样例，算是把题搞懂了，感觉T3比较可做，确定做题顺序为3-1-2。一开始想用dsu on tree+树状数组，但感觉不好清空已有信息，就没有继续往下想，于是就自然地想到了线段树合并，空间有点紧，算了一下空间，节点回收就可以过。1h写并调试完T3，拿去对拍，就开T1了，这时开考大约1.5h。粗略地计算了一下T1的时间复杂度为$3^{25}$,感觉不行，然后就想起(jsq提醒)可以折半搜索，搜完后排序，双指针统计答案，自己构造了几组数据，跑了一下，感觉没问题，静态查了一遍错，似乎也没有问题，就开T2了，这时离考试结束大概还剩1h。开始想T2，二分很显然，但不会check，猜想一个结论却又自己把自己hack了，于是在还剩30min的时候开始打暴力，构造了几个小数据似乎没问题，就去检查文件名和数组大小了。

　　期望得分：100+30+100=230

　　实际得分：100+20+100=220

　　T1没有问题。

　　T2的确存在一个结论，没有想到，题型还是见少了。暴力打挂了是因为每次建图时领接表大小没有清零。

　　T3的正解是dfs序+树状数组，其实我在想到dsu on tree后也有想过dfs序，但感觉不好一次性统计答案，结果是三个答案分开统计，这样的话时间和线段树合并一样为O(N logN)，但空间比线段树合并优秀为O(N)。感觉思维还是不够灵活，想着一次性把所有答案统计出来，实际上这样很难，但如果灵活一点的话就想到多想几次分开统计答案了。

11.7场

　　开场先读题，T1感觉是单调栈，T2没思路，T3又是DAG…确定做题顺序为1-3-2。T1是环，环上两点间有两段弧，感觉不好统计，于是直接断环二倍链，改用单调队列维护，但如果有同高的冰锥又很难维护，于是又开了一个队列，与第一个队列对应，记录其相同高度的冰锥的个数，但删除的时候时候会出问题，于是又维护了一个链表，然后统计答案，最后去重，过了样例，自己手搓了几组数据，发现没过，静态查错，想到了问题所在，细节没有考虑周全，改了一下，就过了自己手造的比较特殊的数据，然后输出了一些数组，没有发现问题，就开T3了。画了画图，没有感觉，思维有点乱，去了次卫生间冷静一下，然后先放弃了T3，想T2，稍微推了一下，发现是DP，然后p的关系似乎是森林，然后另外维护了一个根缀就完了，过了样例一，没过样例二，输出了中间的一些值，发现了一点问题，改了改就过了，这时还剩1小时。T3虽然长得很像可以二分的样子，但往二分的方向想了想，需要提取所有长度大于mid的路径，感觉不可行，就去找性质。偶得一结论，似乎只要断在起点或终点就可以了，赶紧写，写完才发现错了，但时间已经来不及了，就放弃了。检查完数组和文件名就交卷了。

　　期望得分：100+100+0=200

　　实际得分：100+100+5=205

　　第一次估分比实际得分低…

　　T1似乎直接单调栈就行，但断环的位置必须是最高点。

　　T2做麻烦了，维护一个前缀和就可以

　　T3，再次死在了DAG上。其实之前二分的做法是可行的，预先两次拓扑排序存到起点的最大值与到终点的最大值，二分的时候枚举边看它是否需要提取，所有边提取出来后再判断有没有必经点就可以了。当然题解的做法也很巧妙，运用了拓扑序分层的思想，用数据结构动态维护，这种做法似乎是第一次见呢。

总结

　　两天的考试都死在了图论题上，而且都是DAG，自己的图论题还是做少了，最近在练习历年noip题和DP题，这之后需要再练习一下图论题，尤其是应用图论基本算法的题。下周就考试了，ltw这两天都AK了，自己的实力还急需提升啊。

2019-11-07