CF1368G Shifting Dominoes

• problem
• solution
• code

problem

題目鏈接

solution

求的是最后棋盤本質不同的個數，而本質不同等價于兩個空格位置不同。

如果想要移動一個多米諾骨牌，要求長邊上下方有空位。

移動可以看成空位的移動。

所以我們考慮把一個 $(x,y)$ 看成一個點，表示該位置為空位。

然后向能轉移的空位進行連邊。

可以證明，連邊后形成的圖形不是環，而是森林。

• 利用皮克定理證明：$S=I+\frac{B}{2}?1$
• 出現環，意味著可以經過一系列操作后使得空位回到最原始的狀態，但是顯然原來的空位地方已經有一個多米諾骨牌霸占了。

如果將棋盤黑白染色，即一個多米諾骨牌恰好覆蓋一個黑格子和一個白格子。

發現移動空位只會在同顏色格子上移動，因為每次移動無非是行 / 列 $\pm 2$。

不同顏色格子之間答案互不影響。

對兩棵樹 $\text{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; }

總結

以上是生活随笔為你收集整理的CF1368G Shifting Dominoes（扫描线求矩阵的并集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。