CodeJam 2021 Round3 Square Free

• problem
• solution
• code
• code-std

problem

神奈子是個很愛打麻將的老婆婆，有一天她把她的麻將放進了一個 $n\times m$ 的網格圖里，每個麻將可以左斜著放入網格中（如 / ），也可以右斜著（如 \ ），如下圖所示。不過她還沒決定好應該怎么擺。

因為她很喜歡風，所以擺麻將的地方風很大，容易把麻將吹倒，因此存在兩個序列 $a$ 和 $b$，表示第 $i$ 行必須有恰好 $a_i$ 個麻將左斜，第 $j$ 列必須有恰好 $b_j$ 個麻將左斜，才能保證麻將的穩定性。

因為她很喜歡山，所以她喜歡山一般的參差不齊感，而不希望麻將形成規規整整的正方形（如下圖所
示）。

她非常沒耐心，所以你需要告訴她能否將麻將擺成符合要求的樣子，如果可以，為了節省她的時間，你只需要任意給出一種方案即可 。

$n,m\le 20$。

solution

20簡直就是各種算法和高復雜度爆艸

在考場上的 調整法 竟然過了，我也不知道對不對。 還是分享給大家。

這種給出任意一種方案，一般都是猜結論或者單純構造。

這里我從構造入手。

先考慮行的限制，每行從第一列開始直接就放 $a_i$ 個 /，剩下的放 \。每一行形如 //...//\\..\。

這樣首先是將行限制全都滿足了，在此基礎上繼續考慮列的限制。

從左往右每一列每一列的考慮，考慮到第 $i$ 列的時候，要求前 $i?1$ 列全都已經符合要求。

• 該列的 / 恰好滿足要求那就直接下一列。

• 該列的 / 大于要求。那么就需要將該列上的某幾行 / 替換成 \。

  直接枚舉每一行 $k$ ，然后再枚舉 $k$ 行后面 $j(j>i)$ 列的情況。

  如果 $k$ 行 $i$ 列恰好是 /，且 $k$ 行某個 $j$ 列恰好是 \，那么就可以交換兩個位置上的字符。

  $k$ 行的限制仍然滿足，也沒有改動前 $i?1$ 列。

  后面列的改變后面調整再說，現在只對前面負責。

• 該列的 / 小于要求。與上面同理，需要將該列上的某幾行 \ 替換成 /。不贅述。

以上是第一步調整。有可能還不行，就需要進行第二步調整。

以該列的 / 大于要求為例，可能會出現該列上的每個 \ 所在行的 $?j,j>i$ 列都是 \。

那么就找不到可以與該位置交換的 / 了。

這個時候就只能動前面的了。

考慮 $i$ 列的某行 $j_1$，該 $(j_1,i)$ 格子字符為 /，考慮現在將其調整為 \。

那么首先找到 $j_1$ 行的 $x(x<i)$ 列，$(j_1,x)$ 格子字符為 /。

如果這兩個交換，則第 $i$ 列的 / 數量就會減少 $1$，且 $j_1$ 行的限制沒有破壞。

此時發現，$x$ 列的限制破環了，再找一行 $j_2$，$(j_2,x)$ 上的字符為 \，將其改變成 /，又重新維護了 $x$ 列的限制。

又發現 $j_2$ 行的限制被破壞，又得找一個 $y$ 列，繼續調整$......$

會發現 $j_2$ 行后面 $y(y>i)$ 列一定有 \。

因為既然能進入到第二步的調整，那就證明任意行已經找不到 /。

將其改變為 /，那么 $j_2$ 行的限制就又重新維護了。

不管 $i$ 列以后的事情，那么所有行和前面所有列的限制仍然成立。

以該列的 / 小于要求同理，也不贅述。

兩步調整后，會發現，如果只有第一步調整是永遠不會出現正方形的，可是有第二步后就不能保證了。

所以進行第三步對正方形的調整。

而且上述調整發現只可能（？）出現邊長為 $1$ 的正方形。

因為上述調整是行列從小到大的。

一定是先將上一行想盡辦法的調整了再調整下一行，所以不可能下一行又折回去這種感覺。

直接枚舉每個位置為左上角格子，然后判斷一個 $2\times 2$ 格子是否構成正方形，如果是那么交換兩行，注意此時不能直接往下枚舉。

i.e.

/\ /\ \/

有可能換了后跟上面的重新組成了一個正方形，那就行減減，再判斷一遍。

最后三步調整后再判斷一下是否又正方形的出現，這是還出現就直接判為 IMPOSSIBLE。

很有可能是因為數據太水，導致我錯誤地艸過去了。哈哈哈哈

---

以下就是正解算法。

發現只要存在一個滿足行列限制的方案，就一定存在沒有正方形的方案。

如果存在正方形，可以將正方形所有格子內的字符全反轉，仍然滿足行列限制，但破環了正方形。

可以證明這樣是不會存在環，無限循環下去的。

證明：

將表格字符壓成一維的字符串表示，假設 / 的字典序大于 \。

那么每次反轉一個正方形后，字典序只會變小。

因此字典序最小的方案一定是不存在正方形的。

問題轉化為構造一個字典序最小的方案數。

再加上這個行列限制，明顯就是網絡流經典問題。

具體可見 code-std 實現。

code

