A.串串串
【题目描述】
你有两个长度分别为 \(n, m\) 的 \(01\) 串 \(\text{S, T}\)。
有 \(\text Q\) 次询问，每次询问给出 \(l_1, r_1, l_2, r_2\)，其中 \(r_1 − l_1 + 1 = r_2 − l_2 + 1\)。
令 \(a = \text S[l_1 … r_1], b = \text T[l_2 … r_2]\)。
你需要求出 \(a_i ≠ b_i\) 的位置个数对 \(2\) 取模的结果
【解决方法】
一、暴力
暴力枚举 \(i\)，计算 \(a_i\not= b_i\) 的个数之和对 \(2\) 取模的结果。
时间复杂度：\(\text O(q\cdot\max(n,m))\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int n, m, q, cnt;
char s1[maxn], s2[maxn];
int main()
{
scanf("%d%d%s%s",&n,&m,s1+1,s2+1);
scanf("%d",&q);
for (int i = 1, l1,l2,r1,r2; i <= q; ++ i)
{
cnt = 0;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
for (int i = l1, j = l2; j <= r2; ++ j, ++ i)
{
if (s1[i] != s2[i]) cnt ++;
}
printf("%d\n",cnt%2);
}
return 0;
}
二、性质
我们发现对于 \(\begin{matrix}1&\dots&0\ \ (\text S)\\0&\dots&0\ \ (\text T)\end{matrix}\)，如果交换 \(\text S\) 的 \(1\) 与 \(0\) 的位置，不同的数对还是 \(1\)。类似地，
-
若相同的两对，且上下两个数均相同的交换后无影响；
-
若是不同的两对，且上下两个数均相同的交换后，贡献由 \(0\) 变成了 \(2\)，模 \(2\) 后还是无影响；
-
若相同的两对，且上下两个数不相同的交换后无影响；
-
若是不同的两对，且上下两个数均相同的交换后，贡贡献由 \(2\) 变成了 \(0\)，模 \(2\) 后还是无影响；
因此，若将这范围的 \(1\) 放到前面的话，那么不同的数的个数就是 \(a\) 中 \(1\) 的个数和 \(b\) 中 \(1\)的个数之差。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int n, m, q, b1[maxn], b2[maxn];
char s1[maxn], s2[maxn];
int main()
{
scanf("%d%d%s%s",&n,&m,s1+1,s2+1);
for (int i = 1; i <= n; ++ i)
{
b1[i] = b1[i-1] + (s1[i]=='1');
}
for (int i = 1; i <= m; ++ i)
{
b2[i] = b2[i-1] + (s2[i]=='1');
}
scanf("%d",&q);
for (int i = 1, l1,l2,r1,r2; i <= q; ++ i)
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
printf("%d\n",(abs(b1[r1]-b1[l1-1]-b2[r2]+b2[l2-1]))%2);
}
return 0;
}
三、异或
当然，由于是 \(01\) 串，并且昨天刚刚看了看 \(\text{bitset}\)，然后就通过它的左移右移操作取出 \(\text S[l_1\dots r_1]\) 和 \(\text T[l_2\dots r_2]\) 的范围的数，然后异或，得到不同的数的个数，返回 \(1\) 的个数模 \(2\) 即可。
结果，炸的和暴力一个分。
如果，再想想的话，异或后 \(1\) 的个数也就可以把最后的 \(\text{bitset}\) 里面的数得到一个异或和。
那，还用个锤子的 \(\text{bitset}\) 啊，异或前缀和解决。
#include <bits/stdc++.h>
using namespace std;
int n, m, q, Xor[2][2000100];
char s[2][2000100];
int main()
{
scanf("%d%d%s%s",&n,&m,s[0]+1,s[1]+1);
for (int i = 1; i <= n; ++ i) Xor[0][i] = Xor[0][i-1]^(s[0][i]-'0');
for (int i = 1; i <= m; ++ i) Xor[1][i] = Xor[1][i-1]^(s[1][i]-'0');
scanf("%d",&q);
for (int i = 1, l1, r1, l2, r2; i <= q; ++ i)
{
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
printf("%d\n",Xor[0][r1]^Xor[0][l1-1]^Xor[1][r2]^Xor[1][l2-1]);
}
return 0;
}
对于 \(100\%\) 的数据，\(1 ≤ n, m, q ≤ 2 × 10^5，1 ≤ l_1 ≤ r_1 ≤ n，1 ≤ l_2 ≤ r_2 ≤ m\)。
B.方格计数
【题目描述】
在左下角是 \((0, 0)\)，右上角是 \((W,H)\) 的网格上，有 \((W + 1) × (H + 1)\) 个格点。
现在要在格点上找 \(N\) 个不同的点，使得这些点在一条直线上。
并且在这条直线上，相邻点之间的距离不小于 \(D\)。求方案数模 \(10^9 + 7\)。
【解决方法】
【算法一】
考虑枚举两个端点，强制两个端点选，令 \(a\) 为两个端点之间 \(x\) 轴上的距离，\(b\) 为两个端点 \(y\) 轴上的距离，那么这里面可以选择的点的个数有 \(g = \gcd(a, b)\) 个。我们要求 \(N − 2\) 个小球（强制两个端点选），需要放到 \(g\) 个盒子里，相邻两个小球的盒子编号差至少为 \(k\)，方案数为 \(C^{N − 2}_{g + 1 − 2k − (N − 3)(k − 1))}\)。时间复杂度 \(\text O(TW^2H^2)\)，
【算法二】
延续算法一的思路，发现对于相同的 \(a, b\) 方案数也是相同的，考虑枚举 \(a, b\)，跟算法一一样做，最后再乘个 (W − a + 1) × (H − b + 1) 就好了，时间复杂度 \(\text O(TWH)\)。
对于 \(100\%\) 的数据，\(1 ≤ N ≤ 50，1 ≤ W,H,D ≤ 500，1 ≤ T ≤ 20\)。
C.树数树
【题目描述】
牛牛有一棵 \(n\) 个点的有根树，根为 \(1\)。
我们称一个长度为 \(m\) 的序列 \(a\) 是好的，当且仅当：