题解：P10850 [EGOI 2024] Light Bulbs / 灯泡安装

· · 题解

感谢 @Milmon 解答了我在实现上的一些疑惑。

思路

神仙狗屎题。

首先我们考虑最后选出的灯形如什么，其实一定是 n 个横着的灯或者 n 个竖着的灯。读者自证不难。

如果询问时有 cnt_1 行存在横着的灯，cnt_2 列存在竖着的灯，那么最后的返回值就是 n(cnt_1+cnt_2)-cnt_1\times cnt_2。

考虑一些随机化。

维护一个待确定的集合，此时想办法去确定这个集合里灯泡的方向。

再维护一个这些灯泡可能的状态集合（可以采用 bitset 记录），每次询问我们想尽量的缩减状态集合的大小。

在待确定的集合以及已经确定的灯泡中随机一些灯泡点亮，计算此方案在最劣时会剩下多少状态（即对每种询问的返回值计算有多少个状态会问出来这种返回值），然后取这个值最小的方案去询问。

询问过后将不符合返回值的状态删掉，此时可能会出现一些灯泡的方向确定。如果确定的是一个横向的灯泡这一行就没用了，删掉待确定集合中所有在这一行的点。是竖向的灯泡同理。

每次缩减完再加入一些点到待确定的集合中，使得状态集合的大小不超过一个阈值（大约为 1000）。

该算法在 N=100 时，平均每次可以排除大约 92\% 的情况，大约可以在 75 次以内得出答案。

代码

实现得比较烂，仅供参考。

