题解 CF1887E【Good Colorings】

萌萌交互题。

对网格图进行二分图建模，左部 \(n\) 个点表示每一行，右部 \(n\) 个点表示每一列。若格子 \((i,j)\) 被染成 \(c\) 色，就连接 \((L_i,R_j,c)\) 的边。

由抽屉原理易证，在初始局面中至少有一个各边颜色均不同的偶环。获胜条件相当于存在一个各边颜色均不同的四元环。

讨论环长是否为四的倍数。若不为四的倍数，则询问任意一对正对面的点对应的格子；若为四的倍数，错开一位即可。（如图所示）

这样，我们就可以将大环划分为两个大小约为一半的小环。显然，无论询问的边被染成什么颜色，两个小环之中至少有一个不包含这种颜色。在第一个图中为左半部分，在第二个图中为右半部分。

至此，我们可以由一个各边颜色均不同的偶环，经过一次询问，得到一个规模减半的各边颜色依然不同的偶环。重复询问直到环长为四，最大询问次数不超过 \(10\)。

需要注意的一点是，在每组数据结束后，需要读入一行字符串 OK。

// Problem: Good Colorings
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1887E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 2e3 + 5;

int T, n, col[N][N], vis[N];
vector<int> e[N], cyc;
stack<int> stk;

bool dfs(int u, int f) {
    vis[u] = 1;
    stk.push(u);
    for(int v : e[u]) {
        if(v == f || vis[v] == 2) continue;
        if(vis[v] == 1) {
            if(v <= n) cyc.push_back(v);
            while(stk.top() != v) {
                cyc.push_back(stk.top());
                stk.pop();
            }
            if(v > n) cyc.push_back(v);
            return true;
        }
        if(dfs(v, u)) return true;
    }
    vis[u] = 2;
    stk.pop();
    return false;
}

void solve() {
    cin >> n;
    rep(i, 1, 2 * n) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(n + v);
        e[n + v].push_back(u);
        col[u][n + v] = i;
        col[n + v][u] = i;
    }
    rep(i, 1, 2 * n) if(vis[i] == 0) if(dfs(i, 0)) break;
    while(cyc.size() > 4) {
        int sz = cyc.size();
        int uid = 0, vid = sz % 4 == 0 ? sz / 2 + 1 : sz / 2;
        int u = cyc[uid], v = cyc[vid], c;
        cout << "? " << u << " " << v - n << endl << flush;
        cin >> c;
        col[u][v] = col[v][u] = c;
        bool flag = true;
        rep(i, uid, vid - 1) if(col[cyc[i]][cyc[i + 1]] == c) flag = false;
        vector<int> tmp;
        if(flag) {
            rep(i, uid, vid) tmp.push_back(cyc[i]);
        }
        else {
            tmp.push_back(cyc[uid]);
            per(i, cyc.size() - 1, vid) tmp.push_back(cyc[i]);
        }
        swap(cyc, tmp);
    }
    cout << "! " << cyc[0] << " " << cyc[2] << " " << cyc[1] - n << " " << cyc[3] - n << endl << flush;
    string result;
    cin >> result;
    assert(result == "OK");
}

void clear() {
    rep(i, 1, 2 * n) {
        rep(j, 1, 2 * n) col[i][j] = 0;
        vis[i] = 0;
        e[i].clear();
    }
    cyc.clear();
    while(!stk.empty()) stk.pop();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; --T) {
        solve();
        clear();
    }
    return 0;
}