网站制作一般多少钱,网页游戏开服表大全,wordpress 微信 商城,网页传奇合击正题 题目大意 n∗mn*mn∗m填(((或者)))。求一个方案使得最多的行和列匹配。 解题思路
我们先考虑nnn或mmm为奇数#xff0c;那么显然奇数的肯定不必配#xff0c;那么就只需要考虑行或列即可。
若nnn和mmm都为偶数时
我们发现在边边的行列不可能都匹配上#xff0c;那就…正题 题目大意
n∗mn*mn∗m填(((或者)))。求一个方案使得最多的行和列匹配。 解题思路
我们先考虑nnn或mmm为奇数那么显然奇数的肯定不必配那么就只需要考虑行或列即可。
若nnn和mmm都为偶数时
我们发现在边边的行列不可能都匹配上那就让他们无私奉献一下那么除了这几行就都可以匹配上 Suchas:Such\ as:Such as: 匹配数为nm−4nm-4nm−4
当然我们也可以牺牲一般的行(或列)使得最边边的列(或行)匹配上 Suchas:Such\ as:Such as: 匹配数为n2m−1\frac{n}{2}m-12nm−1
判断一下哪种更优即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n,m;
bool v[5001][5001],sw;
int main()
{//freopen(butterfly.in,r,stdin);
// freopen(butterfly.out,w,stdout);scanf(%d%d,n,m);if(m1){int k1;for(int i1;in;i){k^1;for(int j1;jm;j)putchar(k?):();putchar(\n);}}else if(n1){for(int i1;in;i){int k1;for(int j1;jm;j){k^1;putchar(k?):();}putchar(\n);}}else{ if(nm) sw1,swap(n,m);if(nm-4n/2m-1){for(int i1;im;i)v[1][i]1,v[n][i]0;int z0;for(int i2;in;i){int kz;z^1;for(int j1;jm;j)v[i][j](k^1);}}else{for(int i1;im;i)v[1][i]1,v[n][i]0;int z0;for(int i2;in;i){int kz;z^1;v[i][1]1;v[i][m]0; for(int j2;jm;j)v[i][j](k^1);}}if(!sw){for(int i1;in;i){for(int j1;jm;j)putchar(v[i][j]?(:));putchar(\n);}}else{for(int i1;im;i){for(int j1;jn;j)putchar(v[j][i]?(:));putchar(\n);}}}
}
