网站托管一般多少钱,博客移植wordpress,做网站的广告图片,在线企业建站模板CF1368G Shifting Dominoesproblemsolutioncodeproblem
题目链接
solution
求的是最后棋盘本质不同的个数#xff0c;而本质不同等价于两个空格位置不同。
如果想要移动一个多米诺骨牌#xff0c;要求长边上下方有空位。
移动可以看成空位的移动。
所以我们考虑把一个 …
CF1368G Shifting Dominoesproblemsolutioncodeproblem
题目链接
solution
求的是最后棋盘本质不同的个数而本质不同等价于两个空格位置不同。
如果想要移动一个多米诺骨牌要求长边上下方有空位。
移动可以看成空位的移动。
所以我们考虑把一个 (x,y)(x,y)(x,y) 看成一个点表示该位置为空位。
然后向能转移的空位进行连边。
可以证明连边后形成的图形不是环而是森林。 利用皮克定理证明SIB2−1SI\frac{B}{2}-1SI2B−1 出现环意味着可以经过一系列操作后使得空位回到最原始的状态但是显然原来的空位地方已经有一个多米诺骨牌霸占了。 如果将棋盘黑白染色即一个多米诺骨牌恰好覆盖一个黑格子和一个白格子。
发现移动空位只会在同颜色格子上移动因为每次移动无非是行 / 列 ±2±2±2。
不同颜色格子之间答案互不影响。
对两棵树 dfn\text{dfn}dfn 序编号一个空位的所有移动可能就是其子树的大小。
两棵树里面某两个子树出现不同的情况就是两个子树大小的乘积。
将这个转化成二维矩阵面积问题。
显然矩阵之间会有交集所以相当于是扫描线求矩阵的并集。
code
#include cstdio
#include vector
#include iostream
#include algorithm
using namespace std;
#define maxn 200005
#define int long long
vector int G[maxn];
vector pair int, int pos[maxn];
char **s;
int **Hash;
int n, m, cnt, tot, ip;
int Y[maxn 2], id[maxn], tag[maxn 2], len[maxn 2], dfn[maxn], siz[maxn];
bool vis[maxn];
#define lson now 1
#define rson now 1 | 1struct scan { int x, down, up, k; }MS[maxn];void pushup( int now, int l, int r ) {if( tag[now] ) len[now] Y[r] - Y[l];else if( l 1 r ) len[now] 0;else len[now] len[lson] len[rson];
}void modify( int now, int l, int r, int L, int R, int k ) {if( R l or r L ) return;if( L l and r R ) { tag[now] k; pushup( now, l, r ); return; }if( l 1 r ) return;int mid ( l r ) 1;if( L mid ) modify( lson, l, mid, L, R, k );if( mid R ) modify( rson, mid, r, L, R, k );pushup( now, l, r );
}void link( int u, int v ) {vis[v] 1;G[u].push_back( v );
}void dfs( int u ) {dfn[u] ip, siz[u] 1;for( auto v : G[u] ) dfs( v ), siz[u] siz[v];
}signed main() {scanf( %lld %lld, n, m );s new char * [n 5];Hash new int * [n 5];for( int i 1;i n;i ) {s[i] new char [m 5];Hash[i] new int [m 5];scanf( %s, s[i] 1 );for( int j 1;j m;j )Hash[i][j] ( i - 1 ) * m j;}for( int i 1;i n;i )for( int j 1;j m;j ) {if( i 2 n and s[i 1][j] U and s[i 2][j] D ) link( Hash[i][j], Hash[i 2][j] );if( i - 2 1 and s[i - 1][j] D and s[i - 2][j] U ) link( Hash[i][j], Hash[i - 2][j] );if( j 2 m and s[i][j 1] L and s[i][j 2] R ) link( Hash[i][j], Hash[i][j 2] );if( j - 2 1 and s[i][j - 1] R and s[i][j - 2] L ) link( Hash[i][j], Hash[i][j - 2] );if( ! id[Hash[i][j]] ) {id[Hash[i][j]] cnt;if( s[i][j] L ) id[Hash[i][j 1]] cnt;if( s[i][j] U ) id[Hash[i 1][j]] cnt;}pos[id[Hash[i][j]]].push_back( { i, j } );}for( int i 1;i n;i )for( int j 1;j m;j )if( ! vis[Hash[i][j]] ) dfs( Hash[i][j] );for( int i 1;i cnt;i ) {int a pos[i][0].first, b pos[i][0].second;int c pos[i][1].first, d pos[i][1].second;int u Hash[a][b], v Hash[c][d];int l1 dfn[u], r1 dfn[u] siz[u] - 1;int l2 dfn[v], r2 dfn[v] siz[v] - 1;if( ( a b ) 1 ) swap( l1, l2 ), swap( r1, r2 ); MS[ tot] { l1, l2, r2 1, 1 }; Y[tot] l2;MS[ tot] { r1 1, l2, r2 1, -1 }; Y[tot] r2 1;}sort( Y 1, Y tot 1 );int m unique( Y 1, Y tot 1 ) - Y - 1;sort( MS 1, MS tot 1, []( scan a, scan b ) { return a.x b.x; } );int ans 0;for( int i 1;i tot;i ) {ans len[1] * ( MS[i].x - MS[i - 1].x );int down lower_bound( Y 1, Y m 1, MS[i].down ) - Y;int up lower_bound( Y 1, Y m 1, MS[i].up ) - Y;modify( 1, 1, m, down, up, MS[i].k );}printf( %lld\n, ans );return 0;
}
