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

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

  • f(00110,01100)=2
  • f(00110,11000)=4
  • f(00110,10001)=4
  • f(00110,00010)=1

问你 取出 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 = ;
int main() {
string a, b;
cin >> a >> b;
int ans = , coun = ;
int lena = a.size(); int lenb = b.size();
rep(i, , lenb - ) ans = ans ^ ( a[i] - '') ^ (b[i] - '');
if(ans % == ) coun++;
rep(i, lenb, lena - ) {
ans = ans ^ (a[i - lenb] - '') ^ (a[i] - '');
if(ans % == ) coun++;
}
cout << coun << endl;
return ;
}
05-11 22:13