题解：P13068 [GCJ 2020 #3] Pen Testing

· · 题解

思考一下这个操作，发现只有把一支笔写到没有墨才能获得一些能够帮助我们决策的信息。并且我们也不会一直选没有被写过的笔，因为这样和随机选没有本质区别。

这样一个朴素的想法就是我们可以写干一些墨水比较少的笔，来提高接下来取到剩余墨水高的笔的概率。事实上，这里我们让所有笔都书写 2\sim 4 次来去掉那些墨水很少的笔就已经有大约 56\% 的概率可以通过了。

接下来我们进行搜索，来找出每一个状态对应的最优决策。 设数组 a 中 a_i 表示第 i 支未被写干的笔已经被试写了多少次，vis 表示已经被写干的笔的墨水数量集合， f(a,vis) 表示在这种状态下能满足最终要求的排列数。接下来有两种决策：

形式化地，假设当前 a 最小的两个值分别为 a_i,a_j；vis 集合中最大的未被确定的值是 k；w=\max_{a_i\leq k}a_i，则

f(a,vis)=max(g(a_i,a_j,a,vis),f(a',vis)+[w=k]f(a\setminus \left \{ w \right \},vis\cup \left \{ w \right \} ))

其中 g(a_i,a_j,a,vis) 表示选 a_i,a_j 作为最终答案时，当前情况下符合要求的排列数，这个直接暴力算就可以。 a' 表示 a 经过 w\leftarrow w+1 操作后的数组。后面的两项之和分别就是当前书写成功（更新 w）和当前书写失败（扩展 k）。

带入 a={\underbrace{0,0\cdots 0}_{15 个 0}},vis=\varnothing，得到通过概率大约为 64.156\%，状态总数 65504，可以通过此题。

// Written by Mi2uk1 
// Try Harder.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i28 __int128 
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fir first
#define INF (1e9) 
#define sec second
#define pb push_back
#define eb emplace_back

const int N=30+9,M=(1<<12)+9;
const int MOD=998244353;
const double eps=1e-9;
inline void chkmax(int &x,int y){x=x<y?y:x;}
inline void chkmin(int &x,int y){x=x<y?x:y;}
inline void chkmax(ll &x,ll y){x=x<y?y:x;}
inline void chkmin(ll &x,ll y){x=x<y?x:y;}
inline int lowbit(int x){return x&(-x);}
int qpow(int a,int b,int p){
    int ret=1;
    while(b){
        if(b&1) ret=1ll*ret*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return ret; 
}

#define fir first
#define sec second
double tsum=0; 
map<pair<vector<int>,int>,double> mp1;
map<pair<vector<int>,int>,bool> mp2;
double dfs(vector<int> a,int k,int N=15){
    if(a.size()<2) return 0;
    sort(a.begin(),a.end()); 
    if(mp1.count({a,k})) return mp1[{a,k}];

    double cst=0,cwr=0;
    for(int i=k;i<N;++i){
        for(int j=i+1;j<N;++j){
            if(i<a[0] || j<a[1]) continue;
            if(i+j>=N+a[0]+a[1]){
                double coef=0,cnt=1;
                if(i>=a[0] && j>=a[1]) coef+=1;
                if(i>=a[1] && j>=a[0]) coef+=1;
                for(int pos=a.size()-1;pos>=2;--pos){
                    int us=N-max(k,a[pos]);
                    if(i>=a[pos]) --us;
                    if(j>=a[pos]) --us;
                    if(us<=a.size()-1-pos){cnt=0; break;}
                    cnt=cnt*(us-(a.size()-1-pos));
                } cst+=coef*cnt;
            }
        }
    }

    int tpos=-1;
    for(int i=a.size()-1;i>=0;--i)
        if(a[i]<=k){tpos=i; break;}
    if(tpos==-1){
        mp2[{a,k}]=1;
        return mp1[{a,k}]=cst;
    }

    vector<int> tmp;
    //success
    tmp=a; tmp[tpos]++;
    cwr+=dfs(tmp,k);
    //failed
    if(a[tpos]==k){
        tmp=a; tmp.erase(tmp.begin()+tpos);
        cwr+=dfs(tmp,k+1);
    } 

    mp2[{a,k}]=(cst>=cwr); ++tsum;
    return mp1[{a,k}]=max(cst,cwr);
}
bool ed[100009];
vector<pair<int,int> > a[100009];
vector<int> ask;
int ans[100009][2];
int k[100009],ta[100009],tpos[100009];
mt19937 rd(random_device{}()); 
int id[19];
void Mian(){
    int T,N,C; cin>>T>>N>>C;
    vector<int> st(N,0);
    dfs(st,0);

    for(int j=1;j<=T;++j){
        for(int i=1;i<=N;++i) a[j].push_back({i,0});
        k[j]=0; ed[j]=0; 
    }
    while(1){
        bool flg=0; ask.clear();
        for(int j=1;j<=T;++j){
            ta[j]=0;
            if(ed[j]){ask.pb(0); continue;}
            vector<int> tmp;
            for(int i=0;i<a[j].size();++i)
                tmp.push_back(a[j][i].sec);
            sort(tmp.begin(),tmp.end()); 
            if(mp2[{tmp,k[j]}]){
                sort(a[j].begin(),a[j].end(),[](pair<int,int> a,pair<int,int> b){
                    return a.sec<b.sec;
                });
                ans[j][0]=a[j][0].fir; ans[j][1]=a[j][1].fir;
                ed[j]=1; ask.pb(0);
            }else{
                int tmx=-1; tpos[j]=-1;
                for(int i=0;i<a[j].size();++i)
                    if(a[j][i].sec<=k[j] && a[j][i].sec>tmx) tpos[j]=i,tmx=a[j][i].sec;
                if(tpos[j]==-1){
                    sort(a[j].begin(),a[j].end(),[](pair<int,int> a,pair<int,int> b){
                        return a.sec<b.sec;
                    });
                    ans[j][0]=a[j][0].fir; ans[j][1]=a[j][1].fir;
                    ed[j]=1; ask.pb(0);
                }else{
                    ask.pb(a[j][tpos[j]].fir); ta[j]=1; flg=1;
                }
            }
        }

        for(int i=0;i<T;++i) cout<<ask[i]<<' '; cout<<endl; 
        if(!flg){
            for(int i=1;i<=T;++i)
                cout<<ans[i][0]<<' '<<ans[i][1]<<' '; cout<<endl;
            return ;
        }

        for(int j=1;j<=T;++j){
            int res; cin>>res;
            if(!ta[j] || ed[j]) continue;
            if(res) a[j][tpos[j]].sec++;
            else{
                a[j].erase(a[j].begin()+tpos[j]);
                ++k[j];
            }
        }
    }
}
void Mianclr(){

}
signed main(){
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);     

    //freopen("ftc1.in","r",stdin);
    //freopen("r.out","w",stdout);

    int c,T=1; //cin>>T;
    while(T--){
        Mianclr();
        Mian();
    }
}