工信部查网站备案,网站建设推广优化,佛山做网站的公司哪家好,宁波网站建设与设计制作题解#xff1a;CF1946D#xff08;Birthday Gift#xff09;
题目翻译#xff1a;给定一个长度为 n n n 的数组 a a a 以及一个数 x x x#xff0c;请找出最大的 k k k#xff0c;使得数组 a a a 可以被分成 k k k 个部分#xff0c;并且将每个部分中所有元素异…题解CF1946DBirthday Gift
题目翻译给定一个长度为 n n n 的数组 a a a 以及一个数 x x x请找出最大的 k k k使得数组 a a a 可以被分成 k k k 个部分并且将每个部分中所有元素异或起来的结果按位或最终的结果小于等于 x x x。
先观察题面发现其中出现了两个位运算——按位异或和按位或。它们有一个共同性质就是在二进制下每一位之间互不干扰因此我们可以按位分别考虑因此我们可以从左往右遍历每一个二进制位。
我们知道根据或运算的规则只要这些段中某一个段内元素异或起来为 1 1 1则最终的结果一定为 1 1 1换而言之如果现在数组中这一位为 1 1 1 的数的数量为奇数也就代表这一位的计算结果不可能为 0 0 0则最终结果一定为 1 1 1此时如果 x x x 的这一位为 0 0 0则最终计算结果一定大于 x x x所以我们的遍历需要到此为止否则不需要进行任何操作直接去往下一位否则即数量为偶数代表着这一位的计算结果可能为 0 0 0此时如果 x x x 这一位为 1 1 1我们可以尝试更新答案具体怎样更新我们稍后再说就是代表让这一位变成 0 0 0前面的都与 x x x 相等此时计算结果无论后面长什么样都一定小于 x x x当然这并不意味着我们要停止遍历因为我们还有另一种情况——就是这一位选择 1 1 1从这一位到它左边全部和 x x x 完全相同我们不对数组进行任何改变只是进入下一位否则也就是 x x x 这一位为 0 0 0那么就只能想办法让计算结果变为 0 0 0按照对于这一位分段的方法修改数组如何分段和修改也是稍后再讲。通过这种方式求出答案即可注意如果一次答案更新都没有就说明答案应该是 − 1 -1 −1。并且我们不难发现这种方法没有考虑恰好等于 x x x 的情况因此我们先要让 x再进行一系列操作。
剩下的就是更新答案、分段和修改了。因为我们要让 k k k 最大也就是让越少的元素被合并越好因此我们的分段方发如下将所有的对应位为 1 1 1 的数分别编号 2 n 2n 2n 号和 2 n 1 2n1 2n1 号中间包含左右端点的元素被分到一组剩余的不进行合并这就是更新答案和分段的方案。因为这样合并恰好让两个 1 1 1 排在最左侧和最右侧因此这一段不可以再进行任何拆分也就是说这一段的所有点可以视为一个点这个点的值就是这一段中所有点异或起来的结果。用这种方式进行修改数组。
在实现过程中位数用到 0 0 0 到 30 30 30 就可以了并且我们可以用 ((a[j]i)1)1 来判断 a j a_j aj 的第 i i i 位是否为 1 1 1。
Come on代码走起
#includebits/stdc.h
#define N 110000
using namespace std;
int t,n,x,a[N];
int b[N];
int main(){scanf(%d,t);while(t--){scanf(%d%d,n,x),x;for(int i1;in;i)scanf(%d,a[i]);int ans-1,cnt;for(int i30;i0;i--){cnt0;int zt0;for(int j1;jn;j){if(zt0)cnt,b[cnt]a[j];else b[cnt]^a[j];if(((a[j]i)1)1)zt^1;}if(((xi)1)1zt0)ansmax(ans,cnt);else if(((xi)1)0zt1)break;else if(((xi)1)0zt0){ncnt;for(int j1;jcnt;j)a[j]b[j];}}printf(%d\n,ans);}return 0;
}
