发布于 由itewqq

[对抗搜索][剪枝][建模转化][模板] POJ 1085

minimax搜索+α-β剪枝优化模板题。

第一个需要处理的就是把状态全部转化成二进制形式，包括三角形，边，棋盘，等等。转化好了之后就可以用minimax搜索了。在一开始的时候边读入边改变局面和cnta，cntb这两个分别代表a和b的得分，这个题有需要注意的一点就是如果一方得分了那么他是可以继续下一轮的，所以每次都要判断走向下一个局面的时候是不是得分。注意α是max层的最大值的最小边界，β是min层的最小值的最大边界，这里对一方操作之后发现不再满足α<=β，其实是跟父节点的另一方作对比的，一旦不满足即说明当前节点不再有利用价值，直接把这个越界的值返回父节点即可（因为父节点还是要更新状态的）这里并没有要求算出具体得分，所以用-1和1 来表示输赢即可，在每一层里加上cnt与5的关系判别也可以做到剪枝的作用。

还有一个技巧就是枚举二进制中的1，这里用的是类似于树状数组的lowbit的操作，很神奇 ，得到这个之后每次从remain中减去就可以做到枚举的效果了，而不用每次都从低位到高位循环一遍！

 


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-9)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}
const int full=(1<<18)-1;
int mat[11][11]={{0,0,0,0,0,0,0,0,0,0,0},
                 {0,0,0,1,0,0,0,0,0,0,0},
                 {0,0,0,2,3,4,0,0,0,0,0},
                 {0,1,2,0,0,5,6,0,0,0,0},
                 {0,0,3,0,0,7,0,9,10,0,0},
                 {0,0,4,5,7,0,8,0,11,12,0},
                 {0,0,0,6,0,8,0,0,0,13,14},
                 {0,0,0,0,9,0,0,0,15,0,0},
                 {0,0,0,0,10,11,0,15,0,16,0},
                 {0,0,0,0,0,12,13,0,16,0,17},
                 {0,0,0,0,0,0,14,0,0,17,0}
                };
int triangle[9]={7,152,52,352,34304,3200,71680,12544,155648};

int nxt(int cur,int seg,int flag,int& cnta,int& cntb)
{
     int ne=cur|seg;
     for (int i=0;i<9;i++)
     {
         if((cur&triangle[i])!=triangle[i]&&(ne&triangle[i])==triangle[i])
         {
             if(flag)cnta++;
             else cntb++;
         }
     }
     return ne;
}

int alphabeta(int cur,int alpha,int beta,int flag,int cnta,int cntb)
{
     if(cnta>=5)return 1;
     if(cntb>=5)return -1;
     if(cur==full)return cnta>cntb?1:-1;
     int seg,nt,ta,tb;
     if(flag)
     {
         int remain=~cur&full;
         while(remain)
         {
             ta=cnta,tb=cntb;
             seg=remain&(-remain);
             remain-=seg;
             nt=nxt(cur,seg,flag,ta,tb);
             if(ta>cnta)
                alpha=max(alpha,alphabeta(nt,alpha,beta,flag,ta,tb));//alpha?
             else
                alpha=max(alpha,alphabeta(nt,alpha,beta,!flag,ta,tb));
             if(alpha>=beta)break;//pure
         }
         return alpha;//??
     }
     else
     {
         int remain=~cur&full;
         while(remain)
         {
             ta=cnta,tb=cntb;
             seg=remain&(-remain);
             remain-=seg;
             nt=nxt(cur,seg,flag,ta,tb);
             if(tb>cntb)
                beta=min(beta,alphabeta(nt,alpha,beta,flag,ta,tb));//alpha?
             else
                beta=min(beta,alphabeta(nt,alpha,beta,!flag,ta,tb));
             if(alpha>=beta)break;//pure
         }
         return beta;//??
     }
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int t,m,u,v,cur,seg,nt,cnta,cntb,flag,ans,ta,tb,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        cas++;
        cnta=cntb=ta=tb=nt=cur=0;
        flag=1;
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            ta=cnta,tb=cntb;
            scanf("%d%d",&u,&v);
            seg=1<

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。