CF1147F Zigzag Game 题解

题意：

这是一道交互题，并且有 \(T\) 组数据。

给出一个两边均有 \(n\) 个节点的完全二分图，左部点由 \(1\) 到 \(n\) 编号，右部点由 \(n+1\) 到 \(2n\) 编号。输入中会给出一个 \(n \times n\) 的矩阵 \(a\)，其中 \(a_{i,j}\) 表示连接 \(i\) 和 \(j+n\) 的边的边权。

现在有两个玩家 Alice 和 Bob 在这个图上玩游戏。首先 Alice 会选择 "increasing"（增加）或者 "decreasing"（减少）中的一个属性，Bob 则会自动选择另一个。接下来由 Alice 在图上选择一个起始节点 \(p\) 放上一枚棋子，Bob 选择一条连接节点 \(p\) 的边 \((p,q)\)，将棋子移动到 \(q\)。

接下来由 Alice 先手轮流进行操作。每一次操作时操作方需要选择一个与当前节点 \(x\) 相邻的未被经过的节点 \(y\)。设 \(w\) 为 \((x,y)\) 的边权，\(w'\) 为上一次移动时的边权，那么如果当前操作方在最开始选择 "increasing"，则需要满足 \(w > w'\)，否则需要满足 \(w < w'\)。然后当前操作方将棋子移动到 \(y\)。无法移动的操作方失败。

现在你需要与交互库模拟这样一盘游戏，包括选择先后（"Alice" 或者 "Bob"）、选择属性（"increasing" 或者 "decreasing"）、选择初始节点、选择移动节点和游戏过程。你需要保证在与交互库的游戏过程中获胜。

交互格式略。数据范围：\(1 \le T,n \le 50,~1 \le a_{i,j} \le n^2\) 。

可以先去做一下 P4055 [JSOI2009] 游戏，是一道经典的二分图博弈题。

那么根据二分图博弈的经典结论，先手必败当且仅当原图存在完美匹配。

而这道题本身就是完美匹配，这使得我们考察后手是否仍存在必胜策略（选择后手的 Bob）。

显然我们需要构造一种匹配，使得任意两条匹配中的边 \((a,b),(c,d)\) 满足：

我们取了 \((a,b)\)，对方选择了 \((b,c)\) ，而我们可以继续选择 \((c,d)\) 。

设对方选择了 increasing （否则我们把边权取反即可），即我们选择了 decreasing 。

那么上述条件等价于，使得对于任意两条匹配中的边 \((a,b),(c,d)\) 满足

若 \(w(a,b) < w(b,c)\) ，则有 \(w(c,d) < w(b,c)\) 。

可以发现，这个条件和稳定婚姻问题形式上是一致的。

对于匹配关系 \((a,b),(c,d)\) ，若 \(b\) 认为 \(c\) 比 \(a\) 优，则 \(c\) 不能认为 \(b\) 比 \(d\) 优，否则会导致不稳定。

即，若 \(V(b,a) < V(b,c)\) ，则 \(V(c,d) > V(c,b)\) 。其中 \(V(i,j)\) 为 \(i\) 对 \(j\) 的评分/优先级。

如果我们钦定

从 \(a,c\) 一侧指向 \(b,d\) 一侧的边按边权从小到大排序，即 \(w(a,b_1) < w(a,b_2)\) 。
从 \(b,d\) 一侧指向 \(a,c\) 一侧的边按边权从大到小排序，即 \(w(b,a_1) > w(b,a_2)\) 。

那么可以得出：若 \(w(b,a) < w(b,c)\) ，则 \(w(c,d) > w(c,b)\) 。

而稳定婚姻问题是一定有解的，于是我们只需要构造出这样的匹配即可。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define mem(a) memset(a, 0, sizeof(a))
#define pb push_back
#define N ((int)(66))

char op; vector<int> vec[N], tmp;
int n, vis[N], pos[N], npy[N * 2], a[N][N], rk[N][N];
void solve(int type)
{
    mem(pos); mem(npy); rep(i, 1, n) vec[i].clear();
    static queue<int> q; while(!q.empty()) q.pop();
    rep(i, 1, n)
    {
        q.push(i); rep(j, 1, n) vec[i].pb(j);
        auto cmp = [&](int x, int y) { return (a[i][x] < a[i][y]) ^ type; };
        sort(vec[i].begin(), vec[i].end(), cmp);
    }
    rep(i, 1, n)
    {
        tmp.clear(); rep(j, 1, n) tmp.pb(j);
        auto cmp = [&](int x, int y) { return (a[x][i] > a[y][i]) ^ type; };
        sort(tmp.begin(), tmp.end(), cmp);
        rep(j, 0, n - 1) rk[i][tmp[j]] = j + 1;
    }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        while(!npy[u])
        {
            int v = vec[u][pos[u]++];
            if(!npy[v + n] || rk[v][npy[v + n]] > rk[v][u])
            {
                npy[npy[v + n]] = 0; if(npy[v + n]) q.push(npy[v + n]);
                npy[v + n] = u; npy[u] = v + n;
            }
        }
    }
}
void work()
{
    cin >> n; rep(i, 1, n) rep(j, 1, n) cin >> a[i][j];
    cout << "B" << endl; cin >> op;
    if(op == 'D') { rep(i, 1, n) rep(j, 1, n) a[i][j] = -a[i][j]; }
    int x; cin >> x; if(~x) { solve(x > n); cout << npy[x] << endl; } else return;
    cin >> x; while(~x) { cout << npy[x] << endl, cin >> x; }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) work();
    return 0;
}