基于刚才的博弈树,我的分析如下:因此必须要有一个状态位,通知上面的节点是否进行了剪刀,如果
不存在剪刀操作,那么我们可以放心记录下f[s]的值,否则,这个状态是无效的!OK,实现代码在后!
令我震惊的是A-B剪刀居然令速度减少了很多,仔细一想确实如此,动规虽然计算了所有的状态,但在测试用例很
多的情况下,实际上做了一个字典,尤其是官方数据有大概1500个测试用例,那么基本可以覆盖整个主要路径,覆盖
博弈空间直觉上是不可能[没算过,慌到做下一道题],那么平摊效应而言,其实是相当优秀的!
相反用A-B剪刀对于单个用例虽然快了,但对于太多的用例,确不能有效地检索可能到达的路径。这就是典型的半途而废,如果
下一个目标状态频繁的出现在上个用例的A-B剪刀处,那性能上的浪费是可以直接定语的!所以A-B和动规的速度才有如此差距
好了,废话多了,代码如下,下一道L-Game
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>
using namespace std;
const int TriCount=9;
char TriC[TriCount];//edge count of each triangle
//global mapping
char TriofV[19][2]={{-1,-1}/*0*/,{0,-1}/*1*/,{0,-1}/*2*/,{0,2}/*3*/,
                    {1,-1}/*4*/,{1,2}/*5*/,{2,3}/*6*/,{3,-1}/*7*/,
                    {1,5}/*8*/,{4,-1}/*9*/,{4,5}/*10*/,{5,6}/*11*/,
                    {6,7}/*12*/,{7,8}/*13*/,{8,-1}/*14*/,{3,7}/*15*/,
                    {4,-1}/*16*/,{6,-1}/*17*/,{8,-1}/*18*/};
