题意

有个长度为n的排列p，[0,1,2,...n-1]，你可以进行至多2*n次询问，每次询问两个i，j，返回gcd(pi,pj)，让你在规定时间内猜出0在哪两个位置之一

思路

这是一道交互题，询问的上限是2n次

通过三个数，可以去除掉一个不是0的数

对三个数进行以下询问，gcd(a,i),gcd(b,i)

如果gcd(a,i) != gcd(b,i)，那么其中a，b小的被i取代，因为a，b中假如有0，那么一定是大的数，那么小的数一定不是0

如果gcd(a,i) == gcd(b,i)，那么跳过i，因为假如i是0，因为数列每个数都不同，所必不可能相等

那么for一遍数组，每次和当前位置i进行两次询问，最多2n的限制内就可以筛选出0可能存在的位置p，q

代码

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 2e4 + 10;

int n, t = 1;

long long a[N], b[N];

int pw[N];

int l[N], cnt[N];

const int mod = 998244353;

map<int, int> mp;

int v[N];

int ask(int x, int y) {

    cout << "? " << x << ' ' << y << endl;

    int u;

    cin >> u;

    return u;

}

void ok(int x, int y) {

    cout << "! " << x << ' ' << y << endl;

    int u;

    cin >> u;

}

void run() {

    cin >> n;

    int p = 1, q = 2;

    for (int i = 3; i <= n; i++) {

        int r1 = ask(p, i), r2 = ask(q, i);

        if (r1 < r2) {

            p = i;

        }

        if (r1 > r2) {

            q = i;

        }

    }

    ok(q, p);

}

int main() {

    srand(time(0));

    cin >> t;

    while (t--)

        run();

    return 0;

}

巴特西

Codeforces Round #838 (Div. 2) D. GCD Queries

题意

思路

代码

最新文章

热门文章