Maximum And Queries (hard version)
算法本质
思维、dp
题目大意
给定长度n的数组a[]，接下来有q轮询问（询问之间独立），每次会给出k，玩家可以至多进行k次操作：
- 选择数组
a[]某个元素使其值+1
输出最大化a[]所有值的按位AND值。
a[] n q <= 1e6
k <= 1e18思路推演
这个题十分有意思，让我们先来发散一下思维：
- 每次操作需要在根号级别的复杂度下输出答案，所以肯定需要离线做或者预处理
- AND方式的求和，让我们按位思考，且具备贪心属性（如果可以选择更大的二进制位，则选择更大的）
随便拿些样例模拟一下，发现一个特征，就是如果有二进制（左侧为高位）：10010、101、1，如果答案能选择的最高位暂时是二进制第三位，即100，则观察第一个和第三个数，其在二进制第三位上都是0，贪心地想，我们可以理解为其选择后的值变成了0。
顺着这个思路想，如果我们已知ans的值和某个元素的值a[i]，是可以计算出a[i]需要的最少操作数的：
- 找到二进制下的最高位，满足：
a[i]这一位是0，ans这一位是1，假设这是二进制的第x位（注意这里的x是1下标开始的） - 如果不存在，花费即是0
- 如果存在
x，设变量$mask = 2^x-1$花费是：$cost_i = (ans \& mask) - (a_i \& mask)$
这是一种逆向的思维，因为已知k和a[]来直接求ans比较困难。
一个比较顺畅的想法是，预处理出所有的ans即可。注意观察a[]的值，其在1e6以内，但是k很大。如果$k + \sum_{i=1}^n a_i \ge n * 2^{20}$，那就可以说明所有的a[]值都是会被利用到的，可以使用$\left \lfloor \frac{k + \sum_{i=1}^n a_i}{n} \right \rfloor $来求解。
反之，则最终答案一定小于2^20^，我们仅需处理2^20^以内的所有ans值即可，接下来构建dp。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)