numdle

标签：vector gu now string int numdle include

算一下信息熵，每次取最大的询问。

复杂度 O(n^2)，常数略大。

好像还可以组合计数，但懒得想了。

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#pragma GCC optimize(2)
using namespace std;

vector<string> now;

void init(){
    now.clear();
    for(char a='0';a<='9';a++)
    for(char b='0';b<='9';b++)
    for(char c='0';c<='9';c++)
    for(char d='0';d<='9';d++){
        string x="";
        x+=a; x+=b; x+=c; x+=d;
        now.push_back(x);
    }
}

void check(const string &A,const string &B,int &x,int &y){
    static int b[10]; x=y=0;
    for(int i=0;i<10;i++) b[i]=0;
    for(int i=0;i<4;i++) b[A[i]-'0']++;
    for(int i=0;i<4;i++)
        if(A[i]==B[i]) x++;
        else y+=(b[B[i]-'0']>0);
}

int update(vector<string> &V,int x,int y,const string &g,bool op=0){
    if(!op){
        vector<string> w; w.clear();
        int x_,y_;
        for(string v:V){
            check(v,g,x_,y_);
            if(x_==x&&y_==y) w.push_back(v);
        }
        return V=w,0;
    }else{
        int x_,y_,ret=0;
        for(string v:V){
            check(v,g,x_,y_);
            if(x_==x&&y_==y) ret++;
        }
        return ret;
    }
}

string nq(vector<string> &V){
    double mx=0; string gu=V[0];
    int mp[5][5];
    for(string g:V){
        double e=0;
        for(int x=0;x<=4;x++)
        for(int y=0;y<=4;y++)
            mp[x][y]=update(V,x,y,g,1);
        for(string v:V){
            int x,y; check(v,g,x,y);
            if(mp[x][y]) e+=log2(1.0*V.size()/mp[x][y]);
        }
        if(e>mx) mx=e,gu=g;
    }
    return gu;
}

int main(){
    init();
    string rq="0123";
    int x,y;
    while(now.size()!=1){
        cout<<rq<<endl;
        cin>>x>>y;
        update(now,x,y,rq);
        rq=nq(now);
    }
    cout<<rq<<"!!!"<<endl;
}

标签：vector,gu,now,string,int,numdle,include
From： https://www.cnblogs.com/wwlwQWQ/p/17418544.html