XCPC wiki - 交互

博弈

CF1991E. Coloring Game (1900)

有一个由$n$ 个顶点和$m$ 条边组成的无向图。每个顶点可以用三种颜色之一着色。初始时，所有顶点都未着色。

Alice 和 Bob 正在玩一个包含$n$ 轮的游戏。在每一轮中，都会发生以下两个步骤：

1. Alice 选择两种不同的颜色。
2. Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。

如果存在连接两个相同颜色结点的边，则 Alice 获胜。否则 Bob 获胜。给你这个图。决定想扮演哪位玩家并赢得游戏，然后与交互库玩这个游戏。

void eachT() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> E(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    // BFS 二分图染色 
    bool bipartite = true;
    vector<int> c(n + 1, 0);
    c[1] = 1;
    queue<int> Q;
    Q.push(1);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : E[u]) {
            if (c[v] == 0) {
                c[v] = 3 ^ c[u];
                Q.push(v);
            }
            else if (c[v] == c[u]) {
                bipartite = false;
            }
        }
    }

    if (bipartite) {  // 可以构成二分图 
        cout << "Bob" << endl;

        vector<int> vec[3];
        for (int i = 1; i <= n; ++i) {
            vec[c[i]].push_back(i);
        }

        for (int i = 1; i <= n; ++i) {
            int f, g;
            cin >> f >> g;

            vector<int> vis(4);
            vis[f] = vis[g] = 1;

            if (vis[1] && !vec[1].empty()) {  // 有 1
                cout << vec[1].back() << " 1" << endl;
                vec[1].pop_back();
            }
            else if (vis[2] && !vec[2].empty()) {  // 有 2
                cout << vec[2].back() << " 2" << endl;
                vec[2].pop_back();
            }
            else if (!vec[1].empty()) {
                cout << vec[1].back() << " 3" << endl;
                vec[1].pop_back();
            }
            else {
                cout << vec[2].back() << " 3" << endl;
                vec[2].pop_back();
            }
        }
    }
    else {
        cout << "Alice" << endl;

        for (int i = 1; i <= n; ++i) {
            cout << "1 2" << endl;

            int f, g;
            cin >> f >> g;
        }
    }
}

Geo Game

平面上$n$ 个整点，且另有一个点为起点，先手玩家和后手玩家依次选点，与上轮对手选的点连条路径。如果这$n$ 条路径的平方和为偶数，则先手胜；否则后手胜。

void eachT() {
    int n;
    cin >> n;

    int x0, y0;
    cin >> x0 >> y0;

    set<int> s[2];
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;

        s[(0ll + x + x0 + y + y0) % 2].insert(i);
    }

    bool me = 0;
    if (s[0].size() >= s[1].size()) {
        cout << "First" << endl;
        me = 1;
        swap(s[0], s[1]);
    }
    else {
        cout << "Second" << endl;
        me = 0;
    }

    for (int t = 0; t < n; ++t) {
        if (me) {
            if (!s[0].empty()) {
                cout << *s[0].begin() << endl;
                s[0].erase(s[0].begin());
            }
            else {
                cout << *s[1].begin() << endl;
                s[1].erase(s[1].begin());
            }
        }
        else {
            int x;
            cin >> x;
            s[0].erase(x);
            s[1].erase(x);
        }
        me ^= 1;
    }
}

交互

Guess The Tree

求有$n$ 节点的树的每一条边。询问$a,b$，返回满足$|d(a,x) - d(b,x)|$ 最小的$x$，如果存在多个这样的节点，返回$d(a,x)$ 较小的那一个。

最多使用$15n$ 次查询。$n \leqslant 1000$。

期望次数$n\log n$，分治递归求解。

int query(int a, int b) {
    cout << "? " << a << ' ' << b << endl;

    cin >> a;
    return a;
}

void eachT() {
    int n;
    cin >> n;

    vector<int> vis(n + 1);
    vector<pair<int, int>> res;
    auto solve = [&](auto&& self, int a, int b) -> void {
        int x = query(a, b);
        if (x == a) {
            res.emplace_back(a, b);
            vis[x] = 1;
        }
        else if (!vis[x]) {
            self(self, x, b);
            self(self, a, x);
        }
        else {
            self(self, a, x);
        }
    };

    vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            solve(solve, i, 1);
        }
    }

    cout << "! ";
    for (auto& [a, b] : res) {
        cout << a << ' ' << b << ' ';
    }
    cout << endl;
}

2024 江苏省赛 C. Radio Direction Finding

int query(int x) {
    cout << "? " << x << endl;

    cin >> x;
    return x;
}

void answer(int a, int b) {
    cout << "! " << a << " " << b << endl;
    return;
}

void eachT() {
    int n;
    cin >> n;

    int a1 = query(1), an = query(n);

    if (a1 == an + 2) {  // all left
        int a = an, b = query(n - a / 2);

        if (a & 1) {
            answer(n - (a / 2 + (b + 1) / 2), n - (a / 2 - (b - 1) / 2));
        }
        else {
            answer(n - (a / 2 + b / 2), n - (a / 2 - b / 2));
        }
    }

    if (an == a1 + 2) {  // all right
        int a = a1, b = query(1 + a / 2);

        if (a & 1) {
            answer(1 + (a / 2 + (b + 1) / 2), 1 + (a / 2 - (b - 1) / 2));
        }
        else {
            answer(1 + (a / 2 + b / 2), 1 + (a / 2 - b / 2));
        }
    }

    if (a1 == an + 1) {  // opposite
        answer((n + 1) / 2, n - an + n / 2);
    }

    if (an == a1 + 1) {
        answer((n + 1) / 2, 1 + a1 - n / 2);
    }

    if (a1 == an) {
        if (a1 <= n / 2) {
            int l = 1, r = (n + 1) / 2;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (query(mid) == a1) l = mid + 1;
                else r = mid - 1;
            }
            answer(r, r + n - a1);
        }
        else {
            int l = 1, r = (n + 1) / 2;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (query(mid) == n - a1) r = mid - 1;
                else l = mid + 1;
            }
            answer(l, l + n - a1);
        }
    }
}

ace5 and Task Order

交互库会先生成一个长度为$n$ 的$1\sim n$ 排列与一个$[1,n]$ 内的正整数$x$。你需要通过询问确定整个排列。

你可以通过格式 ? i 向交互库询问，返回值有三种：

• <：代表$a_i<x$，该次询问后，$x\leftarrow x-1$；
• >：代表$a_i>x$，该次询问后，$x\leftarrow x+1$；
• =：代表$a_i=x$。

询问次数不超过$40n$，$n\leq 2000$。

#include <chrono>
#include <random>
mt19937_64 rng{ chrono::steady_clock::now().time_since_epoch().count() };

char query(int x) {
    cout << "? " << x + 1 << endl;

    char c;
    cin >> c;
    return c;
}

basic_string<int> solve(basic_string<int>& a) {
    if (a.size() < 2) return a;

    const int n = a.size();
    int pos = rng() % n;    // 否则会被卡成 n^2
    while (query(a[pos]) != '=') {}

    basic_string<int> le, ge;
    for (int i = 0; i < n; ++i) {
        if (i == pos) continue;
        if (query(a[i]) == '<') {
            le += a[i];
        }
        else {
            ge += a[i];
        }
        query(a[pos]);
    }

    le = solve(le);
    ge = solve(ge);

    return le + a[pos] + ge;
}

