Codeforces Round #803 (Div. 2) D. Fixed Point Guessing

Problem - D - Codeforces (Unofficial mirror by Menci)

        第一次写交互题，没看题解一次过（赛后补题）

        题目大意：一个长度为 n 的数组包含 1~ n（ n 为奇数），选择 （ n - 1）/ 2 个元素对，交换他们的位置，问未被交换的元素是哪个

        方法：二分

        l = 0，r = n，mid = （ l + r ）/2；

        _includes = （l ，r）中在范围外的数量

•         左段长度为奇数

1. 假设该元素在内，_includes为偶数（可能为0）
2. 不在该段内，_includes为奇数

•         左段长度为偶数

1. 假设该元素在内，_includes为奇数
2. 不在该段内，_includes为偶数（可能为0）

这样我们就很容易用二分写出来了

        

代码实现 

#include
#define debug0(x) cout << "debug0: " << x << endl
#define fr(t, i, n) for (int i = t; i < n; i++)
#define first fi
#define second se
using namespace std;

typedef long long LL;
typedef pair PII;


const int N = 1e4+10;
int a[N];
void solve(){
	int n;cin >> n;
    int l = 1,r = n;
    while(l < r){
        int mid = (l+r) >> 1;
        cout << "?" << " " << l << " " << mid << endl;//询问

        int includes = 0; 
        for(int i = 0;i < mid-l+1;i ++){
            cin >> a[i];
            if(a[i] >= l && a[i] <= mid)includes++;    //计算_includes
        }
        int _includes = mid-l+1 - includes;

        if((mid-l+1) % 2){                             //判断二分
            if(_includes % 2 == 0)r = mid;
            else l = mid +1;
        }else{
            if(_includes % 2 == 0)l = mid +1;
            else r = mid;
        }
    }
    cout << "!" << " " << l << endl;
}

int main()
{
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;cin >> T;
	
	while(T--){
		solve();
	}
	return 0;
}