Printer Queuehttp://acm.tzc.edu.cn/acmhome/problemdetail.do?method=showdetail&id=1044
这个题目我想我是我做过的题目中思路最清晰的，代码最简洁的吧。（题目较简单）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<queue>//主要考察队列的应用 5 using namespace std; 6 bool comp1(int x,int y) 7 { 8 return x>y; 9 } 10 int main() 11 { 12 int t,i,n,m,s,d,temp; 13 int a[105]; 14 queue<int> Q; 15 scanf("%d",&t); 16 while(t--) 17 { 18 s=0; 19 scanf("%d%d",&n,&m); 20 for(i=0;i<n;i++) 21 { 22 scanf("%d",&a[i]); 23 Q.push(a[i]); 24 if(i==m) 25 d=i+1; 26 } 27 sort(a,a+n,comp1); 28 temp=Q.front(); 29 Q.pop(); 30 for(i=0;i<n;i++) 31 { 32 while(temp!=a[i]) 33 { 34 Q.push(temp); 35 d--; 36 if(d==0) 37 { 38 d=Q.size(); 39 } 40 temp=Q.front(); 41 Q.pop(); 42 } 43 s++; 44 if(d==1) 45 break; 46 d--; 47 temp=Q.front(); 48 Q.pop(); 49 } 50 printf("%d ",s); 51 while(!Q.empty()) 52 Q.pop(); 53 54 } 55 return 0; 56 }
Parencodingshttp://poj.org/problem?id=1068
题意：
P-sequence：表示第i个右括号前面有多少个左括号
W-sequence：表示第i个右括号与自己的左括号匹配好时他们之间有多少个左括号（包括本身的那个左括号）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<queue> 5 #include<string.h> 6 using namespace std; 7 int main() 8 { 9 queue<int> Q; 10 int a[100],i,j,t,n,temp,d,s; 11 scanf("%d",&t); 12 while(t--) 13 { 14 d=0; 15 memset(a,0,sizeof(a)); 16 scanf("%d",&n); 17 for(i=1;i<=n;i++) 18 { 19 scanf("%d",&a[i]); 20 for(j=0;j<a[i]-a[i-1];j++) 21 Q.push(1); 22 Q.push(2); 23 } 24 for(i=1;i<=2*n;i++) 25 { 26 temp=Q.front(); 27 Q.pop(); 28 a[i]=temp; 29 } 30 for(i=1;i<=2*n;i++) 31 { 32 s=0; 33 if(a[i]==2) 34 { d++; 35 if(d!=n) 36 { 37 for(j=i-1;j>=1;j--) 38 { 39 if(a[j]==-1) 40 {s++;continue;} 41 if(a[j]==1) 42 {s++;a[j]=-1; 43 printf("%d ",s);break; 44 } 45 } 46 } 47 else{ 48 for(j=i-1;j>=1;j--) 49 { 50 if(a[j]==-1) 51 {s++;continue;} 52 if(a[j]==1) 53 {s++;a[j]=-1; 54 printf("%d ",s);break; 55 } 56 } 57 58 } 59 } 60 } 61 } 62 return 0; 63 }//做个模型就A了（有点乱）
Grandpa is Famoushttp://poj.org/problem?id=2092
就是找出第二大的数：（注意的是排序和查找）
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 struct line 6 { 7 int w; 8 int num; 9 }a[10005]; 10 bool comp1(line a,line b) 11 { 12 if(a.num>b.num) 13 return true; 14 else if(a.num==b.num) 15 { 16 if(a.w<b.w) 17 return true; 18 } 19 return false; 20 } 21 int main() 22 { 23 int i,j,n,m,k,MAX,t; 24 while(scanf("%d%d",&n,&m)!=EOF) 25 { 26 if(n==0&&m==0) 27 break; 28 for(i=1;i<=10000;i++) 29 { 30 a[i].w=i; 31 a[i].num=0; 32 } 33 for(i=1;i<=n;i++) 34 for(j=1;j<=m;j++) 35 { 36 scanf("%d",&t); 37 a[t].num++; 38 } 39 sort(a+1,a+9999,comp1); 40 MAX=a[1].num; 41 for(i=2;i<=10000;i++) 42 { 43 if(a[i].num<MAX) 44 {MAX=a[i].num; 45 break;} 46 } 47 for(j=i;j<=10000;j++) 48 { 49 if(a[j].num==MAX&&a[j+1].num==MAX) 50 printf("%d ",a[j].w); 51 else if(a[j].num==MAX&&a[j+1].num!=MAX) 52 printf("%d ",a[j].w); 53 } 54 } 55 return 0; 56 }
Emag eht htiw Em Plehhttp://poj.org/problem?id=2993
主要是理解题目意思：转化成国际象棋的形式（总共32个棋子）
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<string.h> 5 #include<algorithm> 6 using namespace std; 7 int main() 8 { 9 int i,j,d1,e1,n,m; 10 char c[33]={'+','-','-','-','+','-','-','-','+','-','-','-','+','-','-','-','+','-','-','-','+','-','-','-','+','-','-','-','+','-','-','-','+'}; 11 char d[33]={'|','.','.','.','|',':',':',':','|','.','.','.','|',':',':',':','|','.','.','.','|',':',':',':','|','.','.','.','|',':',':',':','|'}; 12 char e[33]={'|',':',':',':','|','.','.','.','|',':',':',':','|','.','.','.','|',':',':',':','|','.','.','.','|',':',':',':','|','.','.','.','|'}; 13 char a[1000],b[1000]; 14 char k[20][40]; 15 for(i=0;i<17;i++) 16 for(j=0;j<33;j++) 17 { 18 if(i%2==0) 19 k[i][j]=c[j]; 20 else 21 { 22 if(i==1||i==5||i==9||i==13) 23 k[i][j]=d[j]; 24 else 25 k[i][j]=e[j]; 26 } 27 } 28 gets(a); 29 gets(b);//输入有空格的字符串用get（）！ 30 n=strlen(a);m=strlen(b); 31 for(i=7;i<50;i=i+4) 32 { 33 if(a[i]!='K'&&a[i]!='Q'&&a[i]!='R'&&a[i]!='B'&&a[i]!='N') 34 break; 35 if(a[i]=='K'||a[i]=='Q'||a[i]=='R'||a[i]=='B'||a[i]=='N') 36 {d1=(a[i+1]-'a')*4+2; 37 e1=15-(a[i+2]-'1')*2; 38 k[e1][d1]=a[i]; 39 } 40 } 41 for(j=i;j<n;j=j+3) 42 { 43 d1=(a[j]-'a')*4+2; 44 e1=15-(a[j+1]-'1')*2; 45 k[e1][d1]='P';//这里要注意大小写。 46 } 47 for(i=7;i<50;i=i+4) 48 { 49 if(b[i]!='K'&&b[i]!='Q'&&b[i]!='R'&&b[i]!='B'&&b[i]!='N') 50 break; 51 if(b[i]=='K'||b[i]=='Q'||b[i]=='R'||b[i]=='B'||b[i]=='N') 52 {d1=(b[i+1]-'a')*4+2; 53 e1=15-(b[i+2]-'1')*2; 54 k[e1][d1]=b[i]+32; 55 } 56 } 57 for(j=i;j<m;j=j+3) 58 { 59 d1=(b[j]-'a')*4+2; 60 e1=15-(b[j+1]-'1')*2; 61 k[e1][d1]='p';//这里要注意大小写。 62 } 63 for(i=0;i<17;i++) 64 {for(j=0;j<33;j++) 65 printf("%c",k[i][j]); 66 printf(" "); 67 } 68 69 return 0; 70 }最后要注意棋子的数目（可以全部有，也可以全部没有）。
An Old Stone Gamehttp://acm.tzc.edu.cn/acmhome/problemdetail.do?method=showdetail&id=2200
显然有递归来做的：
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 using namespace std; 5 struct leaf 6 { 7 int child_num; 8 int child[2000]; 9 }tree[2000]; 10 bool cmp(int a,int b) 11 { 12 return a>b; 13 } 14 int min(int a,int b) 15 { 16 return a>b?b:a; 17 } 18 int solve(int id) 19 { 20 int i,j,result,node[2000]; 21 if(!tree[id].child_num) 22 return 1; 23 for(i=0,j=0;i<tree[id].child_num;i++) 24 node[j++]=solve(tree[id].child[i]);//循环找此节点的石子数 25 sort(node,node+j,cmp); 26 result=node[0]; 27 for(i=1;i<j;i++) 28 result+=node[i]-min(node[i],result-i); 29 return result; 30 31 } 32 int main() 33 { 34 int id,node_num,i,j,t,n; 35 scanf("%d",&t); 36 while(t--) 37 { 38 scanf("%d",&n); 39 for(j=0;j<n;j++) 40 { 41 scanf("%d %d",&id,&node_num); 42 tree[id].child_num=node_num; 43 for(i=0;i<node_num;i++) 44 scanf("%d",&tree[id].child[i]); 45 } 46 printf("%d ",solve(1)); 47 } 48 49 return 0; 50 }
设所求结果用result来表示，我们要求的是以1为根的result，这个结果必定依赖于它的子节点的相关信息。这个信息会是什么呢？考虑一棵树的子孙是该树的子树。假设1的子孙分别为r1,r2,r3。那么r1，r2，r3，都是1的子树的根。假设以r1，r2，r3为根的上述结果分别为result1，result2，result3，显然它们之和一定能达到1上也能被放上石子的目的。那这个值是不是最小的呢？假设result1>=result2>=result3，我们用result1个石子让r1上放上了一个石子，此时我们剩余了result1-1个石子没有用，这些石子可以弥补result2，最终可能会得到一个更小的值（<=result1+result2+result3，通过对先前石子的重复利用）。如何安排这种弥补方式呢？
最大值优先。r1需要的石子result1最大，那么最终的结果必定result>=result1，然而最终只需在r1上放一个石子，留下了result1-1个石子。
那么r1 ，r2一共需要Result = result1+result2-min( result-1,result2 )个石子，其中min(result1-1,result2)被加了两次，所以要减掉一次。
这样r1，r2就合并成了一个节点，最少需要Result个石子，那么result=Result+result3-min（Result-2，result3）。最终得解。