#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(20101013);
const int N = 105,B = 1000,M = 400;
int n,ton[N*N];
bool ok[N][N],ok1[N],ok2[N];//是否被确定
bool ans[N][N];//横向还是纵向（1：横向，0：纵向）
bool vis[N][N],vis1[N],vis2[N];
bool out[N][N];
bool cmp(bitset<M> x,bitset<M> y)
{
    for(int i = 0;i<M;i++)
        if(x[i]<y[i]) return 1;
        else return 0;
    return 0;
}
inline void print()
{
    for(int i = 1;i<=n;i++,cout<<endl)
        for(int j = 1;j<=n;j++)
            cout<<out[i][j];
}
signed main()
{
    cin>>n;
    vector<int> v1,v2,s;//v1:未确定的行，v2：未确定的列 
    vector<pair<int,int>> s1;//当前去确定的位置
    vector<bitset<M>> s2;//当前可能的集合
    bitset<M> ts;
    s2.push_back(ts);
    while(1)
    {
        int cc = 0;
        for(int i = 1;i<=n;i++) cc+=ok1[i];
        if(cc==n)//每行都有已确定的横着的灯 
        {
            for(int i = 1;i<=n;i++)
                for(int j = 1;j<=n;j++)
                    out[i][j] = 0;
            for(int i = 1;i<=n;i++)
                for(int j = 1;j<=n;j++)
                    if(ok[i][j]&&ans[i][j]==1)
                    {
                        out[i][j] = 1;
                        break;
                    }
            cout<<"!"<<endl;
            print();
            return 0;
        }
        cc = 0;
        for(int i = 1;i<=n;i++) cc+=ok2[i];
        if(cc==n)//每列都有已确定的竖着的灯 
        {
            for(int i = 1;i<=n;i++)
                for(int j = 1;j<=n;j++)
                    out[i][j] = 0;
            for(int j = 1;j<=n;j++)
                for(int i = 1;i<=n;i++)
                    if(ok[i][j]&&ans[i][j]==0)
                    {
                        out[i][j] = 1;
                        break;
                    }
            cout<<"!"<<endl;
            print();
            return 0;
        }
        while(s2.size()*2<=B)//加入一些点 
        {
            vector<pair<int,int>> vec;
            for(int i = 1;i<=n;i++)
                for(int j = 1;j<=n;j++)
                    vis[i][j] = 0;
            for(auto _:s1) vis[_.first][_.second] = 1;
            for(int i = 1;i<=n;i++)
                for(int j = 1;j<=n;j++)
                {
                    if(ok[i][j]||ok1[i]||ok2[j]||vis[i][j]) continue;
                    vec.push_back({i,j});
                }
            if(!vec.size()) break;
            int now = s1.size(),tmp = s2.size();
            s1.push_back(vec[rnd()%vec.size()]);
            for(int i = 0;i<tmp;i++)
            {
                ts = s2[i],ts.set(now);
                s2.push_back(ts);
            }
        }
        int T = 35;
        int now = 2e9;
        vector<int> mn;
        while(T--)//随机点亮的方案 
        {
            int mx = 0;
            s.resize(s1.size()); 
            for(int i = 0;i<s1.size();i++) s[i] = rnd()%2;
            for(auto z2:s2)
            {
                for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
                for(int i = 0;i<s1.size();i++)
                    if(s[i])
                    {
                        if(z2[i]) vis1[s1[i].first] = 1;
                        else vis2[s1[i].second] = 1;
                    }
                int cnt1 = 0,cnt2 = 0;
                for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
                ton[n*(cnt1+cnt2)-cnt1*cnt2]++;
                mx = max(mx,ton[n*(cnt1+cnt2)-cnt1*cnt2]);
            }
            if(mx<now) mn = s,now = mx;
            for(auto z2:s2)
            {
                for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
                for(int i = 0;i<s1.size();i++)
                    if(s[i])
                    {
                        if(z2[i]) vis1[s1[i].first] = 1;
                        else vis2[s1[i].second] = 1;
                    }
                int cnt1 = 0,cnt2 = 0;
                for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
                ton[n*(cnt1+cnt2)-cnt1*cnt2] = 0;
            }
        }
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++) out[i][j] = 0;
        for(int i = 0;i<s1.size();i++)
            if(mn[i]) out[s1[i].first][s1[i].second] = 1;
        cout<<"?"<<endl;
        print();
        int res;cin>>res;
        auto tmp = s2;s2.clear();
        for(auto z2:tmp)//找出那些合法的方案 
        {
            for(int i = 1;i<=n;i++) vis1[i] = vis2[i] = 0;
            for(int i = 0;i<s1.size();i++)
                if(mn[i])
                {
                    if(z2[i]) vis1[s1[i].first] = 1;
                    else vis2[s1[i].second] = 1;
                }
            int cnt1 = 0,cnt2 = 0;
            for(int i = 1;i<=n;i++) cnt1+=vis1[i],cnt2+=vis2[i];
            if(n*(cnt1+cnt2)-cnt1*cnt2==res) s2.push_back(z2);
        }
        for(int i = 0;i<s1.size();i++)//哪些点的方向被确定 
        {
            int sa = s2[0][i];
            for(auto z:s2)
            {
                int w = z[i]; 
                if(w!=sa) sa = -1;
            }
            if(sa!=-1)
            {
                int x = s1[i].first,y = s1[i].second;
                ok[x][y] = 1,ans[x][y] = sa;
                if(sa==0) ok2[y] = 1;
                else ok1[x] = 1;
            }
        }
        tmp = s2,s2.clear();
        for(auto z:tmp)//更新可能的状态 
        {
            ts.reset();
            int cnt = 0;
            for(int i = 0;i<s1.size();i++)
                if(ok[s1[i].first][s1[i].second]||(!ok1[s1[i].first]&&!ok2[s1[i].second]))//被确定的点不能被删去，以保证正确性 
                    ts[cnt] = z[i],cnt++;
            s2.push_back(ts);
        }
        sort(s2.begin(),s2.end(),cmp);
        s2.erase(unique(s2.begin(),s2.end()),s2.end());
        vector<pair<int,int>> tmp2;
        for(int i = 0;i<s1.size();i++)//更新待确定的点 
            if(ok[s1[i].first][s1[i].second]||(!ok1[s1[i].first]&&!ok2[s1[i].second]))
                tmp2.push_back(s1[i]);
        s1 = tmp2;
    }
    return 0;
}