可删除背包（计数类）： P4141
可删除背包（计数类）： P4141
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028419
https://www.luogu.com.cn/problem/P4141
看完第一眼想到打分治，然后记得以前打abc时好像见到过一种可撤销背包。
使用条件：
-
计数类，非最优性问题
-
物品之间顺序无影响
因此我们直接撤销是对的
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-24
可删除背包（计数类）=＞转移数组进行展开：ABC321F
可删除背包（计数类）=＞转移数组进行展开：ABC321F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133219375 https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前 但删的话应该是从前往后减 为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次 减的话为了保证每个被删的数只减一次，应该从前往后。 考虑前 iii 个已经被还原了，那...
2024-01-15
原根 + 背包 + bitset优化 + 二进制分组：0115B
原根 + 背包 + bitset优化 + 二进制分组：0115B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260 http://47.92.197.167:5283/contest/451/problem/2 原根： g1,…,gp−1g^1,\dots,g^{p-1}g1,…,gp−1 在 mod p\bmod pmodp 意义下取遍 1∼p−11\sim p-11∼p−1 。在 ppp 为质数时， ggg 不超过 p14p^{\fr...
2022-02-17
【一本通OJ 1601：【例 5】Banknotes】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905471.html 题目链接 题目 原题来自：POI 2005 Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 nnn 种面值的硬币，面值分别为 b1,b2,⋯ ,bnb_1, b_2,\cdots , b_nb1,b2,⋯,bn 。但是每种硬币有数量限制，现在我们想要凑出面值 kkk，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...
2024-08-27
8.26 T3日记和二叉搜索树（背包 + bitset优化 + 分治）
8.26 T3日记和二叉搜索树（背包 + bitset优化 + 分治） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141610732 http://cplusoj.com/d/senior/p/NOD2301C 很容易转化为对于一个节点的儿子们要尽量平均分 这是经典的背包问题 然后这个背包又可以经典bitset优化 但是bitset开太大也会死掉，所以你可以手动分治
2021-11-24
【P1270 “访问”美术馆】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=maxy∈xmaxi=0smaxj=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...
2023-12-16
容量很大体积很小背包
容量很大体积很小背包 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028489 在 https://blog.csdn.net/zhangtingxiqwq/article/details/132216843 提到过关于容量很大体积很小的背包问题，现在简要梳理一下： 先贪心选 选了的就上可删除dp，没选的就是朴素dp，把dp范围控制在 [L−m,L+m][L-m,L+m][L−m,L+m] 以内 加入过程直接二进制分组优化