做题笔记 2022.12.24
Merry Xmas.
CF1615F LEGOndary Grandmaster
题目给出的操作是可以将两个相邻两个相同的位反转，这样的操作不好实现，我们考虑将原序列的所有偶数位反转，操作就变为了交换两个相邻的数，注意到交换相同的数是无效的，这样就处理了在转化前对两个不等的数进行操作这样的不合法行为。
现在，对于所有合法的起始状态-终止状态，我们要求出从起始状态变换为终止状态的操作次数之和。
首先考虑对于固定的起始状态 $S$ 和终止状态 $T$，如何计算操作次数。
很显然，我们将 $S$ 和 $T$ 中的 1 从前往后按顺序匹配，总操作次数就是每一对 1 的距离之和。
为了计算答案，考虑 dp，设 $f_{i,j}$ 表示最后一对 1 是 $S_i$ 和 $T_j$ 的方案数，$g_{i,j}$ 表示最后一对 1 是 $S_i$ 和 $T_j$ 的操作次数之和，$g_{i,j}$ 转移时只需要加上 $|i-j|\times f_{i,j}$ 即可。
考虑如何转移，注意到如果 $f_{i,j}$ 从 $f_{a,b}$ 转移，则意味着 $S_{a+1\dots i-1}$ 和 $T_{b+1\dots j-1}$ 全部为 0，所以这些位中不能有已经确定为 1 的位，设 $la_i,lb_j$ 分别表示 $S,T$ 中上一个 1 的位置，有转移：
$$
f_{i,j}=\sum_{a=la_i+1}^{i-1}\sum_{b=lb_j+1}^{j-1}f_{a,b}
$$
这是一个子矩形和，二维前缀和优化即可。
细节有点多。
注意代码的实现中对 0 和 1 的处理与题解是相反的，或者说，代码是在对 0 进行匹配，而题解很显然是对 1 进行匹配。
Code
namespace Main{
const int N = 2005;
const int MOD = 1e9 + 7;
int t, n, a[N], b[N], la[N], lb[N];
ll f[N][N], g[N][N];
bool p1[N], p2[N];
string s1, s2;
void Main(){
input(t);
while(t--){
input(n);
cin >> s1 >> s2;
for(int i = 1; i <= n; i++){
a[i] = s1[i-1] == '?' ? -1 : s1[i-1] - '0';
b[i] = s2[i-1] == '?' ? -1 : s2[i-1] - '0';
if((i & 1) && a[i] != -1) a[i] = 1 - a[i];
if((i & 1) && b[i] != -1) b[i] = 1 - b[i];
}
la[0] = lb[0] = 1;
for(int i = 1; i <= n; i++){
if(a[i] == 0) la[i] = i, p1[i] = true;
else la[i] = la[i-1], p1[i] = p1[i-1];
if(b[i] == 0) lb[i] = i, p2[i] = true;
else lb[i] = lb[i-1], p2[i] = p2[i-1];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(a[i] == 1 || b[j] == 1) f[i][j] = g[i][j] = 0;
else{
f[i][j] = ((!p1[i-1] && !p2[j-1]) + f[i-1][j-1] - f[la[i-1]-1][j-1] - f[i-1][lb[j-1]-1] + f[la[i-1]-1][lb[j-1]-1] + MOD + MOD) % MOD;
g[i][j] = f[i][j] * abs(i - j) % MOD;
g[i][j] = (g[i][j] + g[i-1][j-1] - g[la[i-1]-1][j-1] - g[i-1][lb[j-1]-1] + g[la[i-1]-1][lb[j-1]-1] + MOD + MOD) % MOD;
}
f[i][j] = (f[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1] + MOD) % MOD;
g[i][j] = (g[i][j] + g[i-1][j] + g[i][j-1] - g[i-1][j-1] + MOD) % MOD;
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= n; j++) cerr << g[i][j] - g[i-1][j] - g[i][j-1] + g[i-1][j-1] << ' ';
// cerr << endl;
// }
// cerr << la[n] << ' ' << lb[n] << endl;
write((g[n][n] - g[la[n]-1][n] - g[n][lb[n]-1] + g[la[n]-1][lb[n]-1] + MOD + MOD) % MOD);
puts("");
}
return;
}
} // namespaceCF1659E AND-MEX Walk
给定一张无向连通图，对于一条路径，考虑其边权序列 $w_{1\dots k}$，定义该路径的长度为 $\operatorname{mex}\{w_1,w_1\operatorname{and}w_2,w_1\operatorname{and}w_2\operatorname{and}w_3,\dots,\operatorname{and}_{i=1}^k w_i\}$，每次询问给出 $u,v$，求 $u\rightsquigarrow v$ 路径的最短长度。
容易发现，答案不会超过 2，因为不断进行与运算相当于是每次 reset 了若干个二进制位，那么不可能同时出现 01 和 10，即 1 和 2。
如果答案为 0，那么我们经过的所有边应该至少有一个二进制位全部为 1，于是我们枚举每个二进制位，将所有该位为 1 的边拉出来用并查集合并，如果 $u$ 和 $v$ 连通则答案为 $0$，注意并查集的构造在预处理时即可完成。
如果答案为 1，相当于最低位被 reset 时，还有其他的二进制位为 1，换言之，我们在经过第一条最低位为 0 之前经过的所有边，应当至少有一个二进制位全部为 1（包括现在经过的这条边），在实现时，我们构造一个新点，编号为 0，所有边权最低位为 0 的边的两个端点与 0 合并，然后类似的，枚举每个二进制位，将所有该位为 1 的边拉出来合并，查询时如果 $u$ 和 0 连通则答案为 1。
否则，答案为 2。
Code
namespace Main{
const int N = 100005;
const int L = 30;
int n, m, q;
struct dsu{
int fa[N];
void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i; }
int get(int x){
if(fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void unite(int x, int y){
fa[get(x)] = get(y);
}
}d[L], z[L];
void Main(){
input(n, m);
for(int i = 0; i < 30; i++) d[i].init(n), z[i].init(n);
for(int i = 0, u, v, w; i < m; i++){
input(u, v, w);
for(int j = 0; j < 30; j++){
if(w >> j & 1) d[j].unite(u, v), z[j].unite(u, v);
}
if(~w & 1) for(int j = 1; j < 30; j++) z[j].unite(u, 0), z[j].unite(v, 0);
}
input(q);
while(q--){
int u, v; bool flag = false, f2 = false;
input(u, v);
for(int j = 29; j > 0; j--){
if(d[j].get(u) == d[j].get(v)){
flag = true;
}
if(z[j].get(u) == z[j].get(0)){
f2 = true;
}
}
if(flag || d[0].get(u) == d[0].get(v)) puts("0");
else if(f2) puts("1");
else puts("2");
}
return;
}
} // namespaceCF1734E Rectangular Congruence
说实话这个题我做起来挺吃力的，我甚至一度认为 $n$ 是质数的条件就是误导人。
题目给出的限制是 $a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod n$，单个限制太弱，无法确定任何信息，让人觉得无从下手。
这个式子长得有点像四边形不等式，这样的形式其实很不利于我们观察，考虑将其变形为 $a_{r_1,c_1}-a_{r_1,c_2}\not\equiv a_{r_2,c_1}-a_{r_2,c_2}\pmod n$，这样，不等式一侧的两个数全部来自同一行。
首先，限制条件全部形如同一行中的两数之差意味着如果我们将一行中的数全部加上或减去同一个数，并不会影响整个矩阵的合法性，那么题目中对对角线的限制就解决了，构造的最后再将对角线平移为正确的值即可。
考虑一列一列的构造，首先很自然地想到按照如下的方式摆放前两列：
0 0
0 1
0 2
0 3
0 4那么，第三列怎么办呢，可以考虑干脆将每一行相邻两个数的差固定下来，整个矩阵填充如下：
0 0 0 0 0
0 1 2 3 4
0 2 4 1 3
0 3 1 4 2
0 4 3 2 1形式化的，第 $i$ 行第 $j$ 列填充的数为 $ij\bmod n$，$i,j\in [0,n)$。
接下来考虑正确性，$a_{r_1,c_1}-a_{r_1,c_2}$ 和 $a_{r_2,c_1}-a_{r_2,c_2}$ 可以记作 $kr_1$ 和 $kr_2$，假如 $kr_1\equiv kr_2\pmod n$，也就意味着 $n\mid k(r_1-r_2)$，由于 $n$ 是质数，所以 $k$ 或 $r_1-r_2$ 是 $n$ 的倍数，而显然两者都不可能成立，于是正确性就得到了证明。
Code
namespace Main{
const int N = 355;
int n, a[N];
void Main(){
input(n);
for(int i = 0; i < n; i++) input(a[i]);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) write(((a[i] - i * i + i * j) % n + n) % n), putchar(' ');
puts("");
}
return;
}
} // namespace
Xmas Tree feat. wgx
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