inline int toLine(int v1, int v2){//mapping table
    if(v1>v2) v1^=v2,v2^=v1,v1^=v2;
    if(v1==3&&v2==4) return 8;
    if(v1==4&&v2==5) return 15;
    if(v1==6&&v2==7) return 16;
    if(v1==7&&v2==8) return 17;
    if(v1==8&&v2==9) return 18;
    return v1+v2;
}
//status function
char f[0x080000][2];//may be minor, 2^19
//recursive logic : Tric[TriCount] is enough, if we use recovery logic.
//alpha and beta cut-off branches
int recurGame(unsigned int status, int cPlayer, int alpha, int beta, bool& prune);
typedef struct ndptr{//for candidate of our selections, the sum of number of winning triangle
    char line,Tri;
}ndptr;
//const int MIN_INVL=INT_MIN, MAX_INVL=INT_MAX;
//implementation for Game, no height constriant of tree
//f[status] stands for MAX or MIN chess, how many A could win B?
//forA,forB is used for judgement by intuition
int recurGame(unsigned int status, int cPlayer, int alpha, int beta, bool& prune){
    if(status==0) return 0;//NONE can move
    //already solved
    if(cPlayer>0&&f[status][0]!=10) return f[status][0];
    if(cPlayer<0&&f[status][1]!=10) return f[status][1];
    //depth verification
    int v,A,k,i,j,line,pre;
    bool pru,s=false;
    bitset<19> cstatus=status;
    int len=cstatus.count();
    //sorting ndptr[len] by Tri descending order
    ndptr suc[len];
    k=0;
    for(int i=1;i<19;i++){
        if(cstatus.test(i)){//line i
            for(j=0, A=0; j<2; j++)
               if(TriofV[i][j]!=-1&&TriC[(int)TriofV[i][j]]==2) A++;
            //for, memcpy for TriofV[i][0…1]
            if(k==0){
                suc[k].line=i,suc[k].Tri=A;
                k++;
            }
            else{//[0…k-1], current number is A
                j=k;
                for(;j-1>=0&&suc[j-1].Tri<A;j–)
                    suc[j].line=suc[j-1].line,suc[j].Tri=suc[j-1].Tri;
                suc[j].line=i,suc[j].Tri=A;
                k++;
            }
        }
    }
    //node sorting alogrithm
    if(cPlayer>0){//A max
        v=INT_MIN;
        for(i=0; i<len; i++){
            line=suc[i].line;pru=false;
            /*set*/
            cstatus.reset(line);
            for(j=0;j<2;j++)
                if(TriofV[line][j]!=-1) TriC[(int)TriofV[line][j]]++;
            /*set*/
            /*alpha-beta cutoff*/
            if(suc[i].Tri>0)
                k=suc[i].Tri+recurGame(cstatus.to_ulong(), cPlayer, alpha, beta, pru);
            else k=recurGame(cstatus.to_ulong(), -cPlayer, alpha, beta, pru);
            s=s||pru;
            /*recovery*/
            cstatus.set(line);
            for(int j=0; j<2; j++)
                if(TriofV[line][j]!=-1) TriC[(int)TriofV[line][j]]–;
            /*recovery*/
            if(k>v) v=k;
            if(v>beta) {prune=true; return v;}
            //b cut-off branches
            if(alpha<v) alpha=v;
        }
        if(!s) f[status][0]=v;
    }
    else{//B MIN
        v=INT_MAX;
        for(i=0; i<len; i++){
            line=suc[i].line;pru=false;
            /*set*/
            cstatus.reset(line);
            for(j=0; j<2; j++)
                if(TriofV[line][j]!=-1) TriC[(int)TriofV[line][j]]++;
            /*set*/
            /*alpha-beta cut-off*/
            if(suc[i].Tri>0)
                k=-suc[i].Tri+recurGame(cstatus.to_ulong(), cPlayer, alpha, beta, pru);
            else k=recurGame(cstatus.to_ulong(), -cPlayer, alpha, beta, pru);
            s=s||pru;
            /*recovery*/
            cstatus.set(line);
            for(j=0; j<2; j++)
                if(TriofV[line][j]!=-1) TriC[(int)TriofV[line][j]]–;
            /*recovery*/
            if(v>k) v=k;
            if(v<alpha) { prune=true; return v; }//alpha cut-off
            if(beta>v) beta=v;//MIN change

        }
        if(!s)f[status][1]=v;//对于裁减过得状态,我们如此处理,不用字典了,因此下面的返回值其实意义不大!起码不会影响状态的标定
    }
    return v;
}
#define fbase
int main()
{
    //global shared parameters,f[x] can’t be zero, no tie
    memset((void*)&f[0][0], 10, 0x080000*2);
    #ifdef fbase
    ifstream in, out;
    ofstream e("error.txt");
    if(!e) return EXIT_FAILURE;
    char intxt[20], outtxt[20];
    int x1[20], y1[20], total=0;
    for(int k=1; k<16; k++){
        memset((void*)intxt, 0, 20), memset((void*)outtxt, 0, 20);
        _itoa(k, intxt, 10);
        strcat(outtxt, intxt);
        strcat(outtxt, "out");
        in.open(intxt);
        if(!in){ cout<<intxt<<" ignore"<<endl; continue;}
        out.open(outtxt);
        if(!out){ cout<<outtxt<<" ignore"<<endl; continue;}
        cin.rdbuf(in.rdbuf());
    #endif
    //read n case
    int n,m,x,y,forA,forB,incre,cPlayer,p;//every time change
    bitset<19> status;
    cin>>n;
    string s1,s2;
    for(int i=0; i<n; i++){
        //intial for new game
        memset((void*)TriC, 0, TriCount);
        forA=forB=0,cPlayer=-1/*reset each time start with A*/;
        status=0x07fffe;//copy constructor
        cin>>m;//for previous m step
        #ifdef fbase
        p=0;
        #endif
        memset((void*)x1, 0, sizeof(int)*18), memset((void*)y1, 0, sizeof(int)*18);
        for(int k=0;k<m;k++){
            cin>>x,cin>>y;
            #ifdef fbase
            x1[p]=x,y1[p++]=y;
            #endif
            int line=toLine(x-1,y-1);//to 0 starting pointer
            cPlayer*=-1;
            if(status.test(line)){
                status.reset(line);
                incre=0;
                for(int j=0;j<2;j++){//move for A or B
                    if(TriofV[line][j]!=-1){
                        TriC[(int)TriofV[line][j]]++;
                        if(TriC[(int)TriofV[line][j]]==3) incre++;
                    }
                }
                if(incre>0){
                    if(cPlayer>0) forA+=incre;
                    else forB+=incre;
                    cPlayer*=-1;//one more time
                }
            }
        }
        if((k==4&&i+1==3)||(k==5&&i+1==76)){
            if(-cPlayer>0){
                cout<<"f:"<<(int)f[status.to_ulong()][0]<<endl;
            }
            if(-cPlayer<0){
                cout<<"f:"<<(int)f[status.to_ulong()][1]<<endl;
            }
        }
        bool prun=true;
        int c=recurGame(status.to_ulong(), /*forA, forB,*/ -cPlayer, -12, 12, prun);//next player
        /*if(forA-forB+c>0)
            cout<<"Game "<<i+1<<": A wins."<<endl;
        else
            cout<<"Game "<<i+1<<": B wins."<<endl;*/
        getline(out, s1);
        char id[3];
        _itoa(i+1, id, 10);
        assert(s1.find(id)!=string::npos);
        if((k==4&&i+1==3)||(k==5&&i+1==76)){
            cout<<forA<<" "<<forB<<" "<<c<<endl;
            cout<<"input:"<<k<<endl;
            if(forA-forB+c>0)
                cout<<"Game "<<i+1<<": A wins."<<endl;
            else
                cout<<"Game "<<i+1<<": B wins."<<endl;
        }
        if(forA-forB+c>0){
            if(s1.find(‘A’)==string::npos){//My programm – A win
                #ifdef fbase
                    total++;
                    e<<m<<"  [B>A] c-"<<c<<" forA-"<<forA<<" forB-"<<forB<<endl;
                    for(int u=0;u<p;u++) e<<x1[u]<<" "<<y1[u]<<endl;
                    e<<endl<<intxt<<" mismatch "<<endl;
                    e<<"Game "<<i+1<<": A wins."<<forA-forB+c<<endl;
                    e<<s1<<" [right answer] "<<endl;
                    e<<endl;
                #endif
            }
        }
        else if(forA-forB+c<0){
            if(s1.find(‘B’)==string::npos){
                #ifdef fbase
                    total++;
                    e<<m<<"  [A>B] c-"<<c<<" forA-"<<forA<<" forB-"<<forB<<endl;
                    for(int u=0;u<p;u++) e<<x1[u]<<" "<<y1[u]<<endl;
                    e<<endl<<intxt<<" mismatch "<<endl;
                    e<<"Game "<<i+1<<": B wins."<<forA-forB+c<<endl;
                    e<<s1<<" [right answer] "<<endl;
                    e<<endl;
                #endif
            }
        }
    }
    #ifdef fbase
        in.close(),in.clear();
        out.close(),out.clear();
    }
    cout<<total<<" error"<<endl;
    e.close();
    #endif
    return 0;
}
#undef fbase
Advertisements