P14319 「ALFR Round 11」C1 开关灯 (switch) (ez ver.)

解题思路

先对整个区间 $[1,n]$ 进行操作 $1$（翻转）和操作 $2$（查询），此时分为两种情况：

1. 所有灯全亮。
2. 只有 $1$ 个灯不亮；

对于第一种情况，再次进行全局翻转。

由于坏灯不会连续两次翻转，必定只有 $1$ 个灯亮，这样就转换为类似第二种情况。

此时有且仅有 $1$ 个灯亮或不亮，通过二分查询即可定位。

最多需要 $3+\lceil\log_2 500\rceil=3+9=12$ 次操作。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		cout<<1<<' '<<1<<' '<<n<<endl;
		cout<<2<<' '<<1<<' '<<n<<endl;
		int k;
		cin>>k;
		if(k==n)cout<<1<<' '<<1<<' '<<n<<endl;
		int l=1,r=n;
		while(l<r)
		{
			int mid=l+r>>1;
			cout<<2<<' '<<l<<' '<<mid<<endl;
			int t;
			cin>>t;
			if(k==n?t>0:t<mid-l+1)r=mid;
			else l=mid+1;
		}
		cout<<3<<' '<<l<<endl;
	}
	return 0;
}