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

lailai0916 · 2025-11-19 14:53:08 · 题解

解题思路

先对整个区间 [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;
}