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

Re:0ms一发AC,不需要任何搜索,贴一发代码,四色定理直接染

Posted by 201824100818 at 2019-11-18 22:11:52 on Problem 1129
In Reply To:0ms一发AC,不需要任何搜索,贴一发代码,四色定理直接染 Posted by:danagi at 2015-08-13 12:00:58
> #include <stdio.h>
> #include <string.h>
> bool grid[26][26];
> int color[26];
> int lowbit(int x)
> {
> 	return x&(-x);
> }
> int getColorNum(int x)
> {
> 	switch(x)
> 	{
> 		case 0x1:return 1;
> 		case 0x2:return 2;
> 		case 0x4:return 3;
> 		case 0x8:return 4;
> 	}
> }
> int main()
> {
> 	char c;
> 	int n,ans,tmp;
> 	while(scanf("%d\n",&n)&&n)
> 	{
> 		ans=0;
> 		memset(grid,false,sizeof(grid));
> 		for(int i=0;i<n;++i)
> 		{
> 			getchar();
> 			getchar();
> 			while((c=getchar())!='\n')
> 				grid[i][c-'A']=true;
> 			color[i]=0xf;
> 		}
> 		for(int i=0;i<n;++i)
> 		{
> 			color[i]=lowbit(color[i]);
> 			tmp=getColorNum(color[i]);
> 			if(tmp>ans)
> 				ans=tmp;
> 			if(ans==4)
> 				break;
> 			for(int j=i+1;j<n;++j)
> 				if(grid[i][j])
> 					color[j]^=color[i];
> 		}
> 		ans==1?printf("%d channel needed.\n",ans):printf("%d channels needed.\n",ans);
> 	}
> 	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