![2023年12月15日总结](/img/20231215110118.webp)
2023年12月15日总结
![](https://picx.zhimg.com/v2-9e83e1fd23eccdb98450679841a3a4bc_xll.jpg)
总结
冬月初三,早起,天气清冷。气温骤降,秋风瑟瑟。今天是计数类 dp,但是先来回顾一下上次的动态 dp。【模板】动态DP 动态树分治(加强版) ,两个
全局平衡二叉树 yyds!很好的写法,OI-WIKI 上的写法好神奇,写起来好▒▒。
计数类 dp
收藏一下 alex-wei 的 dp 大杂烩()
好文章捏,抄了。
P4590 [TJOI2018]游园会 要满足不能出现 NOI。虽然是 dp 套 dp,但应该还是算计数 dp 吧,嘻嘻。
这种有奇奇怪怪限制的计数题,从动态规划的角度切入通常比较顺手。****
接下来是来自 dzy 的计数类题目题单。
Codeforces 17C 相当于原子序列复制。和上面 dp 套 dp 差不多,本质上都是构建自动机来转移状态,从而满足限制。比如这道题就是限制子序列,每次的转移就是字符,这道题是序列自动机,状态很简单,就是原串上的位置。P.S. 感觉这种 dp 写向后更新都比较容易啊。
Codeforces 474D 简单的 dp 题目。
Codeforces 486D 也不难,觉得没有蓝题的难度,但是 wa 了。你猜怎么着?我定义一个函数,模意义下取模,大于等于 mod 要减 mod 对吧,我减的 y。awsl。
ABC104 D 倒过来乱搞一下就行,也不难。
Codeforces 176B 容易发现就是一个字符串转,然后有一些模数。由于字符串很短,可以暴力找结束位置,然后暴力
dp 即可。看题解发现可以优化。定义 表示这一步到答案或不是答案的情况,转移即可。 [ZJOI2012] 波浪 发现是黑题,害怕。难度骤增。积累经验,挖坑 dp。(自己取的名字)。此题可能需要高精度小数。但是不想打,用
__float128
淦,发现 TLE 两个点,采用数据类型分治,精度小于 8 位的使用double
。简单说明一下挖坑 dp,最开始没有理解,后来发现好厉害。就是维护一些段,每次加进去一个点相当于往一些段间加一个点进去,这个点可以把两边的段扯到一起,就像缝衣服一样,然后 dp 的时候再维护一下两边的边界就好。[TJOI2015] 组合数学 怎么这道题是紫题上一道是黑的啊~。参看题解,首先是一种贪心的方式。就是可以从上面留下来,然后不够就向左边要。类似于网络流?这道题我第一眼的做法其实是模拟最长不下降子序列之类的做法。考虑另一种做法:Dilworth 定理 题解 P3974 【[TJOI2015]组合数学】 ,参看这篇题解。有:
- 对于一个偏序集,其最少反链划分数等于其最大链的大小。
- 对于一个偏序集,其最少链划分数等于其最大反链的大小。
- 因此可以从右上向左下转移。
此题还可以用线性规划对偶做。不是很会。
后记
还有一坨生成函数没搞。好多好多。今天就先结束了。明天还要测试,后天还要 THUPC。晚安( ̄o ̄) . z Z。
- 标题: 2023年12月15日总结
- 作者: 混氏新子
- 创建于 : 2023-12-15 22:38:08
- 更新于 : 2023-12-15 23:03:17
- 链接: https://blog.huasushis.cn/2023/2023年12月15日总结/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。