D. 3-Coloring Codeforces Round #712 (Div. 2)（题解）

题目链接：D. 3-Coloring
题意：略；
思路：和答案思路不一样，开始设两个对角线一个是从（1,1）开始，另一个是从（2,1）开始然后开始处理，这两个对角线一个是奇数行的对角线，一个是偶数行的对角线，比方说一个对角线(2,1),(4,1),(6,1)是偶数行对角线，然后保证该对角线上是同一种颜色，如果能染该种颜色就染该种，否则肯定能染另一条对角线，然后直到有对角线遍历完，标记一下该对角线，比方说剩下一条奇数行对角线，那么这条线只要不染偶数行的颜色，就一定可以。复杂度\(\Theta(n^2)\)
\(Coding:\)

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<‘0‘||c>‘9‘;c=ch())if(c==‘-‘)f=-f;
for(x=0;c>=‘0‘&&c<=‘9‘;c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc(‘-‘),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+‘0‘);
}
const int N = 10000+10;
int mex[4] = {0,2,3,1};
int n;
int top[110][110];
pair<int,int>idx,idy;
int gos(int a,int b){
    rep(i,1,3){
        if(i!=a&&i!=b)return i;
    }
    return 1;
}
void solve(){
    scanf("%d",&n);
    idx = {2,0};idy = {3,0};
    rep(i,1,n+1){
        i++;
        top[i][0] = 1;
    }
    rep(i,2,n+1){
        i++;
        top[i][0] = 2;
    }
    int flag = 0;int a = top[idx.x][idx.y],b = top[idy.x][idy.y];
    rep(test,1,n*n){
        int f;
        scanf("%d",&f);
        int l , r , k;
        if(flag == 1)goto stk;
        else if(flag == 2)goto stp;
        if(f == a){
            stp:
            idy.x--;idy.y++;
            if(idy.x<1||idy.y>n){
                idy.x = idy.x + idy.y + 1;
                idy.y = 1;//(6,1)
                if(idy.x>=2*n){flag = 1;goto stk; }
                if(idy.x>n)idy.y = idy.y + idy.x - n,idy.x = n;
            }
            top[idy.x][idy.y] = b;
            k = b;
            l = idy.x;
            r = idy.y;
            if(flag == 2){
                k = gos(f,a);
            }
            top[idy.x][idy.y] = k;
        }
        else {
            stk:
            idx.x--;idx.y++;
            if(idx.x<1||idx.y>n){
                idx.x = idx.x + idx.y + 1;
                idx.y = 1;
                if(idx.x>=2*n){flag = 2;goto stp; }
                if(idx.x>n)idx.y = idx.y + idx.x - n,idx.x = n;
            }
            //printf("b:%d %d\n",idy.x,idy.y);
            top[idx.x][idx.y] = a;
            k = a;
            l = idx.x;
            r = idx.y;
            if(flag == 1){
                k = gos(f,b);
            }
            if(flag)top[idx.x][idx.y] = k;
        }
        printf("%d %d %d\n",k,l,r);
        fflush(stdout);//交互性加上这句话
    }
}
signed main(){
    solve();
    return 0;
}

D. 3-Coloring Codeforces Round #712 (Div. 2)（题解）

原文：https://www.cnblogs.com/violentbear/p/14634497.html