显然，可以将全体开关都朝上，来确定控制第一个门的按钮的哪个状态是正确的。确定控制第一个门的是哪个开关，可以使用二分查找，确定之后将次开关始终处于打开状态，防止干扰接下来的操作。递归确定每个门的信息。总操作次数为\(n+log_{2}^{n}n \approx 70000\)，足以通过。
点击查看代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=4e5+100;
extern "C" int tryCombination(int S[]);
extern "C" void answer(int S[], int D[]);
int ans[N],mp[N],opt[N];
extern "C" void exploreCave(int n)
{for(int i=0;i<n;++i)opt[i]=ans[i]=-1;for(int i=0;i<n;++i){int sta=0;for(int j=0;j<n;++j)opt[j]=(ans[j]==-1?0:ans[j]); int x=tryCombination(opt);if(x==i)sta=1;else sta=0;int l=0,r=n-1;while(l<=r){int mid=l+r>>1;for(int j=0;j<=mid;++j)opt[j]=(ans[j]==-1?sta:ans[j]);for(int j=mid+1;j<n;++j)opt[j]=(ans[j]==-1?sta^1:ans[j]);int x=tryCombination(opt);if(x==i)l=mid+1;else r=mid-1;}mp[r+1]=i;ans[r+1]=sta;}answer(ans,mp);
}