CF 1368 G
题目链接
题目叙述
给出一个(n imes m)的棋盘，布满了 (1 imes2) 的多米诺骨牌，告诉你多米诺骨牌的排列情况。每次去掉一个股派，然后可以将其他骨牌挪动。每个骨牌都会被去掉一次。挪动后必须与最开始的位置至少公用一个位置。并且骨牌挪动方向必须平行于骨牌原本的方向（即不能“拐弯”）。问挪动若干次后剩下的两个空格的方案数。
题解
问题转化
考虑将骨牌移动想象成空格移动。对于一个空位置 ((r,c)) （第 (r) 行第 (c) 列），如果 ((r,c)) 下面 ((r+1,c),(r+2,c)) 是一个多米诺骨牌，那么 ((r,c)) 这个空格可以移动到 ((r+2,c)) 。这样连出若干条边，构成一个图。容易知道每个点的入读均为 1.
下面证明这是一个树。只要证明不存在一个环即可。如果存在一个环，那么一定形如这样：
考虑下面这样的形状：
可以将这样的东西向外翻，一次将会添加 4 个格子，这样不断操作一定能操作成一个长方形。然后可以发现中间空出来一个长宽均为奇数的长方形，很明显这样多米诺骨牌并不能将这个长方形填满。
解决
所以像上面那样连边将会连出一个森林。只要一对格子可以被两个组成一个多米诺骨牌的格子移动到，那么就算 1 的贡献。即对于两个结点，存在两个祖先满足他们组成多米诺骨牌的两个格子，那么就算 1 的贡献。
这个问题可以转化为一个矩阵面积并的问题。考虑将每一对点 ((x,y)) ，将其对应到平面上的点 ((dfn_x,dfn_y)) （(dfn_i) 为 (i) 结点的 (dfs) 序）。现在枚举每一块骨牌，如果是由编号为 (x) 和 (y) 的树上的结点所对应的方格组成，那么就将 (x) 的子树所对应的区间作为 (x) 轴的范围， (y) 的子树对应的区间最为 (y) 轴的范围，给这样组成的矩形中的所有点覆盖。通过一共覆盖的点数量即可算出答案。覆盖点数只需要使用扫描线求解即可。
实现
会发现树上结点 (x) 和 (y) 组成的矩形与 (y) 和 (x) 组成的矩形不一样。仔细思考可以发现都覆盖上，再将答案/2即可。
#include <cstdio>
#include <algorithm>
using namespace std;
const int NTOT = 2e5 + 5;
int N, M, deg[NTOT], root[NTOT], totr;
int in[NTOT], out[NTOT], dfstime;
char str[NTOT];
inline int dw(int r, int c) { return (r-1)*M+c; }
int head[NTOT];
struct E {
int v, nxt;
E(int _v, int _n) : v(_v), nxt(_n) {}
E() {}
} edge[NTOT*2];
int totE;
void AddEdge(int u, int v) {
edge[++totE] = E(v, head[u]);
head[u] = totE;
}
void Dfs(int u) {
in[u] = ++dfstime;
for (int p = head[u]; p; p = edge[p].nxt) {
int v = edge[p].v;
Dfs(v);
}
out[u] = dfstime;
}
int tsqr;
struct Square {
int u, d, l, r;
Square(int _u, int _d, int _l, int _r) : u(_u), d(_d), l(_l), r(_r) {}
Square() {}
} sqr[NTOT];
int tqz;
struct smx {
int u, d, ps, ad;
smx(int _u, int _d, int _p, int _a) : u(_u), d(_d), ps(_p), ad(_a) {}
smx() {}
} qz[NTOT*2];
bool cmp(smx &a, smx &b) { return a.ps < b.ps; }
int tag[NTOT*4], cnt[NTOT*4];
int Len(int L, int R) { return R - L + 1; }
int Cal(int p, int L, int R) {
if (!tag[p]) return cnt[p];
else return Len(L, R);
}
void AddSeg(int p, int L, int R, int ql, int qr, int a) {
if (qr < L || R < ql)
return ;
if (ql <= L && R <= qr) {
tag[p] += a;
return ;
}
int m = (L + R) >> 1;
AddSeg(p<<1, L, m, ql, qr, a);
AddSeg(p<<1|1, m+1, R, ql, qr, a);
cnt[p] = Cal(p<<1, L, m) + Cal(p<<1|1, m+1, R);
}
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i)
scanf("%s", str + (i-1) * M + 1);
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j) {
if (i-2 >= 1 && str[dw(i-2, j)] == 'U') {
AddEdge(dw(i, j), dw(i-2, j));
++deg[dw(i-2, j)];
}
if (j-2 >= 1 && str[dw(i, j-2)] == 'L') {
AddEdge(dw(i, j), dw(i, j-2));
++deg[dw(i, j-2)];
}
if (i+2 <= N && str[dw(i+2, j)] == 'D') {
AddEdge(dw(i, j), dw(i+2, j));
++deg[dw(i+2, j)];
}
if (j+2 <= M && str[dw(i, j+2)] == 'R') {
AddEdge(dw(i, j), dw(i, j+2));
++deg[dw(i, j+2)];
}
}
for (int i = 1; i <= N*M; ++i)
if (!deg[i])
root[++totr] = i;
for (int i = 1; i <= totr; ++i)
Dfs(root[i]);
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j) {
if (str[dw(i, j)] == 'U' && str[dw(i+1, j)] == 'D') {
sqr[++tsqr] = Square(in[dw(i, j)], out[dw(i, j)], in[dw(i+1, j)], out[dw(i+1, j)]);
sqr[++tsqr] = Square(in[dw(i+1, j)], out[dw(i+1, j)], in[dw(i, j)], out[dw(i, j)]);
} else if (str[dw(i, j)] == 'L' && str[dw(i, j+1)] == 'R') {
sqr[++tsqr] = Square(in[dw(i, j)], out[dw(i, j)], in[dw(i, j+1)], out[dw(i, j+1)]);
sqr[++tsqr] = Square(in[dw(i, j+1)], out[dw(i, j+1)], in[dw(i, j)], out[dw(i, j)]);
}
}
for (int i = 1; i <= tsqr; ++i) {
qz[++tqz] = smx(sqr[i].u, sqr[i].d, sqr[i].l, 1);
qz[++tqz] = smx(sqr[i].u, sqr[i].d, sqr[i].r+1, -1);
}
sort(qz + 1, qz + tqz + 1, cmp);
long long ans = 0;
for (int i = 1; i <= tqz; ++i) {
AddSeg(1, 1, N*M+1, qz[i].u, qz[i].d, qz[i].ad);
if (i != tqz) ans += (long long)Cal(1, 1, N) * (qz[i+1].ps - qz[i].ps);
// for (int j = 1; j <= 8; ++j)
// printf("tag[j] : %d cnt[j] : %d
", tag[j], cnt[j]);
}
printf("%lld
", ans / 2);
return 0;
}
总结
- 点对数量转化为平面上点的数量
- 一个点是另一个点的子孙可以转化为 dfs 序的区间限制，可以在计数题上用到