Codeforces Round #803 (Div. 2) D题题解

题目链接

题意

交互题

有一个数组A=[1,2,…,n]长度为n，n为奇数，选中(n-1/2)对不相邻数组元素进行交换，说明只有一个数组元素没有进行交换且其余元素2都交换过并只交换过一次，

接下来你可以进行询问询问格式为? l r

接下来会返还交换后数组 a[l]…a[r]的升序排序结果,你可以最多询问15次找到那个没有交换的数组元素

解析

首先一看数据范围再加上做这种交互的经验我就猜到了二分，然后既然要二分那就要找到二分的二段性，也就是把一个数组一分为二，那切割开的数组一定有一个性质是一个满足一个不满足的，这样才能去二分，那这里的二段性显然就是一边数组有一个元素没交换另一边数组元素都交换了的

找到二段性之后就去想怎么判断二分后一边又有一个元素没交换，一遍所有元素都交换了呢，这里可以自己去那纸笔自己模拟一下，我先说结论：

  1. 二分[l,r]，然后询问[l,mid]，然后看[l,mid]内有多少大小是在这个区间内的数的个数

  2. 如果是偶数则代表则代表不存在未交换数，则去判断[mid+1,r]的区间

  3. 如果是奇数就代表存在未交换数，那几继续二分[l,mid]的区间

首先要明白一个就是交换只存在同区间交换或者不同区间交换（这里的区间指的是二分后的两个区间），二分后的区间长度不是奇数就是偶数，那我们先分类讨论一下，我设X为该区间内有多少大小是在这个区间内的数的个数

偶数：因为只存在同区间交换或者不同区间交换，如果是同区间交换，那么X应该不变，也就是奇偶性不变，如果是不同区间交换，那么一个元素跟另一个区间元素交换的话，那原区间就肯定会剩一个数没法跟自己区间的数内部交换也只能跟另一个区间交换，所以X应该减2但是奇偶性不变所以还是偶数，如果是奇数则代表有一个元素没交换

奇数：更上面一样如果是内部交换则奇偶性不变，但是内部交换肯定会剩下一个数(因为区间个数是奇数)，如果他跟另一个区间交换，那么X就减1，那么X就是偶数，如果他不交换那就是奇数

综上所述结论正确

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
bool check(int l,int r){
	cout<<"? "<<l<<' '<<r<<endl;
	int cou=0,x;
	for(int i=l;i<=r;i++){
		cin>>x;
		if(x>=l&&x<=r) cou++;
	}
	if(cou&1) return true;
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		int l=1,r=n,mid;
		while(l<r){
			mid=(l+r)>>1;
			if(check(l,mid))r=mid;
			else l=mid+1;
		}
		cout<<"! "<<l<<endl;
	}
	return 0;
}