题解 CF1147F 【Zigzag Game】

· · 题解

标签: 构造, 博弈论.

假设已知双方的属性并且我方先移动(即我方为 B ), 尝试构造一组匹配, 使得对于任意两条匹配中的边 (a, b), (c,d) 满足: 如果我方走完 (a,b) 后对方可以走 (b,c) , 则我方可以接着走 (c, d) .

如果存在这样的匹配我方显然必胜, 因为不论对方如何移动, 我方只需要沿着匹配的边移动必定合法(由于是匹配所以之前没访问过), 最终获胜.

经过精心构造, 发现上述匹配确实存在, 简单阐述一下原因:

不妨设我方属性为 I (如果为 D 将边权取相反数即可), 上述条件等价于: 使得对于任意两条匹配中的边 (a, b), (c,d) , 若 w_{(a,b)}>w_{(b,c)} , 则 w_{(c,d)}>w_{(b,c)} .

我们发现这个条件与稳定婚姻问题需要满足的条件形式是一致的: 令起点所在的一部(也即 a,c 所在的一部)的点优先度为按边权从大到小排序, 另一部(也即 b,d 所在的一部)的点优先度为按边权从小到大排序. 那么对于匹配关系 (a,b),(c,d) , 若 b 认为 c 比 a 优, 则 c 不能认为 b 比 d 优, 否则婚姻不稳定. 也即若 w_{(b,a)}>w_{(b,c)} , 则 w_{(c,d)}>w_{(c,b)} , 形式完全一致.

众所周知, 稳定婚姻问题是必定有解的, 所以我们可以构造出符合条件的匹配, 这里不赘述稳定婚姻状态的具体的构造方法.

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

不得不说这种博弈的交互题调起来是真的恶心.

#include <bits/stdc++.h>
using namespace std;
int read();

int n;
char t[102];
int w[102][102], rnk[102][102], pos[102];

vector<int> p[102];
queue<int> q;

void init(int t) {
    for (int i = 1; i <= n; ++i) {
        p[i].clear(), p[i + n].clear();
        for (int j = 1; j <= n; ++j)
            p[i].push_back(j + n), p[i + n].push_back(j);
        sort(p[i].begin(), p[i].end(),
             [&](int a, int b) { return w[i][a - n] > w[i][b - n] ^ t; });
        sort(p[i + n].begin(), p[i + n].end(),
             [&](int a, int b) { return w[a][i] < w[b][i] ^ t; });
        q.push(i), pos[i] = 0, pos[i + n] = n;
        for (int j = 0; j < n; ++j)
            rnk[j][p[i][j]] = j, rnk[i + n][p[i + n][j]] = j;
    }

    while (!q.empty()) {
        int u = q.front(), v;
        while (pos[v = p[u][pos[u]]] < rnk[v][u]) ++pos[u];
        if (pos[v] < n) q.push(p[v][pos[v]]);
        pos[v] = rnk[v][u], q.pop();
    }
}

int main() {
    for (int T = read(); T; --T) {
        n = read();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) w[i][j] = read();
        puts("B"), fflush(stdout), scanf("%s", t);
        if (t[0] == 'I')
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j) w[i][j] = -w[i][j];
        int u;
        for (init((u = read()) > n); ~u; u = read())
            printf("%d\n", p[u][pos[u]]), fflush(stdout);
    }
    return 0;
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}