传送门

文章目录

• 题意：
• 思路：

题意：

给一个$n\ast n$的格子染色，一共可以染三种颜色，每次都会给一种颜色，代表当前这种颜色不可以使用，染色要求相邻的颜色不能相同，让你给出一种染色方案。

思路：

类似奇偶染色，我们按$(i+j)\mathrm{m}\mathrm{o}\mathrm{d}2$将块分成奇偶，让后分三种情况：
$(1)$ 当前禁止染颜色$1$，那么我们就将颜色$2$填到偶数格子里，如果偶数格子没有了，就将$3$填到奇数格子里。
$(2)$ 当前禁止染颜色$2$，那么我们就将颜色$1$填到奇数格子里，如果奇数格子没有了，就将$3$填到偶数格子里。
$(3)$ 当前禁止染颜色$3$，那么我们就将颜色$1$填到奇数格子里，如果奇数格子没有了，就将$2$填到偶数格子里。
可以发现，这样染色是不会有相同颜色相邻的，因为这样首先保证了$1,2$不会相邻，让后由于是某个格子全用完之后才填颜色$3$，那么颜色$3$之间也不会相邻。

//#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=110,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; vector<PII>v[10];void print(int col,PII x) {printf("%d %d %d\n",col,x.X,x.Y);fflush(stdout); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)v[(i+j)%2].pb({i,j});for(int i=1;i<=n*n;i++){int x; scanf("%d",&x);if(x==1){if(v[1].size()){print(2,v[1].back());v[1].pop_back();}else{print(3,v[0].back());v[0].pop_back();}}else if(x==2){if(v[0].size()){print(1,v[0].back());v[0].pop_back();}else{print(3,v[1].back());v[1].pop_back();}}else{if(v[0].size()){print(1,v[0].back());v[0].pop_back();}else{print(2,v[1].back());v[1].pop_back();}}}return 0; } /**/、

总结

以上是生活随笔为你收集整理的Codeforces Round #712 (Div. 2) D. 3-Coloring 交互 构造的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。