#include <cstdio> #include <iostream> using namespace std; #define maxn 25 int n, m; int r[maxn], c[maxn]; //int ROW[maxn], COL[maxn]; int ans[maxn][maxn];int main() {freopen( "net.in", "r", stdin );freopen( "net.out", "w", stdout );scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ ) scanf( "%d", &r[i] );for( int i = 1;i <= m;i ++ ) scanf( "%d", &c[i] );for( int i = 1;i <= n;i ++ )for( int j = 1;j <= r[i];j ++ )ans[i][j] = 1;for( int j = 1;j <= m;j ++ ) {int cnt = 0;for( int i = 1;i <= n;i ++ )cnt += ans[i][j];if( cnt == c[j] ) continue;if( cnt > c[j] ) {for( int i = 1;i <= n and cnt != c[j];i ++ )if( ans[i][j] ) {for( int k = m;k > j;k -- )if( ! ans[i][k] ) {swap( ans[i][j], ans[i][k] );cnt --;break;}}for( int i = 1;i <= n and cnt != c[j];i ++ )if( ans[i][j] ) {for( int k = 1;k <= n;k ++ ) {for( int w = j - 1;w and i != k;w -- )if( ans[k][w] and ! ans[i][w] )for( int x = m;x > j;x -- )if( ! ans[k][x] ) {cnt --;ans[i][j] = 0;ans[i][w] = 1;ans[k][w] = 0;ans[k][x] = 1;goto nxtj;}}nxtj:;}}else {for( int i = 1;i <= n and cnt != c[j];i ++ )if( ! ans[i][j] ) {for( int k = m;k > j;k -- )if( ans[i][k] ) {swap( ans[i][j], ans[i][k] );cnt ++;break;}}for( int i = 1;i <= n and cnt != c[j];i ++ )if( ! ans[i][j] ) {for( int k = 1;k <= n;k ++ ) {for( int w = j - 1;w and i != k;w -- )if( ans[i][w] and ! ans [k][w] )for( int x = m;x > j;x -- )if( ans[k][x] ) {cnt ++;ans[i][j] = 1;ans[i][w] = 0;ans[k][w] = 1;ans[k][x] = 0;goto nxti;}}nxti :;}}// printf( "START: %d\n", j );// for( int i = 1;i <= n;i ++ ) {// for( int j = 1;j <= m;j ++ )// if( ans[i][j] ) printf( "%c", 47 );// else printf( "%c", 92 );// puts("");// }if( cnt != c[j] ) return ! printf( "IMPOSSIBLE\n" );}for( int i = 1;i < n;i ++ )for( int j = 1;j < m;j ++ )if( ans[i][j] and ! ans[i][j + 1] and ! ans[i + 1][j] and ans[i + 1][j + 1] ) {swap( ans[i][j], ans[i + 1][j] );swap( ans[i][j + 1], ans[i + 1][j + 1] );i -= 2;break;}for( int i = 1;i < n;i ++ )for( int j = 1;j < m;j ++ )if( ans[i][j] and ! ans[i][j + 1] and ! ans[i + 1][j] and ans[i + 1][j + 1] )return ! printf( "IMPOSSIBLE\n" );printf( "POSSIBLE\n" );for( int i = 1;i <= n;i ++ ) {for( int j = 1;j <= m;j ++ )if( ans[i][j] ) printf( "%c", 47 );// ROW[i] ++, COL[j] ++;else printf( "%c", 92 );puts("");}// for( int i = 1;i <= n;i ++ ) if( ROW[i] != r[i] ) return ! printf( "WA\n" );// for( int i = 1;i <= m;i ++ ) if( COL[i] != c[i] ) return ! printf( "WA\n" );return 0; }

code-std

#include <bits/stdc++.h> using namespace std; #define maxn 25 int a[maxn], b[maxn], r[maxn], c[maxn]; int n, m;bool check( int x, int y ) {memcpy( r, a, sizeof( a ) );memcpy( c, b, sizeof( b ) );for( int i = x;i <= n;i ++ ) {vector < pair < int, int > > v;for( int j = ( i == x ? y : 1 );j <= m;j ++ )v.push_back( { b[j], j } );sort( v.begin(), v.end() );for( int k = v.size() - 1;~ k and a[i];k -- )a[i] --, b[v[k].second] --;}bool flag = 1;for( int i = 1;i <= n;i ++ ) flag &= a[i] == 0;for( int i = 1;i <= m;i ++ ) flag &= b[i] == 0;memcpy( a, r, sizeof( r ) );memcpy( b, c, sizeof( c ) );return flag; }int main() {scanf( "%d %d", &n, &m );int sum = 0;for( int i = 1;i <= n;i ++ ) scanf( "%d", &a[i] ), sum += a[i];for( int i = 1;i <= m;i ++ ) scanf( "%d", &b[i] ), sum -= b[i];if( sum ) return ! puts( "IMPOSSIBLE" );if( ! check( 1, 1 ) ) return ! puts( "IMPOSSIBLE" );puts( "POSSIBLE" );for( int i = 1;i <= n;i ++ ) {for( int j = 1;j <= m;j ++ )if( check( i, j + 1 ) ) printf( "\\" );else a[i] --, b[j] --, printf( "/" );puts("");}return 0; }

總結

以上是生活随笔為你收集整理的[CodeJam 2021 Round 3] Square Free（调整法 / 字典序最小解网络流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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