首页 > ACM题库 > HDU-杭电 > HDU 3590-PP and QQ[解题报告]HOJ
2014
11-27

HDU 3590-PP and QQ[解题报告]HOJ

PP and QQ

问题描述 :

PP and QQ were playing games at Christmas Eve. They drew some Christmas trees on a paper:

Jacobi symbol

Then they took turns to cut a branch of a tree, and removed the part of the tree which had already not connected with the root. A step shows as follows:

Jacobi symbol

PP always moved first.
PP and QQ took turns (PP was always the first person to move), to cut an edge in the graph, and removed the part of the tree that no longer connected to the root. The person who cannot make a move won the game.
Your job is to decide who will finally win the game if both of them use the best strategy.

输入:

The input file contains multiply test cases.
The first line of each test case is an integer N (N<100), which represents the number of sub-trees. The following lines show the structure of the trees. The first line of the description of a tree is the number of the nodes m (m<100). The nodes of a tree are numbered from 1 to m. Each of following lines contains 2 integers a and b representing an edge <a, b>. Node 1 is always the root.

输出:

The input file contains multiply test cases.
The first line of each test case is an integer N (N<100), which represents the number of sub-trees. The following lines show the structure of the trees. The first line of the description of a tree is the number of the nodes m (m<100). The nodes of a tree are numbered from 1 to m. Each of following lines contains 2 integers a and b representing an edge <a, b>. Node 1 is always the root.

样例输入:

2
2
1 2
2
1 2
1
2
1 2

样例输出:

PP
QQ

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;


vector<int> gra[100005];
int sg(int now,int fa)
{
 int sum=0;
 for(int i=0;i<gra[now].size();i++)
 if(gra[now][i]!=fa) sum^=sg(gra[now][i],now)+1;
 return sum;
}
int main()
{
 // freopen("1.txt","r",stdin);
 int c;
 while(scanf("%d",&c)==1)
 {
 int n,x,y,sum=0;
 bool anti=1;
 for(int k=0;k<c;k++)
 {
 scanf("%d",&n);
 for(int i=n;i>-1;i--)
 gra[i].clear();
 for(int i=1;i<n;i++)
 {
 scanf("%d%d",&x,&y);
 gra[x].push_back(y);
 gra[y].push_back(x);
 }
 int temp=sg(1,0);
 if(temp>1) anti=0;
 sum^=temp;
 }
 if(anti)
 {
 if(sum==0) printf("PP\n");
 else printf("QQ\n");
 }
 else
 {
 if(sum) printf("PP\n");
 else printf("QQ\n");
 }
 }
 return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n