蓝桥杯练习（二）

女爷i 2023-05-28 05:21 67阅读 0赞

蓝桥杯练习（二）

      • 阶乘计算
      • 高精度加法
      • Huffuman树
      • 2n皇后问题
      • 报时助手
      • 回形取数
      • 龟兔赛跑预测
      • 时间转换
      • 字符串对比
      • FJ的字符串
      • 参考博客

阶乘计算

问题描述
　　输入一个正整数n，输出n!的值。
输入格式
　　输入包含一个正整数n，n<=1000。
加粗样式输出格式
　　输出n!的准确值。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e4;
  4. int a[maxn]={ 1};
  5. int main(){ 
  6.     int n,d,t=1;
  7.     scanf("%d",&n);
  8.     for(int i=2;i<=n;++i){ 
  9.         d=0;
  10.         for(int j=0;j<t;++j){ 
  11.             a[j]=a[j]*i+d;
  12.             d=a[j]/10;
  13.             a[j]%=10;
  14.         }
  15.         while(d){ 
  16.             a[t++]=d%10;
  17.             d/=10;
  18.         }
  19.     }
  20.     //printf("%d",t);
  21.     for(int i=t-1;i>=0;--i)printf("%d",a[i]);
  22. }

高精度加法

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 1e2+1;
  4. int a[maxn]={ 0};
  5. int b[maxn]={ 0};
  7. void transfer(string &s,int c[]){ 
  8.     int t=0;
  9.     for(int i=s.size()-1;i>=0;--i){ 
  10.         c[t++]=s[i]-'0';
  11.     }
  12. }
  14. int main(){ 
  15.    string s;
  16.    cin>>s;
  17.    transfer(s,a);
  18.    cin>>s;
  19.    transfer(s,b);
  20.    int d=0;
  21.    for(int i=0;i<maxn;++i){ 
  22.        a[i]+=b[i]+d;
  23.        if(a[i]>9){ 
  24.            a[i]-=10;
  25.            d=1;
  26.        }else d=0;
  27.    }
  28.    for(int i=maxn-1;i>0;--i){ 
  29.        if(a[i]!=0){ 
  30.            for(int t=i;t>=0;--t){ 
  31.                cout<<a[t];
  32.            }
  33.            return 0;
  34.        }
  35.    }
  36.    cout<<0;
  37.    return 0;
  38. }

Huffuman树

问题描述
　　Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
　　给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
　　1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi} 中。这个过程的费用记为pa + pb。
　　2. 重复步骤1，直到{pi}中只剩下一个数。
　　在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
　　本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。
输入格式
　　输入的第一行包含一个正整数n（n<=100）。
　　接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main(){ 
  5.     priority_queue<int,vector<int>,greater<int> > q;
  6.     int n,d;
  7.     scanf("%d",&n);
  8.     for(int i=0;i<n;++i){ 
  9.         scanf("%d",&d);
  10.         q.push(d);
  11.     }
  12.     int sum = 0;
  13.     while(q.size()>1){ 
  14.         d = q.top();q.pop();
  15.         d+=q.top();q.pop();
  16.         sum+=d;
  17.         //printf("%d ",d);
  18.         q.push(d);
  19.     }
  20.     printf("%d",sum);
  21. }

2n皇后问题

问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 10;
  4. int g[maxn][maxn];// 1 可以放，0 不可以放 2，黑，3 白
  5. int n,ans;
  6. int row1[maxn];
  7. int row2[maxn];
  9. bool check(int t,int col,int row[]){ 
  10.     for(int i=0;i<t;++i)
  11.         if(row[i]==col||abs(i-t)==abs(row[i]-col))
  12.             return false;
  14.     return true;
  15. }
  17. void dfs(int i,int j,int row[]){ 
  18.     if(i==n&&3==j){ 
  19.         ans++;
  20.         return;
  21.     }
  22.     if(i==n&&j==2){ 
  23.         dfs(0,3,row2);
  24.     }
  25.     for(int t=0;t<n;++t){ 
  26.         if(g[i][t]==1&&check(i,t,row)){ 
  27.             row[i]=t;
  28.             g[i][t]=j;
  29.             dfs(i+1,j,row);
  30.             g[i][t]=1;
  31.         }
  32.     }
  33. }
  35. int main(){ 
  36.     scanf("%d",&n);
  37.     for(int i=0;i<n;++i){ 
  38.         for(int j=0;j<n;++j)scanf("%d",&g[i][j]);
  39.     }
  40.     dfs(0,2,row1);
  41.     printf("%d",ans);
  42.     return 0;
  43. }

报时助手

问题描述
　　给定当前的时间，请用英文的读法将它读出来。
　　时间用时h和分m表示，在英文的读法中，读一个时间的方法是：
　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“three o’clock”。
　　如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。
　　时和分的读法使用的是英文数字的读法，其中0~20读作：
　　0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
　　30读作thirty，40读作forty，50读作fifty。
　　对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30再加1的读法，读作“thirty one”。
　　按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15读作“zero fifteen”。
输入格式
　　输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. string msg[] ={ "zero","one","two","three","four","five","six","seven",
  5. "eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen",
  6. "sixteen","seventeen","eighteen","nineteen","twenty"};
  8. int main(){ 
  9.     int h,m;
  10.     cin>>h>>m;
  11.      if(h<21)cout<<msg[h];
  12.      else  cout<<msg[20]<<" "<<msg[h-20];
  13.     if(m==0){ 
  14.         cout<<" o'clock";
  15.     }else{ 
  16.         cout<<" ";
  17.         if(m<21)cout<<msg[m];
  18.         else if(m<30)cout<<msg[20]<<" "<<msg[m-20];
  19.         else if(m==30)cout<<"thirty";
  20.         else if(m<40)cout<<"thirty"<<" "<<msg[m-30];
  21.         else if(m==40)cout<<"forty";
  22.         else if(m<50)cout<<"forty"<<" "<<msg[m-40];
  23.         else if(m==50)cout<<"fifty";
  24.         else cout<<"fifty "<<msg[m-50];
  25.     }
  26. }

回形取数

问题描述
　　回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入格式
　　输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 202;
  5. int a[MAXN][MAXN];
  6. int n,m;
  7. int main(){ 
  8.     scanf("%d%d",&n,&m);
  9.     for(int i=0;i<n;++i){ 
  10.         for(int j=0;j<m;++j){ 
  11.             scanf("%d",&a[i][j]);
  12.         }
  13.     }
  14.     int l=0,r=m-1,t=0,d=n-1;
  15.     vector<int> ans;
  16.     while(l<=r&&t<=d){ 
  17.         for(int i=t;i<=d;++i)ans.push_back(a[i][l]);
  18.         l++;
  19.         if(ans.size()==n*m)break;
  20.         for(int i=l;i<=r;++i)ans.push_back(a[d][i]);
  21.         d--;
  22.         if(ans.size()==n*m)break;
  23.         for(int i=d;i>=t;--i)ans.push_back(a[i][r]);
  24.         r--;
  25.         if(ans.size()==n*m)break;
  26.         for(int i=r;i>=l;--i)ans.push_back(a[t][i]);
  27.         t++;
  28.         if(ans.size()==n*m)break;
  29.     }
  30.     for(int i=0;i<ans.size()-1;++i)printf("%d ",ans[i]);
  31.     printf("%d",ans[ans.size()-1]);
  32. }

龟兔赛跑预测

问题描述
　　话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，但是所有的乌龟却是一致——它们不到终点决不停止。
　　然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛的结果。
输入格式
　　输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main(){ 
  5.     int v1,v2,t,s,l;
  6.     scanf("%d%d%d%d%d",&v1,&v2,&t,&s,&l);
  7.     int l1=0,l2=0;//兔子，乌龟跑过的距离
  8.     int flag=false;//兔子是否在休息
  9.     int d;//兔子休息时长
  10.     int cnt=0;//消耗时长
  11.     while(true){ 
  12.         cnt++;
  13.         if(flag){ 
  14.             d++;
  15.             if(d==s)flag=false;
  16.         }else l1+=v1;
  17.         l2+=v2;
  18.         //printf("%d %d %d %d\n",cnt,d,l1,l2);
  19.         if(l1==l&&l1==l2){ 
  20.             printf("D");
  21.             break;
  22.         }else if(l1==l){ 
  23.             printf("R");
  24.             break;
  25.         }else if(l2==l){ 
  26.             printf("T");
  27.             break;
  28.         }
  29.         if(l1-l2>=t&&flag==false){ 
  30.             flag=true;
  31.             d=0;
  32.         }
  33.     }
  34.     printf("\n%d",cnt);
  35.     return 0;
  36. }

时间转换

问题描述
　　给定一个以秒为单位的时间t，要求用“::”的格式来表示这个时间。表示时间，表示分钟，而表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。
输入格式
　　输入只有一行，是一个整数t（0<=t<=86399）。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main(){ 
  5.     int n;
  6.     cin>>n;
  7.     printf("%d:%d:%d",n/3600,n%3600/60,n%60);
  8.     return 0;
  9. }

字符串对比

问题描述
　　给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：
　　1：两个字符串长度不等。比如 Beijing 和 Hebei
　　2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
　　3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
　　4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
　　编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入格式
　　包括两行，每行都是一个字符串

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. char toLower(char c){ 
  5.     if(c<='Z')c+=32;
  6.     return c;
  7. }
  8. int stringCmp(string &s1, string &s2){ 
  9.     for(int i=0;i<s1.size();++i){ 
  10.         if(toLower(s1[i])!=toLower(s2[i]))return 4;
  11.     }
  12.     return 3;
  13. }
  15. int main(){ 
  16.     string s1,s2;
  17.     cin>>s1>>s2;
  18.     if(s1.size()!=s2.size())cout<<1;
  19.     else{ 
  20.         if(s1==s2)cout<<2;
  21.         else cout<<stringCmp(s1,s2);
  22.     }
  23.     return 0;
  24. }

FJ的字符串

问题描述
　　FJ在沙盘上写了这样一些字符串：
　　A1 = “A”
　　A2 = “ABA”
　　A3 = “ABACABA”
　　A4 = “ABACABADABACABA”
　　… …
　　你能找出其中的规律并写所有的数列AN吗？
输入格式
　　仅有一个数：N ≤ 26。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main(){ 
  5.     string s = "A";
  6.     int n;
  7.     cin>>n;
  8.     for(int i=1;i<n;++i){ 
  9.         s = s + char('A'+i)+s;
  10.     }
  11.     cout<<s;
  12. }

参考博客

蓝桥杯练习（一）

发表评论

表情：
评论列表 （有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读