清湖网站建设,网站建设前的市场分析,服装厂网站模板,wordpress批量插件CodeJam 2021 Round3 Square Freeproblemsolutioncodecode-stdproblem
神奈子是个很爱打麻将的老婆婆#xff0c;有一天她把她的麻将放进了一个 nmn\times mnm 的网格图里#xff0c;每个麻将可以左斜着放入网格中#xff08;如 / #xff09;#xff0c;也可以右斜着有一天她把她的麻将放进了一个 n×mn\times mn×m 的网格图里每个麻将可以左斜着放入网格中如 / 也可以右斜着如 \ 如下图所示。不过她还没决定好应该怎么摆。 因为她很喜欢风所以摆麻将的地方风很大容易把麻将吹倒因此存在两个序列 aaa 和 bbb表示第 iii 行必须有恰好 aia_iai 个麻将左斜第 jjj 列必须有恰好 bjb_jbj 个麻将左斜才能保证麻将的稳定性。
因为她很喜欢山所以她喜欢山一般的参差不齐感而不希望麻将形成规规整整的正方形如下图所 示。 她非常没耐心所以你需要告诉她能否将麻将摆成符合要求的样子如果可以为了节省她的时间你只需要任意给出一种方案即可 。
n,m≤20n,m\le 20n,m≤20。
solution
20简直就是各种算法和高复杂度爆艹
在考场上的 调整法 竟然过了我也不知道对不对。 还是分享给大家。
这种给出任意一种方案一般都是猜结论或者单纯构造。
这里我从构造入手。
先考虑行的限制每行从第一列开始直接就放 aia_iai 个 /剩下的放 \。每一行形如 //...//\\..\。
这样首先是将行限制全都满足了在此基础上继续考虑列的限制。
从左往右每一列每一列的考虑考虑到第 iii 列的时候要求前 i−1i-1i−1 列全都已经符合要求。 该列的 / 恰好满足要求那就直接下一列。 该列的 / 大于要求。那么就需要将该列上的某几行 / 替换成 \。 直接枚举每一行 kkk 然后再枚举 kkk 行后面 j(ji)j(ji)j(ji) 列的情况。 如果 kkk 行 iii 列恰好是 /且 kkk 行某个 jjj 列恰好是 \那么就可以交换两个位置上的字符。 kkk 行的限制仍然满足也没有改动前 i−1i-1i−1 列。 后面列的改变后面调整再说现在只对前面负责。 该列的 / 小于要求。与上面同理需要将该列上的某几行 \ 替换成 /。不赘述。
以上是第一步调整。有可能还不行就需要进行第二步调整。
以该列的 / 大于要求为例可能会出现该列上的每个 \ 所在行的 ∀j,ji\forall j,ji∀j,ji 列都是 \。
那么就找不到可以与该位置交换的 / 了。
这个时候就只能动前面的了。
考虑 iii 列的某行 j1j_1j1该 (j1,i)(j_1,i)(j1,i) 格子字符为 /考虑现在将其调整为 \。
那么首先找到 j1j_1j1 行的 x(xi)x(xi)x(xi) 列(j1,x)(j_1,x)(j1,x) 格子字符为 /。
如果这两个交换则第 iii 列的 / 数量就会减少 111且 j1j_1j1 行的限制没有破坏。
此时发现xxx 列的限制破环了再找一行 j2j_2j2(j2,x)(j_2,x)(j2,x) 上的字符为 \将其改变成 /又重新维护了 xxx 列的限制。
又发现 j2j_2j2 行的限制被破坏又得找一个 yyy 列继续调整..................
会发现 j2j_2j2 行后面 y(yi)y(yi)y(yi) 列一定有 \。
因为既然能进入到第二步的调整那就证明任意行已经找不到 /。
将其改变为 /那么 j2j_2j2 行的限制就又重新维护了。
不管 iii 列以后的事情那么所有行和前面所有列的限制仍然成立。
以该列的 / 小于要求同理也不赘述。
两步调整后会发现如果只有第一步调整是永远不会出现正方形的可是有第二步后就不能保证了。
所以进行第三步对正方形的调整。
而且上述调整发现只可能出现边长为 111 的正方形。 因为上述调整是行列从小到大的。 一定是先将上一行想尽办法的调整了再调整下一行所以不可能下一行又折回去这种感觉。 直接枚举每个位置为左上角格子然后判断一个 2×22\times 22×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;
}
