![2023年12月1日总结](/img/20231201213505.webp)
2023年12月1日总结
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
总结
今天是12月的第一天!美丽,晶莹的冬天!今天早上起来把昨天那道 【ULR # 1】光伏元件 给改了。这里说几点要注意的地方。建模网上都有,也比较典型,这里就不说了。就是这道题我先写了原始对偶,没过,然后写 ssp,还是没有过。然后我开始怀疑人生了?后来我发现,对于上下界相等的边,就不要再加到残量网络里了,会浪费很多资源,就是这个原因 T 了很久。还有这道题输出方案也有点麻烦,但是写一写还是能过的。
接下来是今天的内容![[数据结构]]。
[[左偏树]]
这个之前写过一次,在第 K 短路的时候用过可持久化的版本。简单易写。
模板题:
顺便复习以下第 K 短路:
复杂度是
写起来还是很顺溜的。只不过第一次交数组开小了 RE 了(就给当成一遍过吧嘻嘻)。主要是 OI WIKI 上面说空间复杂度是
[[K-D Tree]]
看 OI-WIKi 上面说,
多选手会使用替罪羊树结构来维护。但是注意到在刚才的复杂度分析中,要求儿子的子树大小严格减半,即树高必须为严格的
,而替罪羊树只满足树高 ,故查询复杂度无法保证。
所以替罪羊快离开我们吧!我们钟爱二进制分组!
还有注意求最近点最远点之类的题目最好不要用 K-D Tree,一般用于想不到正解而骗分的办法,请注意。
[[虚树]]
推荐用栈构建。
「SDOI2011」消耗战 :做过,今天就不打了。
来打一道 「HEOI2014」大工程 。
怎么说呢?三个 dp,组合起来写起来有亿点点恶心,但是还好。注意用栈搞虚树不要搞错了,要判断栈顶前一个。如果栈从 0 开始的话要注意越界的问题,建议不要从 0 开始。
[[树套树]]
P3380 【模板】二逼平衡树(树套树) :打过,不喜欢再打一遍。
P1975 [国家集训队]排队 :但是很可惜没有打成树套树,因为我一眼看出暴力可以碾标算()。
P3332 [ZJOI2013]K大数查询 :还得是 ZJOI。发现可以整体二分,但是今天是树套树,就不打整体二分了。树套树过了!整体二分留着复习整体二分的时候再来写,打个标记。
中场休息。
转换一下脑子,把昨天没学的矩阵树定理搞了。
[[矩阵树定理]]
「HEOI2015」小 Z 的房间 打一下板子。整数行列式求值还是很有趣的呢!
后记
今天又是充实的一天呢!迎接美丽的12月!辞旧迎新之际(怎么就辞旧迎新了),星星闪耀!
AI:
1 | OI路漫漫其修远兮,吾将上下而求索。 |
- 标题: 2023年12月1日总结
- 作者: 混氏新子
- 创建于 : 2023-12-01 23:36:13
- 更新于 : 2023-12-15 22:44:04
- 链接: https://blog.huasushis.cn/2023/2023年12月1日总结/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。