9.20： 题目：T1,T2,T3

得分：209，排名：2

幸亏是IOI，要OI没大样例真会死。

开赛先看T1，思考一伙之后发现可以 dp,于是写了一份。当时写完感觉稍微有点不对，但没管。交了之后无果，于是直接放弃了 dp，改去写贪心，贪玩发现第二个样例有点问题，于是先写了个 $O(n^3)$ 的版本，但发现提交之后仍然是 $0$ 分，然后改了许久，突然发现样例二所造成的修改也能运用到其它位置，卡掉了自己的贪心。于是滚回去写 dp，最后在 $90$ 分钟左右时通过了 T1。

总结：开始 dp 错误时没有仔细思考而是直接放弃了，贪心错误时将一些可以通过样例推出的性质进一步延伸。

然后是 T2，暴力只用了很短的时间就写完了，然后发现区查最大最小可以通过线段树维护，写了一遍但样例都不对。然后决定直接重构，在纸上手模了一下堆塔的过程，发现中间的那些颜色没有任何意义，可以用 $00-11$ 的二进制数来表示一座塔，然后就过了。总用时 $105$ 分钟。

总结：没啥问题

T3 时间不够了，所以只写了一个 $k=0$。

赛后补题用了大量时间写第三题注释，并严肃弄懂了第三题代码（并出了一道完善程序，可以明年给打初赛的人复习）。

9.21：

题目：T1，T2，T3，T4

得分：238 排名：4

开赛依旧先看 T1，想了会 dp 但发现自己不会转移。然后在思考时突然发现同一个 $[l,r]$ 被不同的操作搜到的概率很低，也就是如果直接搜索的话状态数差不多只有 $n^2$ 级别，于是转去写搜索，起初用的是系统的队列，发现 T 了第二个子任务，然后改成了手写队列但出现了大量 RE 的点。对拍测特殊数据没拍出来，但随机数据查出来了问题。输出之后发现是出现了大量 $[l,r]$ 相近的区间偷吃时间和空间，所以加了个数组用于优化，然后过了，总用时 $111$ 分钟。

T2 看了一眼没思路，直接去写 T3，发现这个区间修改很容易在倍增求 LCA 时直接维护，写了一下就过了，总用时 $19$ 分钟。

又回去看 T2，想到了矩阵快速幂，但我设计的矩阵大小 $2.5\times10^9$，也没想到该怎么优化，所以直接放弃。

T4 暴力分都没想到，直接就结束比赛了。

下午补题，把 T2 和 T4 都过了，并且只交了一遍（展示码力）。

总结：主要问题出在 T1 的对拍拍的用时有点太久了，以后对拍要先测几组随机数据，其他的都没啥。

9.22： 题目：T1,T2,T3,T4

得分：169，排名：5

严肃成为大区。

T1 没啥能说的，看到后一眼想到 dp，设 $dp_{i,0/1}$ 为以第 $i$ 位为末尾，下一位没有/有进位时的方案数，分讨一下就能推出转移方程，写完了，总用时 $14$ 分钟。

话说 T2 真的是绿吗？

看到一眼贪心，然后稍微推了一下，想到从小到大的序列正着贪不太好贪，想到了反向考虑，从全部选上开始一点点删，但是交了一发只有 $54$ 分（这也是我这题的最高得分，此时离开赛只过去了 $68$ 分钟），并找到了一个 hack，此时就以为贪心不太可行，往 dp 的方向去思考了，简单想了想发现了一个 $O(nmk)$ 的 dp，写了一下发现只剩 $18$ 分了，对拍之后发现在分割出从大到小的堆时把变量打错了，但改之后也只有 $26$ 分，此时已经过去了 $3$ 个小时，直接放弃了。

T3 看了一下一点思路没有，直接放弃。

T4 打了 $n,k\le10$ 与 $k=1$ 就提前结束了。

比赛时的主要问题就是 T2 没有在贪心的方向上进一步思考，否则的话应该能发现正解需要的性质。但说实话，当时我已经十分确信贪心不可做了，让我去想应该也想不到。

下午补题主要就是把 T2 和 T4 补了，并发现自己学 OI 这么久以来竟！然！不！知！道！求！和！符！号！对！乘！法！有！分！配！律！这集真的区完了。

9.23:

题目：T1,T2,T3,T4

得分：145，排名：5

？！区区区区！？

每日顺序开题，T1 一眼爆搜，大致思路就是从一开始先 BFS 一遍，统计一下每个点的可行性，再对可行的终点倒着搜一遍。但我最开始想的太复杂了，同时维护了到每一个点有多少条最短路上有花园与到每一个点之前经过的花园总数，调了 inf 分钟没调出来，然后决定先放一下，去看了 T2。

T2 想了一下部分分，就先打了，瞥了一眼 T3,T4，发现是树形 dp，刚好我在这方面的理解也相当于滚木。严肃滚回去看 T1，因为当时发现 $f$ 函数在区间右移时不好维护。

继续看 T1，突然发现自己的 $flower$（即有多少条最短路上有花园）起到了相当于滚木的作用（甚至因为这玩意会被 hack 卡掉，纯飞舞来的），因为题目要求必须经过所有花园，所以实际上只用维护 $1$ 到每个节点的最多花园数就能方便快捷的判断出这个点是否合法。然后光速过 T1，用时 $106+34=150$ 分钟（然而我们注意到这实际上等于 $140$）。这集真的区完了。

看回 T2，发现实际上 $f$ 函数只有在一些数由 $1$ 变为 $0$ 之后才会较难维护，其他情况就是一个十分简单的区间减，而前者在整个循环位移的过程中只会发生 $n$ 次。于是采用线段树，维护区间内 $\ge1$ 的数的数量与 $<1$ 的数的数量还有区间正数最小。但赛后十多分钟才调出来（多测线段树的 $tag$ 忘清空了），于是喜提倒三。

今天的核心问题就在于 T1 调的太 $^{TM}$ 久了，花了 inf 分钟在无意义的测试上，导致 T2 没有调出来。

（旁白）想到你今天的简爱测试卷一点没写，这使你感到生活无望了。

（旁白）但想到你们已经把课件拷了下来，这是你充满了决心。