G-Grid Coloring 2020牛客暑期多校训练营（第六场）

https://ac.nowcoder.com/acm/contest/5671/G

过完这题的时候只过了20个，H过了30个，这是我没想到的。我出了名的不会cf div2 C难度的构造题，然而这道水题竟然最后也没比H多过多少。。。

首先我们先横着放横边，下一个放的等于上一个放的+1，然后把他们放完，这样保证了每一横条有不同的，因为相邻两个都不同

接着再横着放竖边，下一个放的等于上一个放的+1，由于相邻两个竖边构成一个矩形，所以他们不同就保证了每个矩形颜色都不一样。

这样放最后只可能会导致一竖列的颜色全部相同，一行的竖边有n+1条，那么如果(n+1)%k==0，就会有这样的情况，于是我们只要特判这种情况时，下一行的第一条竖边与上一行的第一条竖边颜色不一样就行了，因为(n+1)%k==0，所以一行可以放的每个颜色的数量是一样的。

注意特判n=1或k=1时是无解的

#include<bits/stdc++.h>
using namespace std;

const int maxl=210;

int n,k,ans;
int a[maxl][maxl],b[maxl][maxl];

inline void prework()
{
	scanf("%d%d",&n,&k);
}

inline void mainwork()
{
	if(2*(n+1)*n%k!=0 || k==1 || n==1)
	{
		ans=0;
		return;
	}
	ans=1;
	int now=0;
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n;j++)
		{
			++now;if(now>k) now=1;
			a[i][j]=now;
		}
	for(int i=1;i<=n;i++)
	{
		if((n+1)%k==0)
		{
			if(i==1)
				now=2;
			else
				now=b[i-1][1];
		}
		for(int j=1;j<=n+1;j++)
		{
			++now;if(now>k) now=1;
			b[i][j]=now;
		}
	}
}

inline void print()
{
	if(!ans)
		puts("-1");
	else
	{
		for(int i=1;i<=n+1;i++)
			for(int j=1;j<=n;j++)
				printf("%d%c",a[i][j]," \n"[j==n]);
		for(int j=1;j<=n+1;j++)
			for(int i=1;i<=n;i++)
				printf("%d%c",b[i][j]," \n"[i==n]);

	}
}

int main()
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		prework();
		mainwork();
		print();
	}	
	return 0;
}

 

本文地址：https://blog.csdn.net/liufengwei1/article/details/107615594