1.试题 A: 空间

本题总分：5 分
【问题描述】
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

存储单元进制转换
1B=1Byte=8bit（1Byte就是一个字节，一个字节有8bit（位））（0000 0000）
1KB=1024B
1MB=1024KB
1GB=1024MB
1TB=1024GB
**
数组的每个元素是32位的二进制数（32bit）

  1. 一种思路

256MB = 25610241024*8bit=2147483648bit
那么可开数组的个数为：2147483648/32=67108864（个）
（用c++程序运算注意要使用long long，建议直接用系统计算器）

  1. 另一种思路

32bit=4B
那么可开数组的个数为：25610241024/4=67108864（个）

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. int main(){
  6.     cout<<256*1024*1024/4<<endl;
  7.     return 0;
  8. } 
  10. //答案：67108864

2.试题 B: 卡片

本题总分：5 分
【问题描述】
小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。
小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。
小蓝想知道自己能从 1 拼到多少。
例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. int s[10];//存剩余卡片数量
  6. bool check(int n){
  7.     while(n){
  8.         int t=n%10;
  9.         n/=10;
  10.         if(--s[t]<0) return 1;
  11.     }
  12.     return 0;
  13. }
  14. int main(){
  15.     for(int i=0;i<10;i++) s[i]=2021;
  16.     for(int i=1;;i++){
  17.         if(check(i)){
  18.             cout<<i-1<<endl;
  19.             return 0;
  20.         }
  21.     }
  22.     return 0;
  23. }
  24. //答案：3181

3.试题 C: 直线

