[做题记录] JOISC2020 完结了!

终于是做完了JOISC 2020, 补完了这场当年我只有18分的比赛。
我做到了, 我不再是从前那个我了
下面是简要题解。

Day1T1

考虑\(n^2\)的dp里面可以发现固定一维另外的是区间, 利用这个性质只维护端点从而去掉一维。

Day1T2

随机或者2-sat分析下。

Day1T3

对插入线段树分治, 对于每个静态区间, 处理每个操作影响的范围, 这样只需要一个取max的线段树。
在网上看到还有的做法是对三角形分治, 有没有鸽鸽教教啊/kk

Day2T1

\(n^2\)是简单的, 利用二分图的性质可以快速二分出来一个点向已有集合的边, 由于边不多, 复杂度单\(\log\)。

Day2T2

启发式合并, 注意同时维护出边入边实现会简单很多, 自己实现复杂了。

Day2T3

直接观察结果, 通过对结果构造一个形成过程, 然后讨论转移, 注意卡特兰数的转化。

Day3T1

有简单的笛卡尔树dp做法, 还有一个直接升序考虑的带悔贪心。

Day3T2

link

Day4T1

傻逼题。

Day4T2

随最大独立集即可。

Day4T3

很离谱的转化为最短路???
然后搞个线段树维护一下, 因为每个点会被更新一次, 所以大力线段树暴力就行。

上一篇:HTML标签说明


下一篇:【模板题】Bellman-Ford(有边数限制的最短路)