题解 CF1408A 【Circle Coloring】

· · 题解

直接从左到右确定即可，因为每个位置有 3 个不同选择，但是相关的限制只有 2 个，所以必然有解。

\Theta(n)

code :

#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &x){
    static char ch; x = 0,ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }
int n,a[105],b[105],c[105],ans[105];
inline void solve(){
    int i,j;
    read(n);
    for (i = 1; i <= n; ++i) read(a[i]);
    for (i = 1; i <= n; ++i) read(b[i]);
    for (i = 1; i <= n; ++i) read(c[i]);
    ans[1] = a[1];
    for (i = 2; i < n; ++i) ans[i] = (a[i] == ans[i-1]) ? b[i] : a[i];
    if (a[n] != ans[n-1] && a[n] != ans[1]) ans[n] = a[n];
    else if (b[n] != ans[n-1] && b[n] != ans[1]) ans[n] = b[n];
    else if (c[n] != ans[n-1] && c[n] != ans[1]) ans[n] = c[n];
    for (i = 1; i <= n; ++i) write(ans[i]),putchar(i<n?' ':'\n');
}
int main(){ int T; read(T); while (T--) solve(); return 0; }