阿里蚂蚁金服20220915笔试最后一题

一道比较有意思的题目,值得记录下来~

应该称得上ICPC铜牌题?还是只是因为我变菜了…

题意

给定一个只包含小写字母的字符串,同时给出好串的定义:只有一个小写字母出现的次数为奇数个,其他小写字母出现的次数都为偶数个(其中包括0)
需要你计算给定字符串的所有子串中有多少好串?

其中字符串长度最大为:200000

示例

输入

ababa

输出

9

题解

经典前缀和+哈希的做法,但是引入了状态压缩+异或运算(同时异或运算进行了问题转换)

首先我们将所有前缀和状态压缩为26位二进制数(其中1表示对应的小写字母出现的次数为奇数个,0表示对应的小写字母出现的次数为偶数个)

然后可以发现,对所有 <font color=##ff0000>前缀两两异或则可以得到所有的子串 </font>
例如:aba^ababa可以转化为:000…10^000…01=000…11(即ba,至于顺序不用在意,只需要在意它每个小写字母出现的次数即可)
同时:前缀同样是一个特殊的子串

使用哈希表存储所有子串对应是否为好串的情况。

于是现在难点在于如何将前缀两两异或运算获得所有子串(同时判断是否为好串)的过程用线性时间复杂度实现。

转换下思路:好串的定义可以转化为状态压缩后26位二进制数中只有一位对应位置是1,其中位置都为0。
于是我们可以在遍历所有前缀的同时,在二重循环遍历所有的小写字母(即此时得到的好串就是对应小写字母为奇数个,其他小写字母为偶数个的情况)

至于为啥,在此解释:
我们其实是要计算当前前缀(用a表示)和跟其他前缀和(用b表示)异或得到的结果(也就是子串,用c表示)是否为好串(也就是26位二进制中只有一位是1的情况)
即:a^b=c,但是这样的话时间复杂度就变成了$O(n^2)$,于是我们将该异或运算调整为:a^c=b。(c因为只有一位是1,也就可以直接遍历每一个小写字母即可),这样时间复杂度就变成了$O(26n)$(即线性复杂度)

具体见代码:

#include<bits/stdc++.h>
const int maxn=2e5+5;
using namespace std;
map<int,int> mp;  //记录所有前缀是否为好串的情况
int main(){
    string s;cin>>s;
    int len=s.length();
    int pre=0;  //表示前缀(26位二进制)
    int ans=0;  //最终结果
    mp[0]=1;        //初始化,由于是对前缀两两异或获得所有子串,那肯定得初始化空串的情况
    for(int i=0;i<len;i++){
        //记录当前位置i结尾的前缀
        int pre = pre ^ (1<<(s[i]-'a'));
        //然后再前缀两两异或运算 做下转换(a^b=c ==> a^c=b)
        for(int j=0;j<26;j++){
            int num = pre ^ (1<<j);   //其实就是其他前缀
            if(!mp.count(num)){
                mp[num]=0;
            }else{
                ans+=mp[num];
            }
        }
        mp[pre]++;
    }
    cout<<ans<<endl;
    return 0;
}