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;
}