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

解题思路

先对整个区间

[1,n]

进行操作

1

（翻转）和操作

2

（查询），此时分为两种情况：

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

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

由于坏灯不会连续两次翻转，必定只有

1

个灯亮，这样就转换为类似第二种情况。

此时有且仅有

1

个灯亮或不亮，通过二分查询即可定位。

最多需要

3+\lceil\log_2 500\rceil=3+9=12

次操作。

参考代码

CPP

#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;
}

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

文章操作

解题思路

参考代码

相关推荐

评论

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