本题总分：10 分
【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上， 那么这些点中任意两点确定的直线是同一条。
给定平面上 2 × 3 个整点 {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标 是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数 的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21 个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横 坐标是 0 到 19 (包含 0 和 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之 间的整数的点。请问这些点一共确定了多少条不同的直线。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6. const int MAXN=200000;
  7. int n=0;
  8. typedef struct{
  9.     double k,b;
  10. }Line;
  11. Line l[MAXN];
  12. bool cmp(Line x,Line y){
  13.     if(x.k!=y.k) return x.k<y.k;
  14.     return x.b<y.b;
  15. }
  16. int main(){
  17.     for(int x1=0;x1<20;x1++){
  18.         for(int y1=0;y1<21;y1++){
  19.             for(int x2=0;x2<20;x2++){
  20.                 for(int y2=0;y2<21;y2++){
  21.                     if(x1!=x2){
  22.                         double k=(double)(y2-y1)/(x2-x1);
  23.                         double b=y1-k*x1;
  24.                         l[n].k=k;
  25.                         l[n++].b=b;
  26.                     }
  27.                 }
  28.             }
  29.         }
  30.     }
  31.     sort(l,l+n,cmp);
  32.     int ans=1;//i从1开始，所以不同k，b的数对初始为1 
  33.     for(int i=1;i<n;i++){ //上面公式的计算，由于数的计算顺序不同，可能存在精度问题，判断两个double是否相同，常用的方法是看差值是否在1e-8
  34.         if(fabs(l[i].k-l[i-1].k)>1e-8||fabs(l[i].b-l[i-1].b)>1e-8){//精度问题，我们定义如果两个数对之间，k或b相差的绝对值大于1e-8，可以说是两个不同的直线
  35.             ans++;
  36.         }
  37.     }
  38.     cout<<ans+20;
  39.     return 0; 
  40. }
  41. //答案：40257

4.试题 D: 货物摆放

本题总分：10 分
【问题描述】
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝 规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、 宽、高。
小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上 分别堆 L、W、H 的货物，满足 n = L × W × H。
给定 n，请问有多少种堆放货物的方案满足要求。
例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1。
请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种 方案？ 提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

  1. //如果三个数相乘能得到n，这三个是必为n的约数，我们可以先求n的约数，再进行枚举可以优化时间
  2. //由于不知道约数有多少个，用vector存，下面也有用数组存的方法
  3. #include<iostream>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<vector>
  7. using namespace std;
  8. typedef long long ll;
  9. vector<ll> v;
  10. int main(){
  11.     ll n=2021041820210418;
  12.     for(ll i=1;i*i<=n;i++){
  13.         if(n%i==0){
  14.             v.push_back(i);
  15.             if(n/i!=i) v.push_back(n/i);
  16.         }
  17.     }
  18.     int ans=0;
  19.     for(vector<ll>::iterator x=v.begin();x!=v.end();x++){
  20.         for(vector<ll>::iterator y=v.begin();y!=v.end();y++){
  21.             for(vector<ll>::iterator z=v.begin();z!=v.end();z++){
  22.                 if(*x*(*y)*(*z)==n){
  23.                     //cout<<*x<<' '<<*y<<' '<<*z<<endl;
  24.                     ans++;
  25.                 }
  26.             }
  27.         }
  28.     }
  29.     cout<<ans;
  30.     return 0;
  31. }
  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. ll a[100000];
  7. int k;
  8. int main(){
  9.     ll n=2021041820210418;
  10.     for(ll i=1;i*i<=n;i++){
  11.         if(n%i==0){
  12.             a[k++]=i;
  13.             if(n/i!=i) a[k++]=n/i;
  14.         }
  15.     }
  16.     int ans=0;
  17.     for(ll x=0;x<k;x++){
  18.         for(ll y=0;y<k;y++){
  19.             for(ll z=0;z<k;z++){
  20.                 if(a[x]*a[y]*a[z]==n){
  21.                     ans++;
  22.                 }
  23.             }
  24.         }
  25.     }
  26.     //cout<<k<<endl;//k只有128个，不会超出数组大小 
  27.     cout<<ans;
  28.     return 0;
  29. }
  30. //答案：2430

5.试题 E: 路径

本题总分：15 分
【问题描述】
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

  1. //这是比赛时候写的，复杂度O(n^3),太慢了，一分钟左右出结果吧，还是单源最短路径算法快，但是这个写的快
  2. //由于是填空题，那么这个算法是最快写出来的，让他跑就行了，但是学习算法还是要学快的，这题是感觉是最不用思考的题了
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6. const int inf=999999999;//定义一个很大的数，表示不可达的边
  7. int v[2050][2050];
  8. const int m=2021;
  9. void inti(){
  10.     for(int i=1;i<=2021;i++){
  11.         for(int j=1;j<=2021;j++){
  12.             v[i][j]=inf;
  13.             if(i==j){
  14.                 v[i][j]=0;
  15.             }
  16.         }
  17.     }
  18. }
  19. int main(){
  20.     inti();//初始化边
  21.     //根据题意求边
  22.     for(int i=1;i<=m;i++){
  23.         for(int j=i+1;j<=m&&j<=i+21;j++){//在这个区间内的要计算gcd然后为边 
  24.             int lc=i/__gcd(i,j)*j;
  25.             v[i][j]=lc;
  26.             v[j][i]=lc;
  27.         }
  28.     }
  29.     //floyd核心算法
  30.     for(int k=1;k<=m;k++){
  31.         for(int i=1;i<=m;i++){
  32.             for(int j=1;j<=m;j++){
  33.                 if(v[i][j]>v[i][k]+v[k][j]){
  34.                     v[i][j]=v[i][k]+v[k][j];
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     cout<<v[1][m];//输出1到m的距离
  40.     return 0;
  41. }
  42. //答案：10266837
  1. //spfa算法可求单源最短路径，贝尔曼-福特算法的队列优化形式，通常用于求含负权边的单源最短路径，以及判负权环。
  2. //学了之后敲上来

6.试题 F: 时间显示

时间限制: 1.0s 内存限制: 256.0MB
本题总分：15 分
【问题描述】
小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取 了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日 00:00:00 到当前时 刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要 显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
【输入格式】
输入一行包含一个整数，表示时间。
【输出格式】
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值 为 0 到 23，MM 表示分，值为 0 到 59，SS 表示秒，值为 0 到 59。时、分、秒 不足两位时补前导 0。
【样例输入 1】
46800999
【样例输出 1】
13:00:00
【样例输入 2】
1618708103123
【样例输出 2】
01:08:23
【评测用例规模与约定】
对于所有评测用例，给定的时间为不超过 10 的正整数。

  1. //AC代码
  2. #include<iostream>
  3. #include<cstdio>
  4. using namespace std;
  5. int main(){
  6.     long long n;
  7.     cin>>n;
  8.     int hh,mm,ss;
  9.     n/=1000;//1s=1000ms
  10.     ss=n%60;
  11.     n/=60;
  12.     mm=n%60;
  13.     n/=60;
  14.     hh=n%24;
  15.     printf("%02d:%02d:%02d",hh,mm,ss);
  16.     return 0;
  17. }
  1. //AC代码//虽然代码长但是时间复杂度不高，多此一举
  2. //基础没学好，比赛的时候写完上面的代码之后，看到数据范围是10^18，以为long long存不了，写了下面用字符串模拟模运算的过程，浪费时间气死，但是代码能过！
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cstdio>
  6. #include<cstring>
  7. using namespace std;
  8. char s[100];
  9. int fn(){
  10.     int sum=0;
  11.     int l=strlen(s);
  12.     l-=3;
  13.     int k=0;
  14.     while(k<l){
  15.         while(sum<86400&&k<l){
  16.             sum=sum*10+(s[k++]-'0');
  17.         }
  18.         sum%=86400;
  19.     }
  20.     sum%=86400;
  21.     sum/=3600;
  22.     return sum;
  23. }
  24. int fm(){
  25.     int sum=0;
  26.     int l=strlen(s);
  27.     l-=3;
  28.     int k=0;
  29.     while(k<l){
  30.         while(sum<86400&&k<l){
  31.             sum=sum*10+(s[k++]-'0');
  32.         }
  33.         sum%=86400;
  34.     }
  35.     sum/=60;
  36.     sum%=60;
  37.     return sum;
  38. }
  39. int fs(){
  40.     int sum=0;
  41.     int l=strlen(s);
  42.     l-=3;
  43.     int k=0;
  44.     while(k<l){
  45.         while(sum<60&&k<l){
  46.             sum=sum*10+(s[k++]-'0');
  47.         }
  48.         sum%=60;
  49.     }
  50.     return sum;
  51. }
  52. int main(){
  53.     cin>>s;
  54.     printf("%02d:%02d:%02d",fn(),fm(),fs());
  55.     return 0;
  56. }

7.试题 G: 砝码称重

时间限制: 1.0s 内存限制: 256.0MB
本题总分：20 分
【问题描述】
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。
【输入格式】
输入的第一行包含一个整数 N。
第二行包含 N 个整数：W1, W2, W3, · · · , WN。
【输出格式】
输出一个整数代表答案。
【样例输入】
3 1 4 6
【样例输出】
10
【样例说明】
能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。
1 = 1；
2 = 6 − 4 (天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
9 = 4 + 6 − 1；
10 = 4 + 6；
11 = 1 + 4 + 6。
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

  1. //比赛时候的代码，不会背包所以写了个dfs，好像只能过个30%。//学完背包再写
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<set>
  5. using namespace std;
  6. set<int> v;
  7. int n;
  8. int a[1000],vis[1000];
  9. void dfs(int sum,int l){
  10.     if(l==n){
  11.         if(sum>=1)
  12.         v.insert(sum);
  13.         return ;
  14.     }
  15.     for(int i=0;i<=2*n;i++){
  16.         if(!vis[i]){
  17.             if(i!=0)
  18.             vis[i]=1;
  19.             dfs(sum+a[i],l+1);
  20.             vis[i]=0;
  21.         }
  22.     }
  23.     return ;
  24. }
  25. int main(){
  26.     int x;
  27.     cin>>n;
  28.     for(int i=1;i<=n;i++){
  29.         cin>>x;
  30.         a[i]=x;
  31.         a[i+n]=-1*x;//有三种情况，+wi（放一边），-wi（放另一边），0（不放）
  32.     }
  33.     dfs(0,0);
  34.     cout<<v.size();
  35.     return 0;
  36. }