HDU 3595 GG and MM(Every-SG)
2018-06-17 21:10:09来源:未知 阅读 ()
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 805 Accepted Submission(s):
367
Many years later, GG and MM find this game is too simple, so they decided to play N games at one time for fun. MM plays first, as the same, and the one on his/her turn must play every unfinished game. Rules to remove are as same as above, and if someone cannot remove any stone (i.e., loses the last ending game), then he/she loses. Of course we can assume GG and MM are clever enough, and GG will not lose intentionally, O(∩_∩)O~
The first line of each test case is an integer N, N<=1000, which represents there are N games, then N lines following, each line has two numbers: p and q, standing for the number of the two piles of stones of each game, p, q<=1000(it seems that they are so leisure = =!), which represent the numbers of two piles of stones of every game.
The input will end with EOF.
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> const int MAXN=1001; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int a[MAXN],b[MAXN],SG[MAXN][MAXN],step[MAXN][MAXN]; int GetSG(int x,int y) { if(x>y) std::swap(x,y); if(SG[x][y]!=-1) return SG[x][y]; if(!x||!y) return SG[x][y]=step[x][y]=0; int willx=y%x,willy=x; int k=y/x; if(k==1) { SG[x][y]=GetSG(willx,willy)^1; step[x][y]=step[willx][willy]+1; return SG[x][y]; } else { step[x][y]=GetSG(willx,willy)+step[willx][willy]+1; return SG[x][y]=1;//此时先手必胜 } } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif memset(SG,-1,sizeof(SG)); int N; while(scanf("%d",&N)!=EOF) { int ans=0; for(int i=1;i<=N;i++) { int x=read(),y=read(); if(x>y) std::swap(x,y); GetSG(x,y); ans=std::max(ans,step[x][y]); } puts(ans%2?"MM":"GG"); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:auto关键字
- C++ rand函数 2020-06-10
- Android P HIDL demo代码编写 (原创) 2020-05-07
- HDU-2955-Robberies(0-1背包) 2020-03-30
- C++ STL框架 2020-03-29
- AtCoder Grand Contest 043--A - Range Flip Find Route 2020-03-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash