百度免费建立网站吗,计算机的专业有哪些,wordpress 汽车 模板下载,网站托管好吗题目内容 原题链接 给定一个长度为 n n n 的数组 a a a#xff0c;问有多少个连续子数组的和满足区间加法和等于区间异或和。
数据范围 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105 0 ≤ k 2 20 0\leq k2^{20} 0≤k220
题解
考虑异或是不进…题目内容 原题链接 给定一个长度为 n n n 的数组 a a a问有多少个连续子数组的和满足区间加法和等于区间异或和。
数据范围 1 ≤ n ≤ 2 ⋅ 1 0 5 1\leq n\leq 2\cdot 10^5 1≤n≤2⋅105 0 ≤ k 2 20 0\leq k2^{20} 0≤k220
题解
考虑异或是不进位的加法所以当存在多个数的同一数位都为 1 1 1 则区间异或和必然小于区间加法和。
考虑双指针当区间存在两个数及以上的数的某一数位都为 1 1 1 那么则移动区间每次双指针移动后的合法状态的所有子数组必然也合法。
时间复杂度 O ( n ) O(n) O(n)
代码
#include bits/stdc.h
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin n;vectorint a(n);for (int i 0; i n; i) cin a[i];long long ans 0;int add_sum 0;for (int i 0, j 0; i n; i) {int tmp a[i] | add_sum;add_sum a[i];while (j i add_sum ! tmp) {add_sum - a[j];tmp add_sum | a[i];j 1;}ans i - j 1;}cout ans \n;return 0;
}
