专栏文章

20251127

1123456ph
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimzbrg0
此快照首次捕获于
2025/12/01 18:01
3 个月前
此快照最后确认于
2025/12/01 18:01
3 个月前
查看原文

T1### T1

首先，所有字母均满足要求的卡片一定可以直接放上去。
然后，所有非要求字母被挡完的卡可以放上去。
就变成考试n*m<=1e6的那道题了。
（以上为考场注释）
转化成以前的一道题。这是容易的。然后就做完了。虽然说绕了一步，但是其实能够接受。

T2

先搓了一个 O(n2)O(n^2) 的启发式合并。
加了个小优化，n(n+1)2\frac{n(n+1)}{2}。
加了个小剪枝，n(n+1)4\frac{n(n+1)}{4}。
加了个小优化，n(n+1)9\frac{n(n+1)}{9}。
优化不动了，特判了重复的询问。
过了。
注：赛后，chenyichen给出了证明，证明此程序是对的。时复为 O(nnlog⁡n)O(n\sqrt n \log n)。
这告诉我们:赛时不要害怕，随便创就完事了。况且这份代码肯定可以拿75的部分分。

T3

最开始秒了树的解法，然后苦想100pts。
最后在想到T2的同时想到T3正解（只需要加一个缩点就行了）。
写完T2只剩20min给T3。然后我忘记tarjan怎么打了！！！！！！
复习了一下午的连通性问题。
  1. 复习了tarjan全家桶（边双，点双，强连通）
  2. 复习了边双的树上差分解法，作为备用。
  3. 学习了点双的树上差分解法，写了题解，作为备用。
  4. 复习了kosaraju，作为tarjan的上位替代。

T4

奇妙，只有我想到了 O(n3)O(n^3) 没想到 O(n2log⁡n)O(n^2\log n)。
从 O(n4)O(n^4) 优化到 O(n3)O(n^3) 需要发现一个点只会更新一个答案。
我发现了，然后就忘记了这一点。
然后我考虑数据结构优化，但是

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...