CFdiv2-Fixed Point Guessing-(區間答案二分)

D

題意：
就是給你一個1到n的數組，但是其中進行了n+1/2次交換，每個數只會被交換一次，所以只有一個數沒有交換過。然後你可以查詢15次，每次查詢一個區間，會返回給你這個區間的數從小到大排列後是什麼。現在問你哪一個數沒有被交換。

思考：
剛開始看到15次就知道是二分，但是以為是dfs二分，每次遞歸判斷。但是我感覺又不太好寫。其實呢，對於二分，可以二分答案在哪個區間。也就是先判斷l到r，如果答案在這裏面，r = mid。否則l = mid+1。也就是在另一個區間。這就是單純的判斷在哪個區間，並沒有答案越好越差啥的。但是怎麼判呢，其實對於，輸入的數x，如果x在l到r裏面，那麼意味著他是給這裏面的換的，那麼這裏面的數就會出現兩次，否則就是0次。但是哪個沒有交換的數會貢獻一次，所以如果是奇數，那麼答案就是這個區間。

代碼：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];

int check(int l,int r)
{
    
	cout<<"? "<<l<<" "<<r<<"\n";
	cout.flush();
	int sum = 0;
	for(int i=l;i<=r;i++)
	{
    
		int x;
		cin>>x;
		if(x>=l&&x<=r) sum++;
	}
	return sum;
}

signed main()
{
    
	cin>>T;
	while(T--)
	{
    
		cin>>n;
		int l = 1,r = n;
		while(l<r)
		{
    
			int mid = (l+r)/2;
			if(check(l,mid)&1) r = mid;
			else l = mid+1;
		}
		cout<<"! "<<l<<"\n";
	}
	return 0;
}

總結：
多多思考，積累經驗。