这个星期主要是体验那种打比赛 + 补题的生活。简单总结一下这几天的收获吧。

8.10

赛题： 「雅礼集训 2017 Day1」市场 「雅礼集训 2017 Day1」矩阵 「雅礼集训 2017 Day1」字符串

T1 是一道比较板的线段树操作题（但我不会啊），hansang 只用了 $1h$ 就切了只有我和 tjh 在那里傻傻发愣。赛后已严肃补题。

T2 居然挺水，$0.5h$ 场切，个人估计 ABC 的 E 题水平。（这可是我这几天为数不多的场切题目了）

T3 场上不知道是什么玄学东西（串串是这样的），但 tjh 鼓捣后缀数组加一些奇奇怪怪的操作硬是卡到了 $90$ 分。

得分：$40+100+0=140$。

好吧补题吧。T1 不用说了，已老实；T2 场切了；T3 是什么后缀自动机，不会。

看了一会后缀自动机，回宿舍睡觉了。

8.11

上午去学后缀自动机了，看了个概念，咋建的没看懂。

赛题： 「雅礼集训 2017 Day2」水箱 「雅礼集训 2017 Day2」棋盘游戏 「雅礼集训 2017 Day2」线段游戏

T1 首先矛盾只会发生在高处 $1$ 和低处 $0$ 之间，考虑从上往下扫描建树然后树形 dp，但是我突然发现这么建树的话一个子节点可能会有多个父节点，想了半天也没想到怎么合并。做法宣告假了。

T2 貌似是流。怎么建图？不会。还有这该死的博弈的必败态是什么？不知道。

T3 我怎么在 Library Checker 上见过？虽然我没做。尝试分块但是很明显并不能。

Day 2 惨淡收场。（ T _ T ）最终得分：$10+0+0=10$。

开始补题。T1 从 LOJ 上刮了一篇很巧妙的办法：将隔板视作 -1 操作，自底向上扫描，遇到 -1 合并左右区间，0 直接加入权值（因为没有与之矛盾的操作），1 的话需要权衡一下取 max。妙哉妙哉。

T2 原来是结论题啊，由二分图最大匹配的性质，“易知”必胜点只能是同时位于所有最大匹配的点。证明过程去看链接上我给的题解吧。然后跑二分图最大匹配然后对残量边 bfs 就行了。这题将流和二分匹配运用到了极致，是道很好的题目。

T3 是李超线段树板子，很明显我是不会的。但是鉴于它比较好理解和好学我就顺手把它的概念理解了一下再打了会板子。

好困，好疲倦，不想再打代码了。 （@_@）

8.12

赛题： 「雅礼集训 2017 Day4」洗衣服 「雅礼集训 2017 Day4」编码 「雅礼集训 2017 Day4」猜数列

T1 场上糖了。首先我算出了每件衣服洗好的最早时间，之后想到了个玄学二分做法，调啊调啊调，花了 1.5h 最后被卡了一个 $\log$。我忽然发现我的代码根二分没啥关系，结果：直接再继续处理一下每件衣服开始烘干的最晚时间，分别正反序相加就完事了，std 不超过 $30$ 行。（被自己气笑了）

T2 想过了所有字符串算法没想到咋做（不会又是后缀自动机吧），但是 tjh 的错解冲过去了。

T3 看完题直接懵了，压根不敢碰。

得分：$100+0+0=100$。

补题 ing。T1 虽然糖好歹切了。

T2 不是字符串是 2-sat？坏菜了我怎么没想到，矛盾条件加上 01 串最多 $2$ 种选择还只有一个 ? 这不是明显的 2-sat 吗？不过它的字典树优化建图还是挺妙的，就是用一些中继点辅助建边。

T3 神秘四维 dp，看都看不懂，严肃跳过。（史留到周末吃）

8.13

上午其他人比赛的题目有个 DDP？正好了解一下。原来 DDP 这么简单，差不多 $0.5h$ 就掌握了。

赛题：「雅礼集训 2017 Day5」远行 「雅礼集训 2017 Day5」珠宝 /「NAIPC2016」Jewel Thief 「雅礼集训 2017 Day5」矩阵

T1 第一眼 LCT，但是怎么维护一时想不到。想了 $5 min$ 发现一棵树上任意一个点的最远到达点只会在它的直径的两个点上。然后 LCT 维护直径就行了。$1h$ 场切。

T2 数据怎么这么大啊，想了半天发现可以开桶，然后贪心拿，最后会形成一个上凸函数。但是这个上凸函数有啥用呢？不知道。交了个暴力但是错了，也不想调了。

T3 看完又直接懵了。这是啥啊？咋还有这种题啊？完全不会。

最终得分：$100+0+0=100$。

依旧补题。T1 场切了。

T2 居然是分治 DP？我怎么没听过？奇怪的知识增加了。原来由于对于每一种价格的物品形成的上凸函数使整个 DP 具有了单调性然后就可以分治。妙哉！

T3 讲矩阵的各种性质。我对矩阵可是没那么熟悉，最多设计一个然后去做 DDP。基本看不懂。（依旧留到周末吃）

8.14

上午去看 tjh 学向量了（我居然还没有忘 ^o^ ），顺便打了一遍 DDP 板子。

赛题：「雅礼集训 2017 Day7」事情的相似度 「雅礼集训 2017 Day7」跳蚤王国的宰相 「雅礼集训 2017 Day7」蛐蛐国的修墙方案

T1 想到后缀排序然后对于每个询问将区间的 $rk$ 排序然后对每两个相邻的 $rk$ 求 $height$ 数组区间最小值。然后用 set 和莫队优化被卡了。qwq

T2 我以为又是一个树上背包，就在每个点子树外选一些点放到子树里使该点成为重心。但是我没有一点思路，去调 T1 了。

T3 看的时候脑子已经特别乱了，没有多想也没有多思考。始终没想出如何 $O(N^3)$ 求。

得分：$30+0+0=30$ （T_T）

啥也不说了，补题吧。

T1 是什么“LCT 维护 SAM 的 parent 树”，哎不是怎么又考到 SAM 了啊。好在 Qwen 神力回滚莫队 + ST 表卡过了本题。

T2 神秘题目。原来这题除了根节点就只有 $2$ 种答案啊。我们只需要判断能不能是最小的那一种就行了。好神秘。

T3 被气笑了。$O(2^\frac{N}{4})$ 的玄学复杂度是哪个神人想出来的。这题原来就是个半暴力。可惜场上没时间多想了，没发现性质。

总结

一句话，被题目摁在地上摩擦。（$5$ 天切了 $3$ 题，也是体会到 nasaepa 打省集的感觉了）

就当学新算法了吧。

下周继续！！！（虽然我可能会打吐）