void eachT() {
    int n;
    cin >> n;

    basic_string<int> a;
    a.resize(n);
    iota(a.begin(), a.end(), 0);

    a = solve(a);
    vector<int> res(n);
    for (int i = 0; i < n; ++i) {
        res[a[i]] = i + 1;
    }

    cout << "! ";
    for (int i = 0; i < n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
}

Salyg1n and Array

给定$n$ 与$k$（均为偶数，且$k \leqslant n \leqslant k^{2} \leqslant 2500$），

• 目标：求长度为$n$ 的隐藏序列$a$ 的异或和。
• 询问：给定一个数$i$，交互器会返回$a_i\oplus a_{i+1}\oplus \dots\oplus a_{i+k-1}$，在询问后，$a_i,a_{i+1},\dots,a_{i+k-1}$ 将会被前后颠倒。至多$57$ 次。

期望询问次数$\cfrac{n}{k}+o$。

对于余数部分，不难有$n \bmod k$ 的询问方案，但询问次数为$\cfrac{n}{k}+n \bmod k=2\sqrt{n}$，无法通过。

进一步考虑，余数部分只需问两次。

int query(int x) {
    cout << "? " << x << endl;
    cin >> x;
    return x;
}

void eachT() {
    int n, k;
    cin >> n >> k;

    int res = 0, pos = n % k;
    res ^= query(1);
    res ^= query(1 + pos / 2);
    for (int i = pos + 1; i + k - 1 <= n; i += k) {
        res ^= query(i);
    }
    
    cout << "! " << res << endl;
}

CF1990E2. Catch the Mole (2500)

给定以$1$ 为根的$n$ 个节点的树。有一只隐藏的鼹鼠位于某个节点上，每次你可以向交互库询问鼹鼠是否在节点$x$ 的子树内，若鼹鼠不在这棵子树内，它就会往上走一步，否则不动。

$160$ 次内确定鼹鼠的当前位置。数据范围：$n \leqslant 5000$。

期望复杂度为$2\sqrt{n}+\log n$，即$B+\cfrac{n}{B}+\log n$。

int query(int x) {
    cout << "? " << x << endl;

    cin >> x;
    return x;
}

void answer(int x) {
    cout << "! " << x << endl;
}

constexpr int B = 71;

constexpr int N = 5008;
vector<int> E[N];
int p[N], h[N];

void dfs(int u) {
    for (auto v : E[u]) {
        if (v == p[u]) continue;
        p[v] = u;
        dfs(v);
        h[u] = max(h[u], h[v] + 1);
    }
}

int find(int u) {
    vector<int> a;
    for (auto& v : E[u]) {
        if (v == p[u] || h[v] < B) continue;
        a.push_back(v);
    }
    if (a.empty()) {
        return u;
    }
    for (auto& v : a) {
        if (v == a.back() || query(v) == 1) {
            return find(v);
        }
    }
}

void eachT() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; ++i) {
        E[i].clear();
        p[i] = 0;
        h[i] = 0;
    }

    for (int i = 2; i <= n; ++i) {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    dfs(1);

    for (int u = 1; u <= n; ++u) {
        if (h[u] == 0) {  // u 是叶子 
            for (int i = 0; i < B; ++i) {
                if (query(u) == 1) {
                    answer(u);
                    return;
                }
            }
            break;
        }
    }

    vector<int> a;
    for (int u = find(1); u != 0; u = p[u]) {
        a.push_back(u);
    }
    reverse(a.begin(), a.end());

    int l = 0, r = a.size() - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (query(a[mid]) == 1) {
            l = mid;
        }
        else {
            r = mid - 1;
            l = max(0, l - 1);
            r = max(0, r - 1);
        }
    }

    answer(a[l]);
}

CF1934C. Find a Mine (1700)

$n$ 行$m$ 列网格，有两个格子中有地雷。每次询问给定交互机两个正整数$x,y$，然后交互机返回所有地雷距离这个位置最小的曼哈顿距离。

$4$ 次询问内找出两个地雷中的一个。

struct Point {
    int x, y;
};

int query(int x, int y) {
    cout << "? " << x << " " << y << endl;

    int d;
    cin >> d;
    return d;
}

void answer(int x, int y) {
    cout << "! " << x << " " << y << endl;
}

void eachT() {
    int n, m;
    cin >> n >> m;

    int d = query(1, 1);

    Point p1, p2;
    if (d < n) p1 = { d + 1, 1 };
    else p1 = { n, 2 + d - n };
    if (d < m) p2 = { 1, d + 1 };
    else p2 = { 2 + d - m, m };

    int d1 = query(p1.x, p1.y), d2 = query(p2.x, p2.y);
    if (d1 & 1) {
        answer(p2.x + d2 / 2, p2.y - d2 / 2);
    }
    else if (d2 & 1) {
        answer(p1.x - d1 / 2, p1.y + d1 / 2);
    }
    else {
        int d3 = query(p1.x - d1 / 2, p1.y + d1 / 2);
        if (d3 == 0) {
            answer(p1.x - d1 / 2, p1.y + d1 / 2);
        }
        else {
            answer(p2.x + d2 / 2, p2.y - d2 / 2);
        }
    }
}

CF1999G2. Ruler (1700)

有一把有$1001$ 个刻度（$1 \sim 1001$）的丢失了一个刻度$x$（$2 \le x \le 999$）尺子，刻度分别为。当你用尺子量一个长度为$y$ 的物体时，尺子量出的结果为：

• 若$y < x$，尺子将会量出正确的结果$y$。
• 否则，尺子将会量出错误的结果$y + 1$。

你需要找出丢失的刻度$x$。你可以每次提供两个$1$ 至$1000$ 内的整数$a,b$，你将会收到尺子量出的$a$ 的长度与尺子量出的$b$ 的长度之积。

最多$7$ 次询问。

void eachT() {
    int l = 2, r = 999;
    while (l < r) {
        int lt = l + (r - l) / 3, rt = l + (r - l) * 2 / 3;
        int a = lt, b = rt;

        cout << "? " << a << ' ' << b << endl;

        int x;
        cin >> x;
        if (x == a * b) {
            l = rt + 1;
        }
        else if (x == (a + 1) * (b + 1)) {
            r = lt;
        }
        else {
            l = lt + 1;
            r = rt;
        }
    }

    cout << "! " << l << endl;
}