[CF1503B]3-Coloring
2021/5/3 10:27:57
本文主要是介绍[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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享