SD二轮省集总结

4.29

day 0

中午到 SD，然后住进了学校里

怎么下午还有热身赛啊，没法睡觉了

发现 t1 是简单题；t2 见过类似结论，无脑维护凸包 $n^{5/3}\log n$ 过了；t3 猜了个结论写暴力，写了1h 最后没调过？脑子去哪了

晚上回寝室，看会儿手机睡觉了

 

4.30

day 1

模拟赛

早上模拟赛，7:40 ~ 12:40

扫了一遍三个题，$t1$ 看上去不是很难；$t2$ 看上去非常逆天；$t3$ 状压题好啊！但想了一下没什么好的思路

开 $t1$，发现限制很松，想想只需要考虑和直径的关系就行了，对于 $ans=2$ 的情况好像有点需要讨论的地方，猜那种情况应该不需要考虑，写了一手交上去 0 分？

想了一下最无脑的做法显然是直接分讨一下倍增找到那个点，但好难写啊！应该会有更好的性质吧

推了 2h 没有想到简单的做法，决定先往后开了

开 $t2$，首先想暴力，手玩了一下缩完点后 SCC 之间应该删没用的边就行，但内部需要找一个环？也就是找哈密顿回路？手玩了一下发现竞赛图好像一定有哈密顿回路，但我要怎么找啊？完蛋了，暴力都不会写

看 $t3$ 去了，状压题优势在我，首先考虑容斥

这容不了一点啊！暴力跑路

回来写 $t1$，发现好像有一种简单写法？

交上去怎么 0pts 啊

怎么就剩 20min 了啊

怎么没调出来啊

哭，这波是垫底了

$75+0+35=110，rk58$

赛后立马被 mmz hack 了 $t1$ 的 “简单” 做法，呜呜有种情况没考虑。但那个倍增做法貌似是对的

下午讲题发现我 $t2$ 题意看错了！是重新构造一张图不是删边！！我不会的那种情况压根不存在

$t3$ 思考方向有点问题，一直觉得是要怎么改变计数方式的，听题解发现其实是对暴力 $dp$ 简化状态

感觉有点不会分讨啊，遇到情况稍多一点的就不敢去想了，实际也没有那么复杂啊

$t1$ 订了，$t2$ 正解没听懂，$t3$ 听懂了还没写完

讲课

下午讲课，tsx 的树上问题选讲

CF1394D 先考虑严格增/减 怎么做，发现可以把贡献放到每个点上处理，然后有相等就改 $dp$ 来钦定就行

loj6669 一般这种问树上距离都是先定深度，然后一层一层做，为每个点找父亲。这个题做法是用重剖来找

uoj618 妙妙题，根据重心的结论奇数时答案为 $1$，偶数就是虚树上重心那条边的长度，考虑怎样的两点 $u,v$ 可以作为两端点，需要刨掉路径后的子树 $siz\ge \frac{j}{2}$，可以点分治维护。更好的做法是只考虑一个点要满足哪些限制才可以成为端点，编出来 去掉最大的儿子后剩余节点数 $\ge \frac{j}{2}$，可以证明是充要的。那就可以直接维护点集直径了

uoj33 没懂

CF830E 牛逼均值不等式题

 

5.1

day 2

还是先扫了一遍三个题，$t1$ 看上去很套路；$t2$ 又是很逆天，这些条件指向的显然是线性基，但我并不会怎么对线性基计数，看了部分分好像直接搜线性基就有 20pts；$t3$ 数据结构，看形式有点像吉司机线段树？

开 $t1$，发现枚举 MEX 后问题就简单了，凭感觉写了个 $dp$，写了一发过了样例，大概 8:30 的时候交上去 $10pts$？噢我复杂度怎么这么劣

先把 $V$ 优化成 $n$，然后发现复杂度是惊人的 $n^3$，想了一会发现不需要枚举 $mex$，在 $dp$ 过程中钦定就行了，这样就对了。写完这个已经 9:15，交上去 60？

噢我复杂度算错了，以为有个背包的复杂度可以分析到 $n^2$，结果还是 $n^3$ 的

分析了一下我现在的 $dp$ 瓶颈在于卷积没法优化啊！尝试了多项式和拉差，似乎都不太能做。已经快 10 点先跳了

写 $t2$ 的暴搜，写完发现状态数不是很对啊！完了线性基状态数是 $\prod 2^i$，我以为是 $\sum$

