AGC056A - Three Cells per Row and Column

【题意】

给定一个n*n的矩阵，请构造出一种黑白染色方式，使得每行每列均恰好有3个黑色，且总共的黑色连通块数是n

【分析】

这是一个不是很好想的构造方式，首先考虑n是3的整数倍的情况

直接按照如下方式即可：

 当其不是3的倍数的时候，我们仍然模仿之前的方式，会得到如下的情况，但是这里存在连通块个数变多为n+2个的情况

考虑如何解决这个问题，可以通过交换一些行的方式使得连成黑色的连成一个

发现直接交换第一行和第行就可以减少一个，交换第行和最后一行又可以减少一个

这样就完成了构造

【代码】

#include
using namespace std;
typedef long long ll;
int n;
vector  res;
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&n);
    int pos=0;
    for(int i=0;i