C/C++教程

[CF1503B]3-Coloring

本文主要是介绍[CF1503B]3-Coloring,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

壹、题目描述 ¶

传送门 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

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

这篇关于[CF1503B]3-Coloring的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!