佛山专业的免费建站,建站哪家好就要用兴田德润,湖南网站排名优化公司,服装品牌网站建设处理位运算常用的方法#xff1a; 拆位法#xff08;一位一位的处理#xff0c;通常题目中会给出元素的最大是2的的多少次幂#xff0c;当然也有给10的次幂的#xff0c;自己注意一下就可以了#xff09; 常用的思想 #xff1a; 算贡献。 异或的性质#xff1a; A^A0 …处理位运算常用的方法 拆位法一位一位的处理通常题目中会给出元素的最大是2的的多少次幂当然也有给10的次幂的自己注意一下就可以了 常用的思想 算贡献。 异或的性质 A^A0 A^0A 异或 具有类似前缀和的性质。可以通过前缀异或 求区间的异或值 洛谷lqb 题意对于一组数求所有子串的异或和 之后求和 因为 异或的前缀和的性质。所以区间的异或值可以表示为前缀的异或 通过转化其实就是求异或前缀数组两两异或的 和。 我们 一位一位的考虑。 对于某一位来说 假设前缀数组中的元素 这一位上的数字是 0 0 1 0 1考虑两两异或只有 1 和 0 能产生一个1. 那么 这一位对答案的贡献是 0的个数*1的个数 *这一位的权重。 将每一位的贡献加起来。 最后不要忘记每一个B元素都要和0异或一下。这个从上面的数学公式中可以看出来。这个对应的就是 一个前缀区间的异或值。体现在代码中就是cnt01
#include bits/stdc.h
using namespace std;
#define int long long
void solve()
{int n;cinn;vectorinta(n1);for (int i1;in;i)cina[i],a[i]^a[i-1];int ans0;for(int i0;i20;i){int cnt10,cnt01;for (int j1;jn;j){if ((a[j]i )1)cnt1;else cnt0;}anscnt0*cnt1*(1i);}coutans\n;
}
abc 365 E 题意根据 异或前缀的性质可以转换一下。 乍一看这个很像 B数组两两异或的和。但是我们可以注意到 并没有相邻两项的异或。两两异或的结果很好求。 我们只需要对答案减去B相邻两项的异或。就可以了。 有一个的小细节 B数组的最初的元素是B0所以数组开到了n1。用数学公式表示很清楚~~
#include bits/stdc.h
using namespace std;
#define int long long
void solve()
{int n;cinn;vectorinta(n1);for (int i1;in;i)cina[i],a[i]^a[i-1]; int ans0;for (int i1;in;i)ans-(a[i]^a[i-1]);for (int i0;i30;i){int cnt[2]{};for (int j0;jn;j){int x(a[j]i) 1;cnt[x];}anscnt[0]*cnt[1]*(1lli);}coutans\n;}
添加链接描述 意外发现了洛谷上的这个异或的题单。脑筋急转弯一下。 1所有 子数组的元素和 的和。考虑每个元素的贡献是包含这个元素的子数组的个数 对于下标从1开始的情况**包含这个元素的子数组的个数是i*n-i1).**累加起来就可以了。 2求所有子数组的异或和 的异或和。因为X^X0,所以只有子数组中出现奇数次的数字才会产生贡献。利用map来存储。
void solve()
{int n;cinn;mapint,intmp;int t,tt;for (int i0;in;i){cint;tt(i1)*(n-i);mp[t]tt;}int ans0;for (auto [x,y]:mp){if (y1){ans^x;}}coutans\n;
}3.所有子数组的异或和 的和。这道和上文第一题一样。 4.不会先略过去 下面的题都是子序列 5.和1的子数组不同这次是所有非空子序列的元素和 的元素和。 对于第i 个元素包含这个元素的子序列有 2^(n-1),相当于剩下的元素都有选和不选两种选择。 所以将每个元素的贡献加起来就可以了 6.所有非空子序列的 异或和 的异或和。只有贡献奇数次的数值才会产生贡献。 每个数贡献的是 2^(n-1) 次只有n1的时候是奇数。输出这个数值就可以了。其他时候都是零。 7.计算非空子序列的 异或和 的和 。也是拆位思考。如果这一位没有1那么贡献是0.如果有1那么贡献是2^(n-1) 再乘上权重。不是很明白怎么算的贡献先贴上灵神的题解日后再来想想。
8.计算 非空子序列 和的异或和。 考虑枚举累加每个子序列和的可能值的贡献 对当前序列数和sum得到该和的方案数为奇数时贡献为sum否则为0 考虑使用01背包推导序列数和的方案数的奇偶性 dp[j]表示装满j 的方案数。
#include bits/stdc.h
using namespace std;
const int mod1e97;
#define int long long void solve()
{int n;cinn;vectorinta(n);int sum0;for (int i0;in;i){cina[i];suma[i];}vectorintdp(sum1);//装满容量为j的背包有多少种方法dp[0]1;for (int i0;in;i)for (int jsum;ja[i];j--){dp[j]dp[j-a[i]];}int ans0;for (int i1;isum;i){if (dp[i]1)ans^i;}coutans\n;}
