C Vus the Cossack and Strings （异或思维）

题意：给你两个只包含 0 和 1 的字符串 a, b，定义函数 f ( A, B ) 为字符串A和字符串B 比较

存在多少个位置 i 使得 A[ i ] != B[ i ] ，例如

$f (00110, 01100) = 2$

问你取出 a 中所有长度为 lenb （字符串b的长度）的子串 c，求 f ( c, b) 为偶数的 c 的个数。

解：显然， a 中存在 lena - lenb + 1 个 c，直接枚举显然是爆的，字符串只包含 0 1 且题目只问 f ( b, c ) 的奇偶性。

想到异或，若在位置 i 上 b[ i ] != c[ i ]，则 b[ i ] ^ c[ i ] = 1；否则 b[ i ] ^ c[ i ] = 0；

所以可以用一个 ans 来记录 f ( b, c) 的奇偶性，那么只要枚举 b字符串的长度，然后 ans = ans ^ b[ i ] ^ c[ i ] 就行了

最后判断一下 ans 的奇偶性看满不满足就行了。

这题的关键是 a 的长度为 lenb 的子串 c 有很多，你不可能对于每个 c 都去遍历一遍 b字符串。

首先，枚举a 的所有长度为 lenb 的子串 c 枚举 i , 字符串 c 就是 a[ i ] ~ a[ i + lenb - 1]；

首先，先取第一个 c ; a[ 0 ] ~ a[ lenb - 1] 与 b 进行比较求出 ans0；

然后对于第二个 c ： a[ 1 ] ~ a[ lenb ] 的 ans1 就会等于 ans0 ^ a[ 0 ] ^ a[ lenb ]；

同理对于第 i 个 c： a[ i ] ~ a[ i + lenb - 1 ] 的 ans( i ) = ans( i - 1 ) ^ a[ i - 1 ] ^ a[ i + lenb - 1]

为什么可以这样写呢；那就是因为异或的性质啦。异或 a [ i - 1 ] 是消除 a[ i - 1 ] 的影响

异或 a [ i + lenb - 1] 是加入计算；

举个例：现在令 a = 01100010 ; b = 00110；

第一个 c 的 ans 是

（ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）

第二个 c 的 ans

（ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）^ 0 ^ 0 // 第一个0 是a[ i - 1 ],第二个0是a[ i + lenb - 1 ]；

= 0 ^ （ 0 ^ 0 ）^（ 1 ^ 0 ）^（ 1 ^ 1 ）^（ 0 ^ 1 ）^（ 0 ^ 0 ）^ 0 // 异或两次相当于没有异或

= （ 0 ^ 1）^（ 0 ^ 1 ）^（ 1 ^ 0 ）^（ 1 ^ 0 ）^（ 0 ^ 0 ）

用到了异或运算的交换律和异或两次等于没异或的性质。挺巧妙的这个思维。

代码里的 i 和我说的 i 不一样，不过道理都是一样的啦；

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define ULL unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define dep(i,j,k) for(int i=k;i>=j;i--)
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define make(i,j) make_pair(i,j)
#define pb push_back
#define Pi acos(-1.0)
using namespace std;
const int N = 0;
int main() {
    string a, b;
    cin >> a >> b;
    int ans = 0, coun = 0;
    int lena = a.size(); int lenb = b.size();
    rep(i, 0, lenb - 1) ans = ans ^ ( a[i] - '0') ^ (b[i] - '0');
    if(ans % 2 == 0) coun++;
    rep(i, lenb, lena - 1) {
        ans = ans ^ (a[i - lenb] - '0') ^ (a[i] - '0');
        if(ans % 2 == 0) coun++;
    }
    cout << coun << endl;
    return 0;
}

View Code

一步一步，永不停息

C Vus the Cossack and Strings （ 异或 思维）

C Vus the Cossack and Strings （异或思维）