10:20 有点慌了，先去写 $t3$ 暴力，写完又想了一会儿，依然不会什么好做法

只能再想想 $t1$ 了，发现容斥一下复杂度就对了？额，写完过了样例，11:40 交了

然后继续想 $t2$，转向性质，发现对于 $X=0$ 好像是可以直接 $dp$ 线性基的矩阵的，编了一下感觉差不多，但突然发现 $t1$ 测出来 $45pts$ ？静态查错了一下无果选择对拍，终于在 12:10 拍过了

交上去，据说在结束前是看不到结果了（这就是 apio 赛制吗

回来赶紧写 $t2$ 暴力，没有调出来

$100+0+20=120，rk41$

感觉以后不能无脑开写了啊，想 $t1$ 的时候认为转化完的问题应该随便做都是对的，写完才发现复杂度假了，以后应该多想一下，理清思路再写

$t2$ 听题解感觉是见过这种线性基计数的套路才能会的题，没见过，唉。上午想的那个做法有道理，但漏考虑了一些东西

最应该开的是 $t3$，数据结构这种东西感觉花时间磕总能磕出点分的。

唉，不能那么着急去写代码，写到一半发现 思路假/复杂度错 是最难受的

$t1$ 过了；$t2$ 可以订，得先学一下前置知识；$t3$ 只听懂了大概

 

5.2

day 3，jsy 场

扫了一眼三个题，$t1$ 看起来困难；$t2$ 构造，感觉有点眼熟，好像见过类似的构造 DAG 的；$t3$ 有点逆天，不是很会

大概 8:00 开始想 $t1$，推了很多性质，发现需要一个 “把相交但不包含的线段” 缩起来这个操作，剩下就简单了，但这个操作感觉极其难写啊！尝试弱化推出来的性质，得到一个结论：每次只会选择两段方向不同的？然后破环成链算贡献就行？

直接写到了快 10 点，交了一发 0 分！然后随便手玩了一下把自己 hack 了

尝试修，修完发现做法等价于直接破环成链算贡献，10:40 交了一发 $40pts$，搞笑的是 sub1 没过

改了改交有 $55$，仍然未通过 sub1

不行得往后开了，想了一会 $t2$ 发现和我印象里的那个题不一样，然后尝试分层，构出来指数条路径，但完全控制不了 $a_i$ 啊！

跳跳跳，开 $t3$，除了流只会一个无脑贪心，手玩了一下发现 hack 不掉，写了一手交上去 $0pts$！急了

11:20，回去想 $t1$，继续那个破环成链的想法，意识到了问题在于枚举的断点可能在链的两个端点，这样还得分讨中间每个线段的选法

写完极其恶心的分讨发现直接过了样例和 sub1，好接下来改线段树维护这个东西复杂度就对了！

怎么 12:16 啊！这改的完？

最后又卡住了，我需要 用两种颜色覆盖区间以及撤销，查询全局中是否有被两种颜色同时覆盖的点。最后发现好像可以用扫描线那种写法

没有写完，拼暴力和假做法遗憾离场

$70+0+0=70，rk45$

菜死了

ljh 大佬过了 $t1$，发现他写了那个 “合并相交但不包含的线段” 操作，只写了 10 行？？？原来并查集维护就行了啊。哭。

属于是推了一堆性质最后写了一个没有用到任何性质的做法

$t2$ 听题解发现我第一步根号都没想到…菜死了

$t3$ 巨神秘题，第一步就得观察出一些结论再贪心，感觉当时心态有点崩了，啥也想不到

还是不会分讨，有些看上去复杂的东西思路理清了写起来其实并不复杂啊

不能快速过 $t1$ 的话后面题是真没时间没心态看啊

$t1,t2$ 订了，$t3$ 大概懂了没写

 

5.3

day 4

看 $t1$ 感觉挺困难；$t2$ 又是神秘构造，感觉解很容易构出来啊！$t3$ 开始没看懂题，推了一下样例以为懂了，还是感觉困难

想 $t1$，发现按值域从两边往中间 $dp$ 就是对的？但好难写啊需要记录一堆东西，递归应该好写

吐了，好难写，尝试改递推写法，想了好久细节才写完，发现已经 10:00 了，交上去 $10pts$？

