• 欢迎光临~

【考试总结】2022-07-30

开发技术 开发技术 2022-07-30 次浏览

水晶

异或和为 (0) 可以通过 (n-1) 个乱选,钦定一个抵消来实现。

那么枚举这 (n) 个数字的 (rm LCP),求 (f_{i,0/1,0/1}) 表示前 (i) 个数字有奇数/偶数个选择这位填 (1) 以及是否有一个选择这位低于上界 (M_i) 的。

转移不再赘述。

根据是含义处理边界,例如 (n) 个数字有奇数个当前位是 (1) 那么停止枚举 (rm LCP)

物品

区间答案为 (displaystyleprod_{i=1}^n (cnt_i+1))(+1) 表示不选,否则只能选一个

分块。

预处理每个块的左端点开都得后缀每个 (a_i) 都出现了多少次,在 (Theta(nsqrt n)) 的空间复杂度下可以做到 (Theta(1)) 求一段块中任意元素出现次数

预处理每个块左端点到它开头的后缀的每个前缀的答案,时空复杂度都是 (Theta(nsqrt n))

对于区间长度小于根号者暴力,否则先继承询问右端点到询问左端点所在块后面一个的答案,并且把指针从块尾挪到 (L) 时动态维护答案即可。

颜色

重量为 (0) 的物品提前选上。特判一些边界,比如 (L) 大于同号 (a_i) 的和

尝试构造一个选出物品数量最多且总重量 (le L) 的解:

预选所有重量为负的物品,之后每个正 (i) 可以加入,给数量加一,重量 (+i)。为负的元素可以给数量减一,给重量加 (i)。贪心使得增量最大,减量最小。于是先从 (1sim n) 加入,删除则按照 (-nsim -1) 的顺序

注意这个过程要达到的目的是 数量最大

当限制变成 (=L) 时需要进行一些调整。可以发现对于贪心策略得到的选值方案而言,等于 (L) 的方案和它在重量上差距在 ([-m,m]) 之间,否则可以通过添加元素来减少这个差量

于是调整的物品数量是 (Theta(m)) 级别的,将背包上界卡到 (m^2) ,选中的元素可以退下,价值 (-1) ,重量是 (-w),没选中的可以选中,价值重量为 ((1,w)) 。二进制分组优化即可

程序员灯塔
转载请注明原文链接:【考试总结】2022-07-30
喜欢 (0)