AtCoder ABC295 D - Three Days Ago
题目描述
给出一个数字串，问有多少子段满足，可以以某种方式将这个子段重排，将子段分成两个完全相同的部分。
样例输入输出
20230322
4
\((1, 6) (1, 8) (2, 7) (7, 8)\) 都可以满足条件
分析
如果要满足某一个字段可以被分为两个相同的部分，则不难发现必须要让这个字段中的所有字符的数量都是偶数。
暴力 \(\Theta(n^3)\)
暴力不做说明。
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
memset(tmp, 0, sizeof tmp);
flag = false;
for(int k=i; k<=j; k++){
tmp[a[k]]++;
}
for(int k=0; k<10; k++){
if(tmp[k] % 2){
flag = true;
break;
}
}
if(!flag) res++;
}
}
前缀和 \(\Theta(n^2)\)
我们可以统计一个前缀和数组 \(s_{i, j}\)，表示前 \(i\) 个元素中 \(j\) 元素出现了多少次。那么，枚举所有的 \(l\) 和 \(r\)，只需要判断是否对于所有的 \(j \in [0, 9]\)，都满足 \(s_{r, j} - s_{l-1, j}\) 为偶数即可。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
char str[N];
int n, res, a[N];
int s[N][20]; // s[i][j] 表示前 i 个数中 j 出现的次数
void input(){
cin >> str + 1;
n = strlen(str + 1);
for(int i=1; i<=n; i++){
a[i] = str[i] - '0';
}
}
// 判断是否 [l, r] 中每个数字都出现了偶数次
bool check(int l, int r){
for(int i=0; i<10; i++){
if((s[r][i] - s[l-1][i]) % 2){
return false;
}
}
return true;
}
signed main(){
input();
// 处理前缀和
for(int i=1; i<=n; i++){
s[i][a[i]]++;
for(int j=0; j<10; j++){
s[i][j] += s[i-1][j];
}
}
for(int i=1; i<=n; i++){
for(int j=0; j<10; j++){
cout << s[i][j] << ' ';
}
cout << '\n';
}
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
if(check(i, j)){
res++;
}
}
}
cout << res;
return 0;
}
状态压缩 \(\Theta(n)\)
状态压缩
延续前缀和的思路，如果把上述代码中的 \(tmp_i\) 数组进行状态压缩，那么可以再省掉判断的时间。在这里我们规定 \(f_i\) 为前 \(i\) 个元素压缩后的状态。
那么如何把 \(10\) 个状态压缩呢？不难想到使用二进制数表示。如果二进制表示下 \(f_i\) 的第 \(j\) 位上的数是 \(1\)，则代表前 \(i\) 个数中存在奇数个 \(j\)。反之，如果二进制表示下 \(f_i\) 的第 \(j\) 位上的数是 \(0\)，则代表前 \(i\) 个数中存在偶数个 \(j\)。
那么，我们这样就可以把所有的状态进行压缩。代码如下：
for(int i=1; i<=n; i++){
// 如果原来这一位是 1
if(f[i-1] >> a[i] & 1){
// 变为 0
f[i] = f[i-1] - (1 << a[i]);
}
else{ // 否则变为 1
f[i] = f[i-1] + (1 << a[i]);
}
}
统计完所有的状态后，就需要根据所有的状态进行计算了。
求解答案
同余：如果 \(a\)，\(b\) 和 \(p\) 皆为正整数 ，且 \(a \equiv b \pmod p\)，那么有 \(p \mid a-b\)。
把多个元素的状态压缩后，如果存在 \(f_i = f_j\)，就说明前 \(i\) 个元素出现每个数的次数与前 \(j\) 个元素出现每个数的次数的奇偶性是相同的。
如果 \(f_i = f_j = (0000000010)_2\)，就说明前 \(i\) 项和前 \(j\) 项都出现了奇数个 \(1\)。换言之，前 \(i\) 项和前 \(j\) 项出现 \(1\) 的次数对 \(2\) 取余都是 \(1\)，那么根据同余的性质，不难推出前 \(i\) 项和前 \(j\) 项出现 \(1\) 的次数之差能被 \(2\) 整除，也就是 \(i+1\) 到 \(j\) 中出现了偶数个 \(1\)。
至此，我们可以推出，如果存在两个压缩后的状态相同，就会多一个满足条件的区间。如果有 \(x\) 个相同的状态，那么其中任意两个都可以组成一个合法区间，那么如果规定某一种状态出现了 \(x\) 次，那么由这种状态构成的合法区间的个数就有 \(C_{x}^{2}\) 个，即 \(\dfrac{x \cdot (x-1)}{2}\)。
for(int i=1; i<=n; i++){
// 如果原来这一位是 1
if(f[i-1] >> a[i] & 1){
// 变为 0
f[i] = f[i-1] - (1 << a[i]);
}
else{ // 否则变为 1
f[i] = f[i-1] + (1 << a[i]);
}
// 表示 f[i] 这种状态有多存在了一次
um[f[i]]++;
}
// 枚举每一种状态
for(auto e: um){
// 求组合数 C(num, 2)
int num = e.second;
res += num * (num - 1) / 2;
}
完整代码
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 5e5 + 10;
int n, res, a[N];
char str[N];
int f[N]; // f[i] 表示前 i 个元素的压缩状态
unordered_map<int, int> um;
void input(){
cin >> str + 1;
n = strlen(str + 1);
for(int i=1; i<=n; i++){
a[i] = str[i] - '0';
}
}
signed main(){
input();
// 前 0 个元素状态为 0
f[0] = 0;
um[f[0]]++;
for(int i=1; i<=n; i++){
// 如果原来这一位是 1
if(f[i-1] >> a[i] & 1){
// 变为 0
f[i] = f[i-1] - (1 << a[i]);
}
else{ // 否则变为 1
f[i] = f[i-1] + (1 << a[i]);
}
// 表示 f[i] 这种状态有多存在了一次
um[f[i]]++;
}
// 枚举每一种状态
for(auto e: um){
// 求组合数 C(num, 2)
int num = e.second;
res += num * (num - 1) / 2;
}
cout << res;
return 0;
}