前缀和异或

数据结构 / 前缀和异或
字数统计: 1.4k   |   阅读时长≈ 6 分钟

前置知识

前缀和，压位，位运算，异或

一些性质

根据异或的性质很容易得以下结论

如果[0, l - 1]的区间异或值与[0,r]的区间异或值相同，则[l, r]的区间异或值为0。反之，如果不同，则为1

简单解释一下：因为[0,l-1]这个区间异或两次抵消了

在下面的题目中，往往是求出现偶数次，是因为，相同的话很好找。

不过有时候会问你，至多出现一次奇数的情况，我们只需要枚举每一位，分别讨论翻转它的情况。

一般前缀异或考的就这些，不过变形比较多，注意题目对奇偶性，以及给出的字符串仅有小写字母、数字组成的要求

常见题型

板子

纯板子，有需要可以写一下

1310. 子数组异或查询 - 力扣（LeetCode）

最长长度

给定一个数组，求包含偶数次x(x是某几个数)的子数组最长长度

解题过程基本一样，给出伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
map<int,int>mp;  //记录各个前缀异或出现的位置
mp[0] = -1; //!!比较重要，因为我们遍历是从0开始，让遇到0正确计算
int cur; //当前前缀异或
int maxm; //最长长度
for i : 给定字符串
    cur ^= s[i] //获得当前前缀异或
    if(mp.count(cur))//如果出现过，比较最长
        maxm = max(ans, i - mp[cur]); 
	else 			//反之，记录出现位置
        mp[cur] = i;
	//如果有翻转操作
	for j : 翻转要求
        tmp = cur ^ j //翻转的情况
        if(mp.count(tmp))  //和上面一样
            maxm = max(ans, i - mp[tmp]);
        else
            mp[tmp] = i;
        
return maxm

给出两道例题

1371. 每个元音包含偶数次的最长子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ans = 0, cur = 0, n = s.length();
        map<int,int>mp;
        mp[0] = -1;
        for(int i = 0; i < n; i++){
            //获取当前位
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'o' || s[i] == 'i' || s[i] == 'u'){
                cur ^= 1<<(s[i] - 'a');
            }
            if(mp.count(cur)){ //如果出现过，比较最长
                ans = max(ans, i - mp[cur]);
            }else{			  //反之，记录前缀和出现位置
                mp[cur] = i;
            }
            //这题没有翻转等操作，所以没有翻转部分
        }
        return ans;
    }
};

进阶一点的

1542. 找出最长的超赞子字符串 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestAwesome(string s) {
        int ans = 0, cur = 0, n = s.length();
        map<int,int>mp;
        mp[0] = -1;
        for(int i = 0; i < n; i++){
            cur ^= 1<<(s[i] - '0');	//获取当前位
            if(mp.count(cur)){	//如果出现过，比较最长
                ans = max(ans, i - mp[cur]); 
            }else{				//反之，记录前缀和出现位置
                mp[cur] = i; 
            }
            for(int j = 0; j < 10; j++){ //枚举哪一位不一样的情况（也就是翻转部分）
                int base = 1<<j;
                if(!mp.count(cur ^ base)) continue;
                ans = max(ans, i - mp[cur ^ base]);
            }
        }
        return ans;
    }
};

稍微有点变形的，求次数

1915. 最美子字符串的数目 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    using ll = long long;
    long long wonderfulSubstrings(string s) {
        ll ans = 0, cur = 0, n = s.length();
        map<ll, int>mp; //记录前缀和出现的次数
        mp[0] = 1;  //同样初始化
        for(int i = 0; i < n; i++){
            cur ^= 1<<(s[i] - 'a'); //获取当前位
            //下面我稍微简写了一下，因为次数0的话不影响答案，直接加就可以了。但是上面的题目，如果是起始0就会影响答案
            ans += mp[cur];
            mp[cur]++;
            for(int j = 0; j < 10; j++){ //枚举哪一位不一样的情况（也就是翻转部分）
                int tmp = cur ^ (1<<j); //某一位不同的情况
                ans += mp[tmp];
            }
        }
        return ans;
    }
};

变式

本质基本一样，只不过魔改一下

1177. 构建回文串检测 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int>f(n+1);
        for(int i = 0; i < n; i++){
            int cur = 1<<(s[i] - 'a');
            f[i+1] = cur ^ f[i];
        }
        vector<bool>ans(queries.size());
        for(int i = 0; i < queries.size(); i++){
            int l = queries[i][0], r = queries[i][1] + 1, k = queries[i][2];
            int dif = __builtin_popcount(f[r] ^ f[l]);
            ans[i] = (dif/2 <= k);
        }
        return ans;
    }
};

下面这题其实是考了前缀异或和后缀异或两种。

Problem - D - Codeforces

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int t,n,a[100005];
int f[100005][31],g[100005][31],s[100005];
int main(){
	cin>>t;
	while (t--){
		cin>>n;
		for (int i=1;i<=n;++i){
			cin>>a[i];
			s[i]=s[i-1]^a[i];
		}
		for (int j=0;j<=30;++j) g[0][j]=1;
		for (int i=1;i<=n;++i){
			for (int j=0;j<=30;++j){
				f[i][j]=f[i-1][j];
				g[i][j]=g[i-1][j];
				if ((s[i]>>j)&1) f[i][j]++;
				else g[i][j]++;
			}
		}
		long long ans=0;
		for (int i=1;i<=n;++i){
			int cnt=-1;
			while (a[i]){
				++cnt;
				a[i]>>=1;
			}
            //根据我们一开始说的性质，a[0,l-1]和a[0,r]相同就可以让a[l,r]的异或值为0，即这一位置0
            //因为现在这一位是有数字的，我们要让总体增大，所以是求这一位异或成0的情况
            //如果a[0, l-1]和a[0,r]都是1
			ans+=1ll*f[i-1][cnt]*(f[n][cnt]-f[i-1][cnt]);
            //如果a[0, l-1]和a[0,r]都是0
			ans+=1ll*g[i-1][cnt]*(g[n][cnt]-g[i-1][cnt]);
		}
		cout<<ans<<endl;
	}
	return 0;
}
  • Copyrights © 2023-2024 Kano
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信