成绩
| rank | name | score | T1 | T2 | T3 | T4 |
|---|
|
19
19
19 |
T
J
H
TJH
TJH |
200
200
200 |
100
100
100 |
100
100
100 |
0
0
0 |
0
0
0 |
做题时
看了一下 T1，确认数据范围和题意之后发现就是模拟。
看了一下 T2，看了一下发现好像就是个树形 DP，然后拿个堆搞一搞就可以。
看 T3，一开始想可以暴力搞，看了一下复杂度发现超了
7
7
7 倍，感觉不太行？
然后就想了一个 Trie 的做法。
看 T4，一脸茫然，表示不会快速判断一个图是否是二分图。
然后打完 T1T2 就调 T3，调着调着 WYC 说 T4 是线段树分治洛谷模板题？
我：？？？
然后继续想，发现就是不会判断二分图。
然后就继续打 T3，打完过了一会 WYC 又说 T4 判断二分图就是扩展域并查集的事。
然后自己想了一会似乎想到了做法，然后就码了起来。
（由于思路都是别人说出来听到的就不交了）
（然而当时的撤销似乎有问题，也是没有分的）
预估：100+100+100+0=300
出成绩
好耶 T3 MLE 了，然后似乎开小之后就不行了。
（绷不住了）
然后暴力竟然就是正解，我裂开来。
然后就继续调 T4。
讲题
其实都没有什么太大的问题，T3 有一个很优的剪枝就是一开始去匹配的串从最短的字符串里面拿。
可以直接从一千多秒直接飞到一两百秒。
然后继续调 T4，后来去 luogu 看发现不能路径压缩，改了一下就搞定了。
然后就去把 T3 暴力也写了出来。
总结
感觉自己对复杂度的把握还是不行，有的时候差一点点的话加剪枝可能就是正解了。
做人就要勇一点，相信剪枝的力量
做出来的题目博客
Brothers
Crisis
Word
graph / 二分图 /【模板】线段树分治
|