可删除背包（计数类）： 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的博客！
相关推荐
2021-12-08
【CF577B Modulo Sum】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15664786.html 题目链接 题目 You are given a sequence of numbers a1, a2, …, an, and a number m. Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m. 给出 111 ...
2021-12-08
【HDU 5550 Game Rooms】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15662976.html 题目链接 题目 Your company has just constructed a new skyscraper, but you just noticed a terrible problem: there is only space to put one game room on each floor! The game rooms have not been furnished yet, so you can ...
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，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...
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] 以内 加入过程直接二进制分组优化