Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

照着维基百科的模板敲的alphabeta,比较精炼~ 219ms水过~

Posted by xc19881023 at 2016-06-08 12:50:58 on Problem 1085
#include <cstdio>
#include <algorithm>
using namespace std;
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_state(int cur,int seg,int &cnt_a,int &cnt_b,bool flag) 
{
	int ret=cur|seg;
	for (int i = 0; i < 9; i++) 
	{
		if ((cur&triangle[i])!=triangle[i]&&(ret&triangle[i])==triangle[i])
		{
			if (flag) cnt_a++;	
			else cnt_b++;
		}
	}
	return ret;
}

int alpha_beta(int cur,int alpha,int beta,bool flag,int cnt_a,int cnt_b)
{
	if (cnt_a>=5) return 1;
	if (cnt_b>=5) return -1;
	if (cur==full) return cnt_a>cnt_b?1:-1;
	int remain=~cur&full;
	int t_cnt_a=cnt_a,t_cnt_b=cnt_b; 
	if (flag)
	{
		while (remain) 
		{
			cnt_a=t_cnt_a; 
			int seg=remain&(-remain),tmp=cnt_a;
			remain-=seg; 
			int nxt=nxt_state(cur,seg,cnt_a,cnt_b,true);
			if (cnt_a>tmp) alpha=max(alpha,alpha_beta(nxt,alpha,beta,true,cnt_a,cnt_b));
			else alpha=max(alpha,alpha_beta(nxt,alpha,beta,false,cnt_a,cnt_b));
			if (alpha>=beta) break;	
		}
		return alpha;
	}
	else
	{
		while (remain)
		{
			cnt_b=t_cnt_b;
			int seg=remain&(-remain),tmp=cnt_b;
			remain-=seg;
			int nxt=nxt_state(cur,seg,cnt_a,cnt_b,false);
			if (cnt_b>tmp) beta=min(beta,alpha_beta(nxt,alpha,beta,false,cnt_a,cnt_b));
			else beta=min(beta,alpha_beta(nxt,alpha,beta,true,cnt_a,cnt_b));
			if (alpha>=beta) break;			
		}
		return beta;
	}
}

int main()
{	
	int kase;
	scanf("%d",&kase);
	for (int t=1;t<=kase;t++)
	{
		int n,i,j,cnt_a=0,cnt_b=0,cur=0;
		bool flag=true;
		scanf("%d",&n);
		while (n--)
		{
			scanf("%d%d",&i,&j);
			int tmp_a=cnt_a,tmp_b=cnt_b; 
			cur=nxt_state(cur,1<<mat[i][j],cnt_a,cnt_b,flag);
			if (cnt_a==tmp_a&&cnt_b==tmp_b) flag=!flag;	
		}
		char winner=~alpha_beta(cur,-1,1,flag,cnt_a,cnt_b)?'A':'B';
		printf("Game %d: %c wins.\n",t,winner);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator