背包DP

今日继续垫底系列 T1题意理解错误暴力写挂 T2怒敲 $n \le 4$ 求根公式然后发现答案还得排序。。 $\text{score：0 + 10 + 0 = 10 rk：27/27}$ Problem A：游戏题目描述ysgh是一名Herthstone大师。现在他遇到了一个很严峻的问题： 场上总共有 $n+m$ 个随从，其中ysgh控制着 $n$ 个，对手控制着 $m$ 个。每个随从有自己的血量。 如果ysgh在这一回合成功解掉了对手的所有随从，则ysgh获胜。否则下一回合对手直接骑脸，ysgh就会输掉。 ysgh现在手里仅有一场牌，属性如下： 进行 $d$ 次，每一次等概率随机一个在场上的未死亡随从（包括自己和对手的）并且对其造成一点伤害。若不存在未死亡随从，则不进行此次攻击。一个随从未死亡当且仅当其血量严格大于 $0$。每一次攻击后，所有血量小于等于 $0$ 的随从立即死亡。 ysgh想要知道，他有多大概率可以取胜，也就是多大的概率使得在使用这张牌后，对手的随从全部死亡。 特别提醒：由于描述与实际游戏规则有出入，一切以实际题面描述为准。 数据范围对于所有测试数据，满足 $1 ...

首先有一个性质 对于 $n \ge 11$，操作 $1$ 必定有解 一个来自 $\text{Okami}$ 的严谨证明： 考虑互不相同的数 $x, y, z, …$，则有 123xx y x+yx y z x+y x+z y+z x+y+z 也就是对于 $n$ 个互不相同的数它们显然可以拼出 $2^n - 1$，那么根据抽屉原理，则有 $2^n - 1 \ge 1000$ 时必定有解，则命题成立 那么剩下的就直接 $\text{bitset}$ 优化背包就好了（注意可以直接背包因为若集合 $X$ 和 $Y$ 同时选了一个数，那么它们同时去除该数也是相等的），至于操作 $2$ 的影响则直接树状数组统计每个数要立方几次，由于 $\bmod V$，那么直接倍增处理即可 单词询问复杂度 $O (\frac{(r - l + 1)^2V}{32})$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 ...

题目描述$01$ 背包，数据范围 $1 \le n \le 1e06, 1 \le weight_i \le 300$ 题解神仙 $01$ 背包 考虑重量较小，故可以考虑根据重量分层处理 令 $f_{i, j}$ 表示使用前 $i$ 个重量，总共花费 $j$ 容量的最大价值 容易注意到在同一重量中显然要优先选择价值大的，故将每种重量按价值排序，令 $sumv_{i, j}$ 表示重量为 $i$ 的前 $j$ 大的价值前缀和，则有$$f_{i, j} = \max\limits_k \{f_{i - 1, j - ki} + sumv_{i, k}\}$$然后（通过看题解）可以发现，因为是 $j - ki$，故可以考虑按照 $j \mod i$ 分类处理，这样是满足决策单调性的 至于证明，为了方便可以将式子简化成 $f_i = \max \{f_j +sumv_{i - j}\}$ 的形式，然后用反证法或是四边形不等式都容易证明 那么最后就可以用决策单调性的套路代码或者是用分治解决了 分治比较简单，大概就是看在处理区间 $[u, v]$， $[l, r]$ 决策区间内对于 $mid$ 位 ...