bzoj Triangle War 状态压缩+极大极小搜索+Alpha-Beta剪枝题意分析

100 阅读 0 评论 66 点赞

我是靠谱客的博主动人篮球，最近开发中收集的这篇文章主要介绍bzoj Triangle War 状态压缩+极大极小搜索+Alpha-Beta剪枝题意分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

有一个三角网格，两个人轮流操作，每次可以把一条虚线变成实线。若某个人把某条虚线变成实线后刚好围住了一个三角形，则这个人的得分加一。现在给出一开始的若干个操作，求谁会赢。

分析

首先压缩一波状态，然后就是裸的极大极小搜索+AB剪枝。
一开始错的是因为一开始以为连了一条线后最多围成一个三角形，其实可以围成很多个。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

int tra[10],bin[20],dot[11][11];

void init()
{
    dot[1][2]=1;dot[1][3]=2;dot[2][3]=3;dot[2][4]=4;dot[2][5]=5;dot[3][5]=6;dot[3][6]=7;dot[4][5]=8;dot[5][6]=9;
    dot[4][7]=10;dot[4][8]=11;dot[5][8]=12;dot[5][9]=13;dot[6][9]=14;dot[6][10]=15;dot[7][8]=16;dot[8][9]=17;dot[9][10]=18;
    tra[1]=7;tra[2]=152;tra[3]=52;tra[4]=352;tra[5]=34304;tra[6]=3200;tra[7]=71680;tra[8]=12544;tra[9]=155648;
}

int check(int x,int y)
{
    int ans=0;
    for (int i=1;i<=9;i++)
        if ((x&tra[i])==tra[i]&&(bin[y]&tra[i])==bin[y]) ans++;
    return ans;
}

int findmin(int now,int beta,int ca,int cb);
int findmax(int now,int alpha,int ca,int cb)
{
    if (now==bin[18]-1) return ca>cb?1:-1;
    if (ca>=5) return 1;
    if (cb>=5) return -1;
    int ans=-1;
    for (int i=1;i<=18;i++)
        if ((now&bin[i-1])==0)
        {
            int x=now+bin[i-1];
            int w=check(x,i-1);
            if (w) ans=max(ans,findmax(x,alpha,ca+w,cb));
            else ans=max(ans,findmin(x,ans,ca,cb));
            if (ans>=alpha) return ans;
        }
    return ans;
}

int findmin(int now,int beta,int ca,int cb)
{
    if (now==bin[18]-1) return ca>cb?1:-1;
    if (ca>=5) return 1;
    if (cb>=5) return -1;
    int ans=1;
    for (int i=1;i<=18;i++)
        if ((now&bin[i-1])==0)
        {
            int x=now+bin[i-1];
            int w=check(x,i-1);
            if (w) ans=min(ans,findmin(x,beta,ca,cb+w));
            else ans=min(ans,findmax(x,ans,ca,cb));
            if (ans<=beta) return ans;
        }
    return ans;
}

int main()
{
    bin[0]=1;
    for (int i=1;i<=18;i++)
        bin[i]=bin[i-1]*2;
    init();
    int t;
    scanf("%d",&t);
    for (int l=1;l<=t;l++)
    {
        int n;
        scanf("%d",&n);
        int s=0,next=0,ca=0,cb=0;
        for (int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (x>y) swap(x,y);
            s+=bin[dot[x][y]-1];
            int w=check(s,dot[x][y]-1);
            if (w)
            {
                if (!next) ca+=w;
                else cb+=w;
            }
            else next^=1;
        }
        int tmp;
        if (!next) tmp=findmax(s,1,ca,cb);
        else tmp=findmin(s,-1,ca,cb);
        if (tmp>0) printf("Game %d: A wins.n",l);
        else printf("Game %d: B wins.n",l);
    }
    return 0;
}