当前位置: 代码迷 >> 综合 >> 算法之美——浙大计算机研究生复试上机考试-2009年
  详细解决方案

算法之美——浙大计算机研究生复试上机考试-2009年

热度:78   发布时间:2024-01-13 06:17:43.0

XXX定律

[cpp]  view plain copy
  1. #include "iostream"  
  2. using namespace std;  
  3. int main()  
  4. {  
  5.     int n;  
  6.     while (cin>>n&&n!=0)  
  7.     {  
  8.         int cnt=0;  
  9.         while(n!=1)  
  10.         {  
  11.             n=n%2?(n*3+1)>>1:n>>1;  
  12.             cnt++;  
  13.         }  
  14.         printf("%d\n",cnt);  
  15.     }  
  16. }  

ZOJ

[cpp]  view plain copy
  1. #include "iostream"  
  2. #include "string"  
  3. using namespace std;  
  4.   
  5. int main()  
  6. {  
  7.     string str;  
  8.     while(cin>>str&&str!="E")  
  9.     {  
  10.         int i;  
  11.         int count[26];  
  12.         memset(count,0,sizeof(int)*26);  
  13.         for (i=0;i<str.length();i++)  
  14.             count[str[i]-'A']++;  
  15.         int z='Z'-'A',o='O'-'A',j='J'-'A';  
  16.         while (count[z]>0||count[o]>0||count[j]>0)  
  17.         {  
  18.             if(count[z]-->0)  
  19.                 printf("Z");  
  20.             if(count[o]-->0)  
  21.                 printf("O");  
  22.             if(count[j]-->0)  
  23.                 printf("J");  
  24.         }  
  25.         printf("\n");  
  26.     }  
  27. }  

继续xxx定律

[cpp]  view plain copy
  1. #include "iostream"  
  2. using namespace std;  
  3. int a[550];  
  4. bool num[250000];//(x*3+1)/2======num means cover  
  5.   
  6. int main()  
  7. {  
  8.     int n,i,j;  
  9.     while (scanf("%d",&n)!=EOF&&n!=0)  
  10.     {  
  11.         memset(num,false,sizeof(bool)*1010);  
  12.         for (i=0;i<n;i++)  
  13.         {  
  14.             scanf("%d",&a[i]);  
  15.             int temp=a[i];  
  16.             while(!num[a[i]]&&temp!=1)  
  17.             {  
  18.                 temp=temp%2?(temp*3+1)>>1:temp>>1;  
  19.                 num[temp]=true;  
  20.             }  
  21.         }  
  22.         i=n-1;  
  23.         while(num[a[i]])  
  24.             i--;  
  25.         printf("%d",a[i]);  
  26.         //num[a[i]]=true;   %>_<%我还以为出现的关键数不该再出现了,没想到不用特判   
  27.         for (i=i-1;i>=0;i--)  
  28.         {  
  29.             if (!num[a[i]])  
  30.                 printf(" %d",a[i]);  
  31.             //num[a[i]]=true;  
  32.         }  
  33.         printf("\n");  
  34.     }  
  35. }  

找大富翁

[cpp]  view plain copy
  1. /************************************************************************/  
  2. /* bubble-437ms                                                                   */  
  3. /************************************************************************//  
  4. #include "iostream"  
  5. using namespace std;  
  6. int a[100100];  
  7. void swap(int i,int j)  
  8. {  
  9.     a[i]=a[i]^a[j];  
  10.     a[j]=a[i]^a[j];  
  11.     a[i]=a[i]^a[j];  
  12. }  
  13. int main()  
  14. {  
  15.     int n,m,i,j;  
  16.     while (scanf("%d%d",&n,&m)!=EOF&&!(n==0&&m==0))  
  17.     {  
  18.         if(n<m)  
  19.             m=n;  
  20.         for (i=0;i<n;i++)  
  21.             scanf("%d",&a[i]);  
  22.         for (i=1;i<=m;i++)  
  23.         {  
  24.             for(j=0;j<n-1;j++)  
  25.                 if (a[j]>a[j+1])  
  26.                     swap(j,j+1);  
  27.         }  
  28.         for(i=1;i<m;i++)  
  29.             printf("%d ",a[n-i]);  
  30.         printf("%d\n",a[n-m]);  
  31.     }  
  32. }  
  33.   
  34. /************************************************************************/  
  35. /* sort-468ms                                                                     
  36. #include "iostream" 
  37. #include "algorithm" 
  38. using namespace std; 
  39. int a[100100]; 
  40. void swap(int i,int j) 
  41. {  
  42. a[i]=a[i]^a[j]; 
  43. a[j]=a[i]^a[j]; 
  44. a[i]=a[i]^a[j]; 
  45. } 
  46. int main() 
  47. {  
  48. int n,m,i,j; 
  49. while (scanf("%d%d",&n,&m)!=EOF&&!(n==0&&m==0)) 
  50. {  
  51. if(n<m) 
  52. m=n; 
  53. for (i=0;i<n;i++) 
  54. scanf("%d",&a[i]); 
  55. sort(a,a+n); 
  56. for(i=1;i<m;i++) 
  57. printf("%d ",a[n-i]); 
  58. printf("%d\n",a[n-m]); 
  59. } 
  60. } */  
  61. /************************************************************************//  
找出直系亲属


[cpp]  view plain copy
  1. #include "iostream"  
  2. #include "string"  
  3. #include "algorithm"  
  4. using namespace std;  
  5. #define INF 1000000  
  6. #define min(a,b) a<b?a:b  
  7. char tree['Z'+10][2];  
  8.   
  9. int Dfs(char a,char b,int level)  
  10. {  
  11.     //分别从a和b往下找  
  12.     if(a=='-'||tree[a][0]=='-'&&tree[a][1]=='-')  
  13.         return INF;  
  14.     if(tree[a][0]==b||tree[a][1]==b)  
  15.         return level+1;  
  16.     int left=Dfs(tree[a][0],b,level+1);  
  17.     int right=Dfs(tree[a][1],b,level+1);  
  18.     return min(left,right);  
  19. }  
  20. int main()  
  21. {  
  22.     string str;  
  23.     int n,m,i,j;  
  24.     while (scanf("%d%d",&n,&m)!=EOF&&!(n==0&&m==0))  
  25.     {  
  26.         memset(tree,'-',sizeof(char)*2*('Z'+10));  
  27.         for(i=0;i<n;i++)  
  28.         {  
  29.             cin>>str;  
  30.             tree[str[0]][0]=str[1];  
  31.             tree[str[0]][1]=str[2];  
  32.         }  
  33.         for(i=0;i<m;i++)  
  34.         {  
  35.             cin>>str;  
  36.             int level1=Dfs(str[0],str[1],0);  
  37.             int level2=Dfs(str[1],str[0],0);  
  38.             int level=level1>=INF?-level2:level1;  
  39.             if(abs(level)>=INF)  
  40.             {  
  41.                 printf("-\n");  
  42.                 continue;  
  43.                 }  
  44.             while (level++<-2)  
  45.                 printf("great-");  
  46.             level--;  
  47.             if(level==-1)  
  48.                 printf("parent\n");  
  49.             else if(level==-2)  
  50.                 printf("grandparent\n");  
  51.   
  52.             while (level-->2)  
  53.                 printf("great-");  
  54.             level++;  
  55.             if (level==2)  
  56.                 printf("grandchild\n");  
  57.             else if(level==1)  
  58.                 printf("child\n");  
  59.         }  
  60.     }  
  61. }