过了所有的15个官方测试文件,但在浙大那个死地方过不聊[难道20MS的都会被鄙视么?]
我对这道题做的不是很满意,应该说相当不满意,老想把所有技巧都用进去,加个技巧,错个地方!不过,先放这边把
我转向下一道题目,估计很难,比这个应该会难很多!花精力在这种菜题上实在不值得,编码时间不过30分钟,tmd用
测试用例测了整整两天!兰的管了,框架熟悉了就好啦!
  • 问题1:Alpha-Beta剪刀难道不能和DP状态的二维数组并存么?博弈的状态空间如下:

这样会造成f[s]的错误标志,所以后来的数据就全部错了!

  • 状态的排序[很简单,线形的插入即可],状态的设置与恢复必须成对,而且在返回之前

代码[已过所有官方数据,浙大的测试时间20MS,A-B+排序果真威力强大!]

#include <iostream>
#include <fstream>
#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
typedef struct ndptr{//for candidate of our selections, the sum of number of winning triangle
    char line,Tri/*increaing number*/;
}ndptr;
//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);

//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){
     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;
    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++;
            }
        }
    }
    assert(k==len&&len>0);
    //node sorting alogrithm
    if(cPlayer>0){//A max
        v=INT_MIN;
        for(i=0; i<len; i++){
            line=suc[i].line;
            /*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);
            else k=recurGame(cstatus.to_ulong(), -cPlayer, alpha, beta);
            /*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) return v;
            //b cut-off branches
            if(alpha<v) alpha=v;
        }
        f[status][0]=v;
    }
    else{//B MIN
        v=INT_MAX;
        for(i=0; i<len; i++){
            line=suc[i].line;
            /*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);
            else k=recurGame(cstatus.to_ulong(), -cPlayer, alpha, beta);
            /*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) return v;//alpha cut-off
            if(beta>v) beta=v;//MIN change
        }
        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("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //read n case
    int n,m,x,y,forA,forB,incre,cPlayer;//every time change
    bitset<19> status;
    cin>>n;
    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
        for(int k=0;k<m;k++){
            cin>>x,cin>>y;
            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(-cPlayer>0){
            cout<<"f:"<<(int)f[status.to_ulong()][0]<<endl;
        }
        if(-cPlayer<0){
            cout<<"f:"<<(int)f[status.to_ulong()][1]<<endl;
        }

        int c=recurGame(status.to_ulong(), -cPlayer, -12, 12);//next player

        cout<<forA<<" "<<forB<<" "<<c<<endl;
        if(forA-forB+c>0)
           cout<<"Game "<<i+1<<": A wins."<<endl;
        else if(forA-forB+c<0)
           cout<<"Game "<<i+1<<": B wins."<<endl;
        else
           cout<<"Game "<<i+1<<": Weird result."<<endl;
    }
    return 0;
}
#undef fbase

Advertisements