本文主要是介绍牛客周赛 Round 32 E.小红的回文数【挖掘性质+哈希前缀和】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：https://ac.nowcoder.com/acm/contest/75174/E
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小红定义一个整数是“好数”，当且仅当该整数通过重排之后可以形成回文数。（可以包含前导零）
现在小红拿到了一个正整数x，小红想截取一段连续区间得到好数，她想知道有多少种不同的方案？
输入描述:
输入一个正整数x。 1≤x≤10^(10^5)
输出描述:
得到“好数”的方案数。
示例1
输入
110
输出
5
说明
长度为 1 的区间，三个都是合法的。 长度为 2 的区间，"11"是合法的，"10"是不合法的。 长度为 3 的区间， "110"是合法的。
解题思路：
当截取的区间长度为偶数时，每种字符都只能出现偶数次，
当截取的区间长度为奇数时，有且仅有一种字符出现奇数次。
综上所述最多只能有一种字符出现奇数次。
(1)所有字符出现偶数次
(2)0,1,2,3,4,5,6,7,8,9中的某一种字符出现奇数次。
由于要求的是满足要求的子区间个数，我们可以使用前缀和进行维护，到这里我们还需要知道一个性质。
性质如下：
- 奇数-奇数=偶数
- 偶数-偶数=偶数
- 奇数-偶数=奇数
- 偶数-奇数=奇数
我们不妨用一个二进制数temp表示当前某种数出现次数的奇偶性，例如temp二进制数的第i位1表示数字i出现奇数次，否则表示数字i出现偶数次，比如说temp的第0位为1表示0出现的次数为奇数，否则表示0出现的次数为偶数。
当前位置前缀和temp,如果要使得子区间所有数字都出现偶数次，那么前面位置前缀和表示应该和temp一样，俩个前缀和相减才能保证每种数字出现偶数次。
当前位置前缀和temp,如果要使得某一种数字出现奇数次，其他数字都出现偶数次，例如数字i出现奇数次，那么前面位置前缀和应该为temp^(1<<i)，其他位置奇偶性相同，相减就是偶数次，第i个位置奇偶性不同，那么相减为奇数，俩个前缀和相减才能保证只有某一种数字出现奇数次，其他数字都出现偶数次。
时间复杂度：O(n*10)，枚举字符串s时间为O(n)，枚举某一种出现次数为奇数的字符，总共有10种，所以时间为O(10)，所以最终时间为O(10*n)，时间复杂度为O(n)，常数为10。
空间复杂度：O(n)，使用一个哈希表，存储所有前缀和的哈希值。
cpp代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_map>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5 + 10;
int n, m;
unordered_map<int,int>mp;
int main()
{string s;cin>>s;n=s.size();int temp=0;mp[temp]++; //所有数字出现0次，加入哈希表LL sum=0; //sum记录答案for(int i=0;i<n;i++){temp^=(1<<(s[i]-'0')); //异或上当前位置，表示当前位置结尾的前缀和sum+=mp[temp]; //所有数字俩个前缀和奇偶性相同，也就是所有字符出现偶数次的区间for(int j=0;j<10;j++){sum+=mp[temp^(1<<j)]; //某个数字出现奇数次，其他数字出现偶数次的区间。}mp[temp]++; //当前位置结尾的前缀和加入哈希表}cout<<sum;return 0;
}这篇关于牛客周赛 Round 32 E.小红的回文数【挖掘性质+哈希前缀和】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