调了 40min 终于调出来了，然后发现前缀和优化一下就 $m^2$ 了，交上去 $60pts$

然后需要求阶乘，想起来以前 jsy 提过的分块打表，写完有 $80pts$

已经 11:00 了！想 $t2$，虽然手动很好构造，但并不会什么有道理的做法，想了想跳了

看 $t3$，写了暴力和 $A$ 性质就已经 12:10 了，发现暴搜没前途之后去想了 $B$ 性质，要求有交集，那点减边好像是对的？虽然有三段要分别算系数，然后套个线段树做类似 $dp$ 的东西就好了？尝试拓展到二维，发现不行，没有 $dp$ 顺序

没写完，遗憾离场

$80+0+15=95，rk41$

菜完了

出来问别人 $t1$ 怎么都做的这么快，听到转成图上做 $dp$ 就非常简单，好有道理啊！图论可以很方便的描述一些限制！

发现 $t2$ 大多数都是乱搞，额我没尝试过

$t3$ 发现点减边是对的啊！但还差一点观察。唉还是想的时间太短了！

为啥 $t1$ 不能做快点呢？

$t1$ 正解是科技不订了，$t2$ 先练练双极定向再写，$t3$ 懂了没写

 

5.4

day 5

$t1$ 看上去我挺擅长；$t2$ $t3$ 看上去都可做！

开 $t1$，$m$ 的范围大概率告诉你是矩乘，然后尝试压状态发现是可以做到的，猜了一个做法感觉状态不多，写了一手直接过了。才 8:50，赢！

$t2$ $t3$ 权衡了一下，$t3$ 部分分看上去不是很有区分度，决定先想一会儿然后磕 $t2$

没什么思路，开 $t2$

一眼想到经典 trick 转成 01 做，想了想会算概率了，那就有 $n^2$ 了，写写试试，交上去 $32pts$，此时 10:00

尝试优化，方向显然是 $ddp$，首先改了一下转移，我原来那个是从上往下做，应该没法 $ddp$，改从下往上合并就对完了，写了一下没问题

然后发现系数有点问题，涉及到一条链修改，有点 LCT 的感觉？

突然意识到暴力跳就是对的啊！均摊了

这就很能改 $ddp$ 了啊！编了一会细节准备开写，一看时间怎么 11:40 了？我是不是写不完啊

最终决定拼暴力了，写完有 52。最后写了 $t3$ 的暴力

$100+52+5=157，rk17$

为什么会有人编完了所有细节最后决定放弃呢？

为什么会有人前期思考那么顺最后打成依托呢？

不知道赛时在干嘛啊，怎么时间就过去了

这种 $t2$ 应该大胆写的啊！并不难啊

$t3$ 是第一步转化没想到，感觉思考时间太短了

$t1,t2$ 订过了，$t3$ 没完全懂

 

5.5

day 6

$t1$ 构造感觉很可做；$t2$ 看上去很困难；$t3$ 看起来可做

开 $t1$，手玩了一下应该构 $2\times 2$ 就是最多的，然后 $Y$ 的限制可以构一些 $3\times 3$ 的来调整，对完了啊开写！

交上去获得了高贵的 $5pts$，发现 $TLE$ ？不是我高精度怎么这么慢啊！

唐了一会意识到我一个高精度数的 $num$ 数组开太大了，导致它每次赋值常数太大了

然后一直修到 10:00 仍然只有 45pts，发现全构 $2\times 2$ 总数量都不够，那完蛋了！

手玩了一下别的发现都没有 $2\times 2$ 优，急了，感觉这题根本做不了啊

（原因是我上来就猜了个结论正方形肯定要比长方形优，然后一直没有去试 $2\times 3$）

看 $t2$，感觉暴搜有很多分，写！交上去竟然有 $50pts$？跳了

看 $t3$，显然是二分图匹配问题，尝试一下转独立集发现很可做！最后需要一个矩形加，查全局 $max$ 操作。啊没时间了只能写暴力维护这个

写完线段树 $n^2\log$ 发现跑 $3s$，哭了

最后果然没有通过 $n=3000$

$45+35+16=96，rk50$

别乱猜结论啊！感觉构造题 思路断的时候应该重新推一遍，忘掉之间得出的性质/结论

还有就是要擅用暴搜啊！

$t2$ 赛后才知道出题人说要卡掉暴搜过 { a , b } \{a,b\} {a,b}，当时去厕所了没听到…

