題意
有個長度為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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/540140.html
標籤：其他