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

· · 题解

题目链接。

解题思路

可以先输出一个 1 1 n，再查询 2 1 n。

这个时候有两种情况：

:::info[结果为 n]

说明这次坏的灯泡反转了，可以可以再输出一个 1 1 n。

这样就可以让那个坏的灯泡不变，其他的灯泡重新变回暗。

二分找的唯一一个亮着的灯即可。

共执行 3+\log_2500=12 次。

:::

:::info[结果为 n-1]

说明坏的灯泡没变。

二分寻找唯一一个暗着的灯即可。

共执行 2+\log_2500=11 次。

:::

代码

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
int n,la,tot;
void solve(){
    cin>>n;
    cout<<"1 1 "<<n<<endl;
    cout<<"2 1 "<<n<<endl;
    cin>>la;
    if(la==n) cout<<"1 1 "<<n<<endl;
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        cout<<"2 "<<mid+1<<' '<<r<<endl;
        cin>>tot;
        if(la==n?!tot:tot==r-mid) r=mid;
        else l=mid+1;
    }
    cout<<"3 "<<l<<endl;
}
int t;
signed main(){
    cin>>t;
    while(t--) solve();
    return 0;
}

:::

:::warning[注意事项]

两种情况不太一样，一种是二分亮的灯泡，另一种是二分暗的灯泡。

所以注意判断。

:::