第十二届蓝桥杯大赛省赛赛题C++大学C组

试题A：约数个数 问题描述

  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？

算法设计

  读入字符，输出格式为数值。

#includeint main(){ using namespace std; char ch; scanf("%c",&ch); printf("%d",ch);}

输入：

L

输出：

75

试题B：空间 问题描述

  小蓝准备用256MB的内存空间开一个数组，数组的每个元素都是32位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256MB的空间可以存储多少个32位二进制整数

算法设计

  先将MB转换为字节Byte，然后进行除法运算

#includeint main(){ using namespace std; int cs = 256 * 1024 * 1024 / 4; cout << cs;}

输出：

67108864

试题C：卡片 问题描述

  小蓝有很多数字卡片，每张卡片上都是数字0到9。
  小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，没拼一个，就保持起来，卡片就不能用来拼其他数了。
  小蓝想知道自己能从1拼到多少。
  例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10，但是拼11时卡片1已经只有一张了，不够拼出11。
  现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少。

算法设计

  可以发现数字1是最先用完的，使用while循环，找到第2021张数字1。

#includeint main(){ using namespace std; int k = 1; int count = 0; while(k){ int temp = k; while(temp){ int x = temp % 10; temp = temp /10; if(x == 1){ count++; } } if(count >= 2021){ break; } else{ k++; } } cout << k;}

输出：

3181

试题D：相乘 问题描述

  小蓝发现，他将1至1000000007之间的不同的数与2021相乘后再除以1000000007的余数，会得到不同的数。
  小蓝想知道，能不能再1至1000000007之间找到一个数，与2021相乘后再除以1000000007后的余数为999999999。如果存在，请在答案中提交这个数；如果不存在，请在答案中提交0。

算法设计

  按照题目意思，数字i为1~1000000007间整数， i × 2021 1000000007 frac{i times 2021}{1000000007} 1000000007i×2021​取余为999999999。

#includeint main(){ using namespace std; for (long long int i = 1; i <= 1000000007; ++i) { if(i * 2021 % 1000000007 == 999999999){ cout << i << endl; break; } } return 0;}

输出：

17812964

试题E：路径 问题描述

  小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
  小蓝的图由2021个结点组成，依次编号1至2021。
  对于两个不同的结点 a a a, b b b，如果 a a a和 b b b的差的绝对值大于21，则两个结点之间没有边相连；如果 a a a和 b b b的差的绝对值小于等于21，则两个点之间有一条长度为 a a a和 b b b的最小公倍数的无向边相连。
  例如：结点1和节点23之间没有边相连；结点3和结点24之间有一条无向边，长度为24；节点15和结点25之间有一条无向边，长度为75。
  请计算，结点1和结点2021之间的最短路径长度是多少？

算法设计

  使用dijkstra算法求最短路径

#include#include#includeusing namespace std;typedef long long ll;const int Max = 1e6 + 5;int u[Max], v[Max], w[Max];int g = 0, first[Max], nex[Max];struct node{int n, w;bool operator<(const node& a)const{return w > a.w;}node(int a, int b){n = a;w = b;}};ll dis[Max], b[Max];priority_queue que;void add(int a, int b,int c){u[++g] = a;v[g] = b;w[g] = c;nex[g] = first[a];first[a] = g;}ll gcd(ll a, ll b){if (a == 0)return b;return gcd(b%a, a);}ll lcm(ll a, ll b){return a * b / gcd(a, b);}int main(){memset(first, -1, sizeof(first));memset(dis, 0x7f, sizeof(dis));for (int i = 1;i <= 2021;i++){for (int j = i + 1;j - i <= 21 && j <= 2021;j++){add(i, j, lcm(i, j));add(j, i, lcm(i, j));}}que.push(node(1,0));dis[1] = 0;while(!que.empty()){node no = que.top();que.pop();if (b[no.n])continue;dis[no.n] = no.w;b[no.n] = 1;for (int i = first[no.n];i != -1;i = nex[i]){if (b[v[i]])continue;if (dis[u[i]] + w[i] < dis[v[i]]){dis[v[i]] = dis[u[i]] + w[i];que.push(node(v[i],dis[u[i]]+w[i]));}}}cout << dis[2021];}

输出：

10266837

试题F：时间显示 问题描述

  小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日00:00:00到当前时刻经过的毫秒数。
  现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
  给定一个整数表示的时间，请将这个时间对应的时分秒输出。

输入格式

  输入一行包含一个整数，表示时间。

输出格式

  输出时分秒表示的当前时间，格式形如HH:MM:SS，其中HH表示时，值为0到23，MM表示分，值为0到59，SS表示秒，值为0到59。时、分、秒不足两位时补前导0。

算法设计

  首先将毫秒转换为秒，1毫秒 = 0.001秒，秒/(6060)得到总小时数，由于不需要显示天数，再除以24取余，得到当天小时数。秒/(6060)取余，得到当天分钟总秒数，再除以60得到总分钟。秒/(60*60)取余，得到当天分钟总秒数，再除以60取余得到秒数。

#includeint main(){ using namespace std; long long int n,t,h,m,s; scanf("%lld",&n); t = n / 1000;//计算秒 h = t / 3600 % 24; //计算总小时数 m = (t % 3600) / 60; //对秒求余 s = (t % 3600) % 60; printf("%02lld:%02lld:%02lld",h,m,s); return 0;}

输入：

46800999

输出：

13:00:00

试题G：最少砝码 问题描述

  你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于 N N N的正整数重量。
  那么这套砝码最少需要包含多少个砝码？
  注意砝码可以放在天平两边。

输入格式

  输入包含一个正整数 N N N。

输出格式

  输出一个整数代表答案。

算法设计

用贪心的思想来解决这个问题：尽可能在增加砝码时使得砝码的重量最大。
要称重量为 1，需要砝码 1
重量为 2，增加砝码 3（使增加的砝码尽可能的大，所以不是 1 和 2 ）
1 3 可以同时称 ‘1’=1，‘2’+1=3，‘3’=3，‘4’=3+1 ；
所以下一个是5，增加砝码 9（尽可能的大）
1 3 9 可以同时称（除去 1 和 3 能称的）：
‘5’+3+1=9，‘6’+3=9，‘7’+3=9+1，‘8’+1=9，‘9’=9
‘10’=9+1，‘11’+1=9+3，‘12’=9+3，‘13’=1+3+9

#include using namespace std;int main(void){ int n; cin >> n; int weight = 1; int count = 1; int total = 1; while (total < n){ count++; weight *= 3; total += weight; } cout << count << endl; return 0;}

输入：

7

输出：

3