小白月赛 F.草方块与牛排(构造)

本文主要是介绍小白月赛 F.草方块与牛排(构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小白月赛 F.草方块与牛排(构造)

显然 $r=\dfrac{n^2-4}{4}=\dfrac{n^2}{4}-1$

使用的个数 $r$ 为整数， $n$ 必须为偶数。

将行按照奇偶染色(第一行染0，第二行染1…)。那么牛排的类型只能为3个1、1个0 或者是3个0，1个1。

因为0和1的个数相等。

$3 x + y = 3 y + x$ ，所以 $x = y$ 。

$r = 2 x$ ， $r$ 为偶数。

假设 $n = 4 k$ ，那么 $r=4k^2-1$ 为奇数，矛盾。

因此 $n = 4 k + 2$ 型。

在这里插入图片描述

// Problem: 草方块与牛排
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();return ret*f;
}
inline void write(int x){        if(x<0){ putchar('-'); x=-x; }      if(x>9) write(x/10);     putchar(x%10+'0');     
}
int n;
inline int get(int x,int y){return (x-1)*n+y;
}
void print1(int x,int y){write(get(x,y)),putchar(' ');write(get(x,y+1)),putchar(' ');write(get(x,y+2)),putchar(' ');write(get(x+1,y)),putchar('\n');write(get(x+1,y+3)),putchar(' ');write(get(x+1,y+2)),putchar(' ');write(get(x+1,y+1)),putchar(' ');write(get(x,y+3)),putchar('\n');
}
void print2(int x,int y){write(get(x,y)),putchar(' ');write(get(x+1,y)),putchar(' ');write(get(x+2,y)),putchar(' ');write(get(x,y+1)),putchar('\n');write(get(x+3,y+1)),putchar(' ');write(get(x+2,y+1)),putchar(' ');write(get(x+1,y+1)),putchar(' ');write(get(x+3,y)),putchar('\n');
}
int main(){n=read();if(n%4==2){write((n*n-4)/4),putchar('\n');for(int j=3;j<=n;j+=4)for(int i=1;i<=n;i+=2)print1(i,j);for(int i=3;i<=n;i+=4) print2(i,1);}else write(-1);return 0;
}