2022.8.6 颓废记录()-其他

2022.8.6 颓废记录()

[CF912D]Fishes

$$1\le r \le n,m\le 10^5,1\le k \le \min(n\times m,10^5)$$。

$$1\le r \le n,m\le 10^5,1\le k \le \min(n\times m,10^5)$$。

（也不知道为啥我会在 $$\texttt{graph}$$ 题单里看到这题 /yiw）

std::unordered_map
// Problem: CF912D Fishes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF912D
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,r,k;
int a[maxn],b[maxn];
struct node {
int x,y;
node() {
x = y = 0;
}
node(int x,int y):x(x),y(y){}
bool operator < (const node& p)const {
return 1ll * a[x] * b[y] < 1ll * a[p.x] * b[p.y];
}
};
priority_queue<node> q;
unordered_map<int,bool> vis[maxn];
int main() {
scanf("%d %d %d %d",&n,&m,&r,&k);
for(int i = 1;i <= n - r + 1;++ i)++ a[i],-- a[i + r];
for(int i = 1;i <= m - r + 1;++ i)++ b[i],-- b[i + r];
for(int i = 1;i <= n;++ i)a[i] += a[i - 1];
for(int i = 1;i <= m;++ i)b[i] += b[i - 1];
sort(a + 1 , a + 1 + n , greater<int>());
sort(b + 1 , b + 1 + m , greater<int>());
q.emplace(1 , 1);
vis[1][1] = true;
long long ans = 0;
while(k --) {
auto [x , y] = q.top();
q.pop();
ans += 1ll * a[x] * b[y];
if(x < n&&vis[x + 1].find(y) == vis[x + 1].end()) {
vis[x + 1][y] = true;
q.emplace(x + 1 , y);
}
if(y < m&&vis[x].find(y + 1) == vis[x].end()) {
vis[x][y + 1] = true;
q.emplace(x , y + 1);
}
}
printf("%.10lf\n",(double)(1.0 * (double)ans) / (double)(1.0 * (double)(n - r + 1) * (double)(m - r + 1)));
return 0;
}


while
auto& [x,y]=q.top()
q.pop()

[CF1056E]Check Transcription

$$2\le |t|\le 10^5,1\le |s|\le 10^6$$。

$$2\le |t|\le 10^5,1\le |s|\le 10^6$$。

SA
SA

（我并没有直接去枚举那个出现次数较多的，这样虽然时间复杂度不标准但也能过）

Wrong Answer on test#17

int
long long
unsigned long long

Code

// Problem: CF1056E Check Transcription
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1056E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int maxm = 1e5 + 5;
const ll p = 13331;
const ll mod = 1e9 + 7;
char t[maxn],s[maxn];
unsigned long long Hash[maxn],pw[maxn];
int n,m;
int main() {
scanf("%s %s",t + 1,s + 1);
m = strlen(t + 1);
n = strlen(s + 1);
pw[0] = 1;
Hash[0] = 0;
for(int i = 1;i <= n;++ i) {
pw[i] = pw[i - 1] * p % mod;
(Hash[i] = Hash[i - 1] * p % mod + s[i]) % mod;
}
int ans = 0;
int cnt1 = 0,cnt2 = 0;
for(int i = 1;i <= m;++ i)cnt1 += t[i] == '0',cnt2 += t[i] == '1';
for(int len1 = 1;len1 <= (n - cnt2) / cnt1;++ len1) {
int len2 = (n - cnt1 * len1) / cnt2;
if(len1 * cnt1 + len2 * cnt2 != n)continue ;
int cur = 0,st1 = 0,st2 = 0;
bool flag = true,flag1 = false,flag2 = false;
for(int i = 1;i <= m;++ i) {
if(!flag)break ;
if(t[i] == '0') {
if(flag1)flag &= ((Hash[cur + len1] - Hash[cur] * pw[len1] % mod + mod) % mod == (Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod);
else st1 = cur,flag1 = true;
cur += len1;
}
else {
if(flag2)flag &= ((Hash[cur + len2] - Hash[cur] * pw[len2] % mod + mod) % mod == (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
else st2 = cur,flag2 = true;
cur += len2;
}
if(flag1&&flag2)flag &= ((Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod != (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
}
ans += flag;
}
printf("%d",ans);
return 0;
}


[CF1093G]Multidimensional Queries

$$n$$ 个 $$k$$ 维的点 $$a_1\ldots a_n$$，两点 $$(x_1,x_2,\ldots,x_k),(y_1,y_2,\ldots,y_k)$$间的曼哈顿距离为 $$\sum\limits_{i=1}^k |x_i-y_i|$$。
$$Q$$ 次操作，操作分两种：

$$1\ i \ b_1\ b_2,\ldots,b_k$$，表示将 $$a_i$$ 修改为 $$(b_1,b_2,\ldots,b_k)$$ 。

$$2\ l\ r$$，表示询问 $$[l,r]$$ 内最大的两点间曼哈顿距离。

$$1 \le n,Q \le 2\times 10^5,1\le k\le 5$$。

$$n$$ 个 $$k$$ 维的点 $$a_1\ldots a_n$$，两点 $$(x_1,x_2,\ldots,x_k),(y_1,y_2,\ldots,y_k)$$间的曼哈顿距离为 $$\sum\limits_{i=1}^k |x_i-y_i|$$。

$$Q$$ 次操作，操作分两种：

• $$1\ i \ b_1\ b_2,\ldots,b_k$$，表示将 $$a_i$$ 修改为 $$(b_1,b_2,\ldots,b_k)$$ 。
• $$2\ l\ r$$，表示询问 $$[l,r]$$ 内最大的两点间曼哈顿距离。

$$1 \le n,Q \le 2\times 10^5,1\le k\le 5$$。

Code

// Problem: CF1093G Multidimensional Queries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1093G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxk = 5;
int n,k,x;
int a[maxn][maxk];
int b[maxk];
struct Segment_Tree {
int ls[maxn << 2],rs[maxn << 2],sum[maxn << 2];
void pushup(int i) {
sum[i] = max(sum[i << 1] , sum[i << 1 | 1]);
return ;
}
void build(int i,int l,int r) {
ls[i] = l;
rs[i] = r;
sum[i] = -1e9;
if(l == r) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? a[l][j] : -a[l][j];
return ;
}
int mid = l + r >> 1;
build(i << 1 , l , mid);
build(i << 1 | 1 , mid + 1 , r);
pushup(i);
return ;
}
void modify(int i,int pos) {
if(ls[i] == rs[i]) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? b[j] : -b[j];
return ;
}
int mid = ls[i] + rs[i] >> 1;
if(pos <= mid)modify(i << 1 , pos);
else modify(i << 1 | 1 , pos);
pushup(i);
return ;
}
int query(int i,int l,int r) {
if(ls[i] >= l&&rs[i] <= r) {
return sum[i];
}
if(ls[i] > r||rs[i] < l)return -1e9;
int mid = ls[i] + rs[i] >> 1,s = -1e9;
if(l <= mid)s = max(s , query(i << 1 , l , r));
if(r > mid)s = max(s , query(i << 1 | 1 , l , r));
return s;
}
}tr[32];
int main() {
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;++ i)
for(int j = 0;j < k;++ j)scanf("%d",&a[i][j]);
for(x = 0;x < (1 << k);++ x)tr[x].build(1 , 1 , n);
int Q;
scanf("%d",&Q);
int S = (1 << k) - 1;
while(Q --) {
int op,i,l,r;
scanf("%d",&op);
if(op & 1) {
scanf("%d",&i);
for(int j = 0;j < k;++ j)scanf("%d",&b[j]);
for(x = 0;x < (1 << k);++ x)tr[x].modify(1 , i);
}
else {
scanf("%d %d",&l,&r);
int ans = -1e9;
for(x = 0;x < (1 << (k - 1));++ x)ans = max(ans , tr[x].query(1 , l , r) + tr[S ^ x].query(1 , l , r));
printf("%d\n",ans);
}
}
return 0;
}


upd：晚上交互题居然做出来了，可惜一开始脑抽，复杂度实现错了，不然排名能高好多的 QAQ。

[CF1713D]Tournament Countdown

（注：写题解时 system test 还未进行，如果 fst 了就看个乐吧 qwq）

$$2^n$$ 个人打淘汰赛。$$1$$ 号和 $$2$$ 号打，$$3$$ 号和 $$4$$ 号打，依次类推。

，表示询问 $$a$$ 号和 $$b$$ 号胜利次数的关系。$$1$$ 表示 $$a$$ 赢的次数比 $$b$$ 多，$$2$$ 表示 $$a$$ 赢的次数比 $$b$$ 少，$$0$$ 表示 $$a,b$$ 胜利次数相同。

$$1\le n\le 17$$。

$$2^n$$ 个人打淘汰赛。$$1$$ 号和 $$2$$ 号打，$$3$$ 号和 $$4$$ 号打，依次类推。

• ? a b，表示询问 $$a$$ 号和 $$b$$ 号胜利次数的关系。$$1$$ 表示 $$a$$ 赢的次数比 $$b$$ 多，$$2$$ 表示 $$a$$ 赢的次数比 $$b$$ 少，$$0$$ 表示 $$a,b$$ 胜利次数相同。

$$1\le n\le 17$$。

• 结果为 $$1$$：也就是 $$c_1\gt c_3= 0$$，说明 $$c_1 = 1$$，也就是说 $$1$$ 和 $$2$$ 的比赛中 $$1$$ 一定胜利了，否则 $$c_1$$ 不可能为 $$1$$。那 $$2$$ 就没有询问的必要了，直接询问下 $$1\ 4$$ 即可。
• 结果为 $$2$$：和上面类似。
• 结果为 $$0$$：即 $$c_1=c_3=0$$，那就可以推出来 $$c_2=c_4=1$$，询问 $$2\ 4$$ 即可。

• 首先特判 $$n=1$$ 的情况，直接用一次询问得出答案。
• 若 $$n \gt 1$$，就把 $$2^n$$ 拆成 $$2^{n-2}$$ 个 $$4$$ 人小组，用我们上面的算法判断，得出 $$2^{n-2}$$ 个胜者，再递归到 $$n-2$$ 的情况求解。

（老觉得这个东西很怪，可能有问题，请大佬们帮忙看看 QAQ）

Code

// Problem: D. Tournament Countdown
// Contest: Codeforces - Codeforces Round #812 (Div. 2)
// URL: https://codeforces.com/contest/1713/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define Chtholly set<node>::iterator
#define SET set<int>::iterator
#define VEC vector<int>::iterator
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 5e5 + 5;
const int maxm = 3e6 + 5;
const int maxk = 30;
const ll mod = 1e9 + 7;
const int INF = 1e9;
const ll INFll = 1e16;
int n;
std::vector<int> s;
int ask(int a,int b) {
int p;
printf("? %d %d\n",a,b);
fflush(stdout);
scanf("%d",&p);
return p;
}
void solve(int n) {
if(n <= 1) {
printf("! %d\n",ask(s[0] , s[1]) == 1 ? s[0] : s[1]);
fflush(stdout);
return ;
}
else if(n == 2) {
int p = ask(s[0] , s[3]);
if(p == 1) {
printf("! %d\n",ask(s[0] , s[2]) == 1 ? s[0] : s[2]);
fflush(stdout);
}
else if(p == 2) {
printf("! %d\n",ask(s[1] , s[3]) == 1 ? s[1] : s[3]);
fflush(stdout);
}
else {
printf("! %d\n",ask(s[1] , s[2]) == 1 ? s[1] : s[2]);
fflush(stdout);
}
return ;
}
vector<int> G;
for(int i = 0;i < (1 << n);i += 4) {
int p = ask(s[i] , s[i + 2]);
if(p == 1) {
G.pb(ask(s[i] , s[i + 3]) == 1 ? s[i] : s[i + 3]);
}
else if(p == 2) {
G.pb(ask(s[i + 2] , s[i + 1]) == 1 ? s[i + 2] : s[i + 1]);
}
else {
G.pb(ask(s[i + 1] , s[i + 3]) == 1 ? s[i + 1] : s[i + 3]);
}
}
s = G;
solve(n - 2);
return ;
}
void work() {
scanf("%d",&n);
s.clear();
for(int i = 1;i <= (1 << n);++ i)s.pb(i);
solve(n);
return ;
}
int main() {
int T;
scanf("%d",&T);
while(T --)work();
return 0;
}

————————

[CF912D]Fishes

$$1\le r \le n,m\le 10^5,1\le k \le \min(n\times m,10^5)$$。

$$1\le r \le n,m\le 10^5,1\le k \le \min(n\times m,10^5)$$。

（也不知道为啥我会在 $$\texttt{graph}$$ 题单里看到这题 /yiw）

std::unordered_map
// Problem: CF912D Fishes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF912D
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,r,k;
int a[maxn],b[maxn];
struct node {
int x,y;
node() {
x = y = 0;
}
node(int x,int y):x(x),y(y){}
bool operator < (const node& p)const {
return 1ll * a[x] * b[y] < 1ll * a[p.x] * b[p.y];
}
};
priority_queue<node> q;
unordered_map<int,bool> vis[maxn];
int main() {
scanf("%d %d %d %d",&n,&m,&r,&k);
for(int i = 1;i <= n - r + 1;++ i)++ a[i],-- a[i + r];
for(int i = 1;i <= m - r + 1;++ i)++ b[i],-- b[i + r];
for(int i = 1;i <= n;++ i)a[i] += a[i - 1];
for(int i = 1;i <= m;++ i)b[i] += b[i - 1];
sort(a + 1 , a + 1 + n , greater<int>());
sort(b + 1 , b + 1 + m , greater<int>());
q.emplace(1 , 1);
vis[1][1] = true;
long long ans = 0;
while(k --) {
auto [x , y] = q.top();
q.pop();
ans += 1ll * a[x] * b[y];
if(x < n&&vis[x + 1].find(y) == vis[x + 1].end()) {
vis[x + 1][y] = true;
q.emplace(x + 1 , y);
}
if(y < m&&vis[x].find(y + 1) == vis[x].end()) {
vis[x][y + 1] = true;
q.emplace(x , y + 1);
}
}
printf("%.10lf\n",(double)(1.0 * (double)ans) / (double)(1.0 * (double)(n - r + 1) * (double)(m - r + 1)));
return 0;
}


while
auto& [x,y]=q.top()
q.pop()

[CF1056E]Check Transcription

$$2\le |t|\le 10^5,1\le |s|\le 10^6$$。

$$2\le |t|\le 10^5,1\le |s|\le 10^6$$。

SA
SA

（我并没有直接去枚举那个出现次数较多的，这样虽然时间复杂度不标准但也能过）

Wrong Answer on test#17

int
long long
unsigned long long

Code

// Problem: CF1056E Check Transcription
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1056E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int maxm = 1e5 + 5;
const ll p = 13331;
const ll mod = 1e9 + 7;
char t[maxn],s[maxn];
unsigned long long Hash[maxn],pw[maxn];
int n,m;
int main() {
scanf("%s %s",t + 1,s + 1);
m = strlen(t + 1);
n = strlen(s + 1);
pw[0] = 1;
Hash[0] = 0;
for(int i = 1;i <= n;++ i) {
pw[i] = pw[i - 1] * p % mod;
(Hash[i] = Hash[i - 1] * p % mod + s[i]) % mod;
}
int ans = 0;
int cnt1 = 0,cnt2 = 0;
for(int i = 1;i <= m;++ i)cnt1 += t[i] == '0',cnt2 += t[i] == '1';
for(int len1 = 1;len1 <= (n - cnt2) / cnt1;++ len1) {
int len2 = (n - cnt1 * len1) / cnt2;
if(len1 * cnt1 + len2 * cnt2 != n)continue ;
int cur = 0,st1 = 0,st2 = 0;
bool flag = true,flag1 = false,flag2 = false;
for(int i = 1;i <= m;++ i) {
if(!flag)break ;
if(t[i] == '0') {
if(flag1)flag &= ((Hash[cur + len1] - Hash[cur] * pw[len1] % mod + mod) % mod == (Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod);
else st1 = cur,flag1 = true;
cur += len1;
}
else {
if(flag2)flag &= ((Hash[cur + len2] - Hash[cur] * pw[len2] % mod + mod) % mod == (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
else st2 = cur,flag2 = true;
cur += len2;
}
if(flag1&&flag2)flag &= ((Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod != (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
}
ans += flag;
}
printf("%d",ans);
return 0;
}


[CF1093G]Multidimensional Queries

$$n$$ 个 $$k$$ 维的点 $$a_1\ldots a_n$$，两点 $$(x_1,x_2,\ldots,x_k),(y_1,y_2,\ldots,y_k)$$间的曼哈顿距离为 $$\sum\limits_{i=1}^k |x_i-y_i|$$。
$$Q$$ 次操作，操作分两种：

$$1\ i \ b_1\ b_2,\ldots,b_k$$，表示将 $$a_i$$ 修改为 $$(b_1,b_2,\ldots,b_k)$$ 。

$$2\ l\ r$$，表示询问 $$[l,r]$$ 内最大的两点间曼哈顿距离。

$$1 \le n,Q \le 2\times 10^5,1\le k\le 5$$。

$$n$$ 个 $$k$$ 维的点 $$a_1\ldots a_n$$，两点 $$(x_1,x_2,\ldots,x_k),(y_1,y_2,\ldots,y_k)$$间的曼哈顿距离为 $$\sum\limits_{i=1}^k |x_i-y_i|$$。

$$Q$$ 次操作，操作分两种：

• $$1\ i \ b_1\ b_2,\ldots,b_k$$，表示将 $$a_i$$ 修改为 $$(b_1,b_2,\ldots,b_k)$$ 。
• $$2\ l\ r$$，表示询问 $$[l,r]$$ 内最大的两点间曼哈顿距离。

$$1 \le n,Q \le 2\times 10^5,1\le k\le 5$$。

Code

// Problem: CF1093G Multidimensional Queries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1093G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxk = 5;
int n,k,x;
int a[maxn][maxk];
int b[maxk];
struct Segment_Tree {
int ls[maxn << 2],rs[maxn << 2],sum[maxn << 2];
void pushup(int i) {
sum[i] = max(sum[i << 1] , sum[i << 1 | 1]);
return ;
}
void build(int i,int l,int r) {
ls[i] = l;
rs[i] = r;
sum[i] = -1e9;
if(l == r) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? a[l][j] : -a[l][j];
return ;
}
int mid = l + r >> 1;
build(i << 1 , l , mid);
build(i << 1 | 1 , mid + 1 , r);
pushup(i);
return ;
}
void modify(int i,int pos) {
if(ls[i] == rs[i]) {
sum[i] = 0;
for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? b[j] : -b[j];
return ;
}
int mid = ls[i] + rs[i] >> 1;
if(pos <= mid)modify(i << 1 , pos);
else modify(i << 1 | 1 , pos);
pushup(i);
return ;
}
int query(int i,int l,int r) {
if(ls[i] >= l&&rs[i] <= r) {
return sum[i];
}
if(ls[i] > r||rs[i] < l)return -1e9;
int mid = ls[i] + rs[i] >> 1,s = -1e9;
if(l <= mid)s = max(s , query(i << 1 , l , r));
if(r > mid)s = max(s , query(i << 1 | 1 , l , r));
return s;
}
}tr[32];
int main() {
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;++ i)
for(int j = 0;j < k;++ j)scanf("%d",&a[i][j]);
for(x = 0;x < (1 << k);++ x)tr[x].build(1 , 1 , n);
int Q;
scanf("%d",&Q);
int S = (1 << k) - 1;
while(Q --) {
int op,i,l,r;
scanf("%d",&op);
if(op & 1) {
scanf("%d",&i);
for(int j = 0;j < k;++ j)scanf("%d",&b[j]);
for(x = 0;x < (1 << k);++ x)tr[x].modify(1 , i);
}
else {
scanf("%d %d",&l,&r);
int ans = -1e9;
for(x = 0;x < (1 << (k - 1));++ x)ans = max(ans , tr[x].query(1 , l , r) + tr[S ^ x].query(1 , l , r));
printf("%d\n",ans);
}
}
return 0;
}


upd：晚上交互题居然做出来了，可惜一开始脑抽，复杂度实现错了，不然排名能高好多的 QAQ。

[CF1713D]Tournament Countdown

（注：写题解时 system test 还未进行，如果 fst 了就看个乐吧 qwq）

$$2^n$$ 个人打淘汰赛。$$1$$ 号和 $$2$$ 号打，$$3$$ 号和 $$4$$ 号打，依次类推。

，表示询问 $$a$$ 号和 $$b$$ 号胜利次数的关系。$$1$$ 表示 $$a$$ 赢的次数比 $$b$$ 多，$$2$$ 表示 $$a$$ 赢的次数比 $$b$$ 少，$$0$$ 表示 $$a,b$$ 胜利次数相同。

$$1\le n\le 17$$。

$$2^n$$ 个人打淘汰赛。$$1$$ 号和 $$2$$ 号打，$$3$$ 号和 $$4$$ 号打，依次类推。

• ? a b，表示询问 $$a$$ 号和 $$b$$ 号胜利次数的关系。$$1$$ 表示 $$a$$ 赢的次数比 $$b$$ 多，$$2$$ 表示 $$a$$ 赢的次数比 $$b$$ 少，$$0$$ 表示 $$a,b$$ 胜利次数相同。

$$1\le n\le 17$$。

• 结果为 $$1$$：也就是 $$c_1\gt c_3= 0$$，说明 $$c_1 = 1$$，也就是说 $$1$$ 和 $$2$$ 的比赛中 $$1$$ 一定胜利了，否则 $$c_1$$ 不可能为 $$1$$。那 $$2$$ 就没有询问的必要了，直接询问下 $$1\ 4$$ 即可。
• 结果为 $$2$$：和上面类似。
• 结果为 $$0$$：即 $$c_1=c_3=0$$，那就可以推出来 $$c_2=c_4=1$$，询问 $$2\ 4$$ 即可。

• 首先特判 $$n=1$$ 的情况，直接用一次询问得出答案。
• 若 $$n \gt 1$$，就把 $$2^n$$ 拆成 $$2^{n-2}$$ 个 $$4$$ 人小组，用我们上面的算法判断，得出 $$2^{n-2}$$ 个胜者，再递归到 $$n-2$$ 的情况求解。

（老觉得这个东西很怪，可能有问题，请大佬们帮忙看看 QAQ）

Code

// Problem: D. Tournament Countdown
// Contest: Codeforces - Codeforces Round #812 (Div. 2)
// URL: https://codeforces.com/contest/1713/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define Chtholly set<node>::iterator
#define SET set<int>::iterator
#define VEC vector<int>::iterator
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 5e5 + 5;
const int maxm = 3e6 + 5;
const int maxk = 30;
const ll mod = 1e9 + 7;
const int INF = 1e9;
const ll INFll = 1e16;
int n;
std::vector<int> s;
int ask(int a,int b) {
int p;
printf("? %d %d\n",a,b);
fflush(stdout);
scanf("%d",&p);
return p;
}
void solve(int n) {
if(n <= 1) {
printf("! %d\n",ask(s[0] , s[1]) == 1 ? s[0] : s[1]);
fflush(stdout);
return ;
}
else if(n == 2) {
int p = ask(s[0] , s[3]);
if(p == 1) {
printf("! %d\n",ask(s[0] , s[2]) == 1 ? s[0] : s[2]);
fflush(stdout);
}
else if(p == 2) {
printf("! %d\n",ask(s[1] , s[3]) == 1 ? s[1] : s[3]);
fflush(stdout);
}
else {
printf("! %d\n",ask(s[1] , s[2]) == 1 ? s[1] : s[2]);
fflush(stdout);
}
return ;
}
vector<int> G;
for(int i = 0;i < (1 << n);i += 4) {
int p = ask(s[i] , s[i + 2]);
if(p == 1) {
G.pb(ask(s[i] , s[i + 3]) == 1 ? s[i] : s[i + 3]);
}
else if(p == 2) {
G.pb(ask(s[i + 2] , s[i + 1]) == 1 ? s[i + 2] : s[i + 1]);
}
else {
G.pb(ask(s[i + 1] , s[i + 3]) == 1 ? s[i + 1] : s[i + 3]);
}
}
s = G;
solve(n - 2);
return ;
}
void work() {
scanf("%d",&n);
s.clear();
for(int i = 1;i <= (1 << n);++ i)s.pb(i);
solve(n);
return ;
}
int main() {
int T;
scanf("%d",&T);
while(T --)work();
return 0;
}