省选游记

目标：比 THUWC 总分高。

(upd：只达到 Day 1 分数)

Day 0

试机日。

快速敲了 WC T3 40pts 暴力

8:30 注意到有个 graperm （graph permutaion），图排列必然是拓扑序题目。

8:32 开题。

三道二元组。

T1 是不想做的中位数，还需要离散化。

T2 是可达点对，10^5 范围只可惜不能用不确定性算法。

T3 又是字典序最小，不想做构造。

于是依照惯例，1 小时 40 分钟过 T1。T2 以为随机打乱分块剪枝就是 k-d tree 的复杂度，但不对。T3 啥都不会。

不过 Day 1 难度是实实在在的好处，毕竟谁也不想看到自己的正解假了对吧。

怎么还出图容斥？

~T1 不会，T2 不会，T3 不会~

好吧，最近怎么都把神秘贪心放 T1，看到 B 性质知道是建筑抢修要按时间排序，觉得 C 性质是关键，后来想到用优先队列或 set 维护时间，如果有箱子挡着就想办法让箱子先走，结果贪心策略是整体移动？那我不会做了。

T2 不知道通过点集怎么状压统计存在外向树的子树个数，时间复杂度应该是 O(n^3 2^n) 或 O(n3^n) 的，如果枚举独立集之类然后容斥系数和什么大小有关时间复杂度可以是跑不满的 O(n^23^n) 卷积，于是只打了最暴力的 24 pts。

T3 是可达序列问题，不是，为什么省选题目的要素重复率这么高？只会 bfs，不知道能不能多拿一点分。

我输了，但我快要赢了。