感觉开 $t2,t3$ 的时候都是当成只拿暴力去思考的，结果好多不难的题也没怎么深入思考，这不行啊！

$t1$ 订了，$t2$ 懂了，$t3$ 没懂

 

5.6

day 7

看 $t1$ 很套路，显然是历史和的形式；$t2$ 又是神秘图论，但 $n$ 只有 $50$？$t3$ 神秘

想 $t1$，扫描线后维护时间戳发现就是一个树上颜色段均摊，啊啊我不会 LCT，只能 树剖+ODT 了，感觉会被卡常啊…

0.5h 写了 5k，又用 0.5h 调了两行代码，交上去发现 $80pts$，真被卡常了！

又卡了半个小时到 $95$，决定跳了

9:40 开 $t2$，感觉节奏还行啊

先尝试了一下在 $dfs$ 树上分讨，感觉是讨论不出来，想了想 $n$ 只有 $50$ ，做法大概还是基于暴力枚举

枚举边是 $O(m)$ 的，但如果我能让有用的边只有 $O(n)$ 条复杂度是不是对了啊

哎好像是 $n^5$，感觉应该是对的啊，常数不会很大

想了一下怎么让这个边数是 $O(n)$，很快猜到一个基于贪心的东西，每次找距离最近的，未访问过的点遍历

写了一手，打表发现数量好像确实是 $O(n)$。但我怎么输出不对啊！

修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修修

在调了 1w 个弱智错误后终于过了样例，怎么跑 $7\sim 8s$ 啊！先交吧，怎么已经 11:40 了

等了一会发现还没评到，尝试了一下卡常卡到 $4s$ 多，这不会和无脑暴力一个分吧，哭

赶紧来写 $t3$ 暴力，哎我怎么不会 $nq$？噢枚举值域然后并查集维护一下

剩 5min 调过了小样例，交。哎我 $t2$ 怎么保龄了？

wc 我交到 $t1$ 上了，赶紧改过来了

$100+40+0=140，rk30$

$t3$ 不知道怎么挂了呜呜呜

感觉这把还是，好不容易有个节奏很好的前期，后面又打炸了

$t2$ 正解是 $\frac{n^5}{w}$… 赛时思考方向很对啊！应该再多尝试一下有没有更好的做法，不该急着写的

$t3$ 听题解是很可做的题，唉想的时间还是太短了，被 $t2$ 的 sb 错误卡住了

$t1$ 过了，$t2$ 懂了还没写完，$t3$ 差不多懂

 

5.7

day 8

爆炸

看 $t1$ 有点眼熟，$t2$ 很有意思，$t3$ 是高深的线代，不太可做

开 $t1$，尝试了一些经典套路，还是不会做。中间突然意识到由于括号序列固定，问题可以转化成很简洁的形式：有若干的关键点，每个关键点需要在前面选择一项任务，要求权值和最小

感觉这是很本质的转化了，想了一下感觉线段树能直接维护匹配，开写

写完发现假了！修改对匹配的影响是很大的，复杂度不对

修修修修修修修修修修修修修修修修修修修修修修修修修修修

一直觉得这已经是很本质的转化了，这都做不了那这题就没做法了，所以一直在磕

中间尝试开了一下 $t2$，好像直接容斥有很多分？写了一半发现假了

最后又来开 $t2$，想到了之间不会的用图来描述限制，发现能做了！直接 $dp$ 就行。而且看上去很能做有 $k$ 的限制？

没写完，遗憾离场

$55+0+0=55，rk?$

菜死了

为啥都说 $t1$ 的修改是能直接维护的啊？我怎么总感觉影响很大… 又学习了一下，感觉大概是不关注具体的匹配，只关注整体的权值和就能维护了

$t2$ 下午听题解发现想的一样，所以我为啥不开 $t2$ 呢？

$t3$ 神秘题，完全不懂

$t1$ 没完全懂，$t2$ 懂了，$t3$ 完全不懂

 

总结

我们发现这 $8$ 天没有过掉 任何一个 $t2$ 或者 $t3$

经过前一段的训练以为自己水平有长进了，结果发现压根啥也不会啊

感觉模拟赛打的少了，不习惯高压状态下思考和写代码，心态很差

还有一些能力上的缺失，不会 分类讨论