20251126 总结

starfallen · 2025-11-26 21:39:31 · 个人记录

T1

一眼题。写完了发现可以把 dij 优化成 01bfs，但是算了一下时间复杂度可以过，就没管了。

T2

简单拆贡献。最后时间复杂度是 O(n\log n\log V)，其中，n=5\times10^5,V=2^{30}。没算时间复杂度，感觉能过。然而最后洛谷上确实过了，BBC 上没过。在最后 10 分钟我知道了是在 BBC 上测，然后一眼看出发现代码有一个地方可以优化，最后时间复杂度就是 O(n\log V)，但是没写完。当时考场上想着反正能过，就不管了。

当然，最后评测时候肯定不会用 BBC 的机子，相应的，肯定也会开大 n 的范围，这样我就会去思考优化了。这个优化不难。

T3

神秘题目。考场上大样例下发了 50 分的表，我就没想着去怎么做了。发现 DP 不是很好转移，思考一会无果后就放弃了，直接写了 50 分走人。这道题的难点在于将 DP 转移的系数单独拎出来考虑。只要你想到单独拎出来了，就不难发现这是另外的一个问题，也可以 DP 求解。很妙的思路。

T4

扫描线是容易想到的。现在我们的问题是有四组矩形，每组有 O(n) 个。我们想要求这四组组内并之后的交。这是不好维护的，我们好维护的只有矩形面积并。

接下来就是精髓，把交用容斥转化为并，然后就好算了。这是最精髓的一步。我们有两种互反的信息，一般使用容斥或者反演就可以在信息集不大的情况下转化为另一种情况。这种思维（将难以维护的信息转化为好维护的信息）是很重要的。况且这种方法也很巧妙，不是吗。