壹、题目描述 ¶

传送门 to CF

中文翻译：

这是一道交互题。

现有一个 \(n\times n\) 的网格，你要在这个网格中填入 \(3\) 种颜色 \(1,2,3\). 你可以填任意一种颜色任意多次，只要你可以赢。

程序会和你交互 \(n^2\) 次，每一次程序会给你一种颜色 \(a\)，表示在这一轮中你不能填入颜色 \(a\)，每一次交互程序输入之后，你需要立即输出三个参数 \(\lang b,i,j\rang\) 表示在格子 \((i,j)\) 处填入颜色 \(b(b\in[1,3])\)，注意，\((i,j)\) 必须是一个尚未被染色的格子。

你需要确保在 \(n^2\) 次交互之后，这个网格的相邻的格子（共用一条边）颜色不同。

你一定有必胜策略。

注意：交互程序有可适应性，即它会根据你的操作选择最优的策略。

交互过程如下：

最开始你需要读入 \(n\) 表示网格的大小，然后进入回合。

每一次回合，你需要先读入一个 \(a(a\in[1,3])\)，含义如上。

然后，你必须输出三个参数 \(\lang b,i,j\rang\)，含义如上。

在 \(n^2\) 次交互完成之后，请立即退出程序。

数据范围与提示：\(2\le n\le 100\)，不要忘记刷新缓冲区！

贰、题解 ¶

比较经典的黑白格染色问题。下面把颜色 \(i\) 称为 \(\#i\).

考虑将棋盘分成黑色格子和白色格子，就像国际象棋的棋盘那样，然后，我们贪心地将 \(1\) 颜色填入白色格子，将 \(2\) 颜色填入黑色格子，那 \(3\) 颜色呢？很简单，如果白色格子填满了就往黑色格子里面填，反之，往白色格子填，显然，不可能存在两个 \(3\) 号色，其中一个在黑格，一个在白格。

总而言之，\(\#3\) 就是拿来 “中和” 一种颜色被禁止多次的情况，这种颜色能够被使用的次数变少了，我们就要拿 \(3\) 来替代这种颜色出现的次数，使得这种颜色能够填满它所对应的 黑色/白色 格子。

所以，我们就有了一个填颜色的法则：

• \(\#1\) 被禁止，考虑能够将 \(\#2\) 填入黑色格子，如果不能，则说明 \(\#1\) 出现太少了（\(\#2\) 都被填完了，\(\#1\) 还能不少？），那就用 \(\#3\) 去补 \(\#1\) 对应的白格；
• \(\#2\) 被禁止，考虑能够将 \(\#1\) 填白色格子，如果不能，则说明 \(\#2\) 出现太少了，那就用 \(\#3\) 去补 \(\#2\) 对应的黑格；
• \(\#3\) 被禁止，随便找 \(\#1\) 填入白色格子或者 \(\#2\) 填入黑色格子即可；

叁、参考代码 ¶

#define Endl putchar('\n')
#define mp(a, b) make_pair(a, b)
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define fep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline T readin(T x){
	x=0; int f=0; char c;
	while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
	for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
	return f? -x: x;
}

int n;

inline void print(int b, int i, int j){
	printf("%d %d %d\n", b, i, j); fflush(stdout);
}

vector<pii>pos[2];

signed main(){
	scanf("%d", &n);
	// 0: black ;  1: white
	rep(i, 1, n) rep(j, 1, n)
		pos[(i+j)&1].push_back(mp(i, j));
	int a, b, use;
	for(int i=1; i<=n*n; ++i){
		scanf("%d", &a);
		if(a==1){
			if(!pos[0].empty())
				use=0, b=2;
			else use=1, b=3;
		}
		else if(a==2){
			if(!pos[1].empty())
				use=1, b=1;
			else use=0, b=3;
		}
		else if(a==3){
			if(!pos[1].empty())
				use=1, b=1;
			else use=0, b=2;
		}
		print(b, pos[use].back().fi, pos[use].back().se);
		pos[use].pop_back();
	}
	return 0;
}

肆、用到 の Trick

“相邻禁止” 可以往黑白格分类方向思考，那东西长得就一副国际象棋的磨样，刚好可以错开相邻。