蓝桥杯十二到十五届B，C++组签到题

前言

本人是双非科班大一，马上第一次参加蓝桥杯，在参加之前只接触了三个月左右的算法，还是个蒟蒻，斗胆写下一些自己写真题的感受与方法，如有不对请指正。
第十二届

空间

作为B组的签到题，此题主要考基础知识，似乎从来没有这么考过。直接盘算即可
256 * 1024 * 1024 * 8 / 32
卡片

蓝桥杯官网给出的第二题是此题，似乎另有另一道

此题就是个数学问题，直接列几个n盘算找规律即可

1. #include <iostream>
2. #include <cmath>
3. using namespace std;
5. int main() {
6.     long long n;
7.     cin >> n;
8.     long long x = 8 * n + 1;
9.     double s = sqrt(x);
10.     long long k = (s - 1) / 2;
11.     if (k * (k + 1) / 2 >= n) {
12.         cout << k << endl;
13.     } else {
14.         cout << k + 1 << endl;
15.     }
16.     return 0;
17. }

复制代码

直线

此题由于数据较小可以直接暴力罗列所有的情况进行判定，起首需要清除横着的线与竖着的线，即两个点确定的直线的斜率存在且不为0的情况。
为什么要先清除掉呢，主要是因为我们是找到两个点之后，先盘算斜率k，再盘算截距b，假如出现上述情况，就会出现分母为0的情况。
这里的别的一个问题就是由于我们的k与b是double范例的，又因为double范例在进行除法时很容易会出现精度错误导致盘算堕落，所以盘算的b的时候不能直接利用先算出来的k进行盘算，需要转换为b = (y2 * (x2 - x1) - (y2 - y1) * x2) * 1.0 / (x2 - x1)（就是两点式）。
由于会出现重复直线的问题，所以这里利用容器set来进行自动去重
详细代码如下

1. #include <iostream>
2. #include<set>
3. using namespace std;
4. set<pair<double,double>>line_set;
5. int main()
6. {
7.     double k = 0;
8.     double b = 0;
9.   // 请在此输入您的代码
10.   for(int x1 = 0;x1 < 20;x1 ++)
11.     for(int y1 = 0;y1 < 21;y1++)
12.         for(int x2 = 0;x2 < 20;x2 ++)
13.             for(int y2 = 0;y2 < 21;y2++)
14.             {
15.                 if(x2 != x1 && y1 != y2)
16.                 {
17.                     k = (y2 - y1) * 1.0 / (x2 - x1);
18.                     b = (y2 * (x2 - x1) - (y2 - y1) * x2) * 1.0 / (x2 - x1);//出现double除法会出现精度问题，
19.                     line_set.insert({k,b});
20.                 }
21.             }
22.     printf("%zd",line_set.size() + 20 + 21);
23.   return 0;
24. }

复制代码

货品摆放

题目固然我没有怎么读懂_(:з」∠)_ ，但是我看懂了他举的例子，就是找到给出的n的三个因子然后进行排列，盘算因子我们都知道怎么盘算，但是找到三个因子就可能不知道了。
这时牢记正难则反，我们从反面思考，我们要找到该数的三个因子，使得这三个因子相乘就是该数本身，我们得先预处理一下该数的所有因子，假如我们先锁定该数的两个因子，然后遍历所有的因子找到一个因子使得锁定的两个因子乘上找到的因子是否等于该数即可。
但是这样子相当于要嵌套三层循环，时间复杂度度过高，对他进行一个优化变成两重循环。我们仍然是锁定两个因子，然后假如n%这俩因子相乘等于0的话，那就说明这一组是我们的答案。因为假如n能整除这俩因子的乘积，那就说明整除的商也是n的一个因子，那么我们就找到了三个因子相乘等于n了。
详细代码如下

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. long long yue[1000010];
5. int main()
6. {
7.         //先把约数提前处理，然后遍历约数相乘
8.         long long n = 2021041820210418;
9.         int cnt = 0;
10.         for (int i = 1; i <= n / i; i++)
11.         {
12.                 if (n % i == 0)
13.                 {
14.                         yue[++cnt] = i;
15.                         if (i != n / i)
16.                         {
17.                                 yue[++cnt] = n / i;
18.                         }
19.                 }
20.         }
21.         int ans = 0;
22.         for(int i = 1;i <= cnt;i++)
23.                 for (int j = 1; j <= cnt; j++)
24.                 {
25.                         if (n % (yue[i] * yue[j]) == 0)
26.                                 ans++;
27.                 }
28.         cout << ans;
29. }

复制代码

路径

这个题就是个模版题，幸好学了最短路，固然模版已经忘了_(:з」∠)_也借此复习了一下最短路问题，这个题只要知道最短路的几种算法都可以完成。
这里需要提一下，可能有人不知道最小公倍数怎么盘算，就是先找出最大公约数，然后两数相乘再除以最大公约数即可，最大公约数就是辗转相除法。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int g[2500][2500];
4. int d[2500];
5. bool st[2500];
6. int gcd(int a,int b)//先找最大公约数
7. {
8.     return b ? gcd(b,a % b) : a;
9. }
10. int lcm(int a,int b)//再找最小公倍数
11. {
12.     return a * b / gcd(a,b);
13. }
14. int dijkstra()
15. {
16.     memset(d,0x3f,sizeof d);
17.     d[1] = 0;
18.     for(int i = 1;i <= 2021;i++)
19.     {
20.         int t = -1;
21.         for(int j = 1;j <= 2021;j++)
22.         {
23.             if(!st[j] && (t == -1 || d[j] < d[t]))
24.             t = j;
25.         }//找到距离起点最近的点t
26.         st[t] = true;
27.         for(int j = 1;j <= 2021;j++)
28.         {
29.             d[j] = min(d[j],d[t] + g[t][j]);
30.         }
31.     }
32.     return d[2021];
33. }
34. int main()
35. {
36.   for(int i = 1;i <= 2021;i++)
37.     for(int j = 1;j <= 2021;j++)
38.     {
39.         if(i != j)
40.         {
41.             if(fabs(i - j) <= 21)
42.             {
43.                  g[i][j] = g[j][i] = lcm(i,j);
44.             }
45.             else
46.             {
47.              g[i][j] = g[j][i] = 0x3f3f3f3f;
48.             }
50.         }
51.         
52.     }//处理数据
53.     cout << dijkstra();
54.   return 0;
55. }

复制代码

时间显示

蓝桥杯似乎每一届都有关于日期的问题，所有我们得牢记闰年的盘算方法（固然这题没考闰年）即被4整除而且不被100整除大概被400整除。这道题就直接根据题目模拟即可
详细代码如下

1. #include <iostream>
2. using namespace std;
3. typedef long long ll;
4. int main()
5. {
6.   // 请在此输入您的代码
7.   ll n;
8.   cin >> n;
9.   n /= 1000;
10.   int h = n / 3600 % 24;
11.   n %= 3600;
12.   int m = n / 60 % 60;
13.   n %= 60;
14.   printf("%02d:%02d:%02d",h,m,n);
15.   return 0;
16. }

复制代码

第十三届

九进制转十进制

就直接按照进制转换做即可

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
6.   cout << 2 * pow(9,0) + 2 * pow(9,1) + 2 * pow(9,3);
7.   return 0;
8. }

复制代码

顺子日期

依然是蓝桥杯喜好考的日期问题，我们只需要判定mmdd是不是顺子就行
详细代码如下

1. #include <iostream>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
7.   int month[13] ={0,31,28,31,30,31,30,31,31,30,31,30,31};
8.   //mmdd只需要判断mmdd是不是顺子就行
9.   int m = 1;
11.   int ans = 0;
12.   while(m <= 12)
13.   {
14.       int day = month[m];
15.       for(int i = 1;i < day;i++)
16.       {
17.         int a = m / 10,b = m % 10,c = i / 10,d = i % 10;
18.         if(a == b - 1 && b == c - 1)
19.         {
20.           ans++;
21.         }
22.         if(b == c - 1 && c == d - 1)
23.         ans++;
24.     }
25.      m++;
27.   }
28.   cout << ans;
29.   return 0;
30. }

复制代码

刷题统计

这个问题留意是1e18，所以是需要开long long的(#define int long long的含金量还在上升 )，我没开long long就只过了50%的样例
我们需要先算出要多少周，在盘算剩下的题目需要多少天。
详细代码如下

1. #include <iostream>
2. using namespace std;
3. typedef long long ll;
4. int main()
5. {
6.   // 请在此输入您的代码
7.   ll a,b,n;
8.   cin >> a >> b >> n;
9.   ll t = n / (a * 5 + b * 2);//先算周
10.   ll s = n % (a * 5 + b * 2);//剩下的
11.   ll ans = t * 7;
12.   for(int i = 1;s > 0 && i <= 7; i++)
13.   {
14.       if(i == 6 || i == 7)
15.       {
16.           s -= b;
17.           ans++;
18.       }
19.       else
20.       {
21.           s -= a;
22.           ans++;
23.       }
24.   }
25.   cout << ans;
26.   return 0;
27. }

复制代码

修剪灌木

这个题目固然看着很长，但是在纸上画绘图模拟一遍就出来了，第i棵灌木的最长长度就是i与n-i-1取最大值然后乘上2，乘2是因为往返。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
6.   int n;
7.   cin >> n;
8.   for(int i = 0;i < n;i++)
9.   {
10.       cout << max(i,n - i - 1) * 2 << endl;
11.   }
12.   return 0;
13. }

复制代码

第十四届

日期统计

这道题初看我没有任何思绪，以至于我以为需要使用八重循环来遍历所有情况，随后我换了中角度思考，我之前以为要进行八重循环是从给定的数组中找日期，那么为什么不遍历2023年所有的日期然后在数组中寻找呢，所以思绪就是先找到2023年所有的正当日期，2023是个平年，所以不用管2月，然后找到数组中是否有着对应的子序列
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
6.   int num[100]={5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,
7. 7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,
8. 0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3};
9. int month[13] ={0,31,28,31,30,31,30,31,31,30,31,30,31};
10.     //遍历2023的所有合法日期
11.     int ans = 0;
12.     for(int m = 1;m <= 12;m++)
13.     {
14.         for(int j = 1;j <= month[m];j++)
15.         {
16.             string st = "2023";
17.             if(m < 10)
18.             st += "0";
19.             st += to_string(m);
20.             if(j < 10)
21.             st += "0";
22.             st += to_string(j);
23.             int k = 0;
24.             for(int l = 0;l < 100 && k < 8;l++)
25.             {
26.                 if(num[l] == st[k] - '0')k++;
27.             }
28.             if(k == 8)
29.             ans++;
30.         }
31.       
32.     }
33.     cout << ans;
34.   return 0;
35. }

复制代码

代码解释
用string来存储是可以方便加上签到0，我们是先找到一个正当日期然后再遍历数组寻找子序列，当我们子序列的正当长度到达8时就说明该日期乐成在数组中找到了。
01串的熵

这个题是找0出现了多少次，所以我们遍历所有0出现的次数，盘算熵即可
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
6.   int len = 23333333;
7.   //暴露枚举所有的0的个数计算信息熵
8.   for(int i = 1;i <= len / 2;i++)//0的个数比1少
9.   {
10.       double ans = 0;
11.       ans -=  1.0  * i / len  * log2(1.0 * i / len) * i ;
12.       ans -= 1.0  * (len - i) / len * log2(1.0 * (len - i) / len) * (len - i);
13.       if(fabs(ans -= 11625907.5798) < 1e-4)
14.       {
15.           cout << i;
16.           break;
17.       }
19.   }
20.   return 0;
21. }

复制代码

代码解释
迷惑的点就是对数怎么盘算，实在就直接写就行^ _ ^，但这里会卡一个精度问题，同之前的问题，double范例在进行除法盘算时会出现精度问题，导致盘算堕落。
起首需要知道log2这个函数的参数范例是double，返回范例也是double，所以我们需要乘上1.0而且用double来进行担当。
冶炼金属

我这里的方法有些蠢，背面我看别人的题解发现这居然是个数学问题，我的思绪就是先找到最大值，然后让最大值不停自减使得该值是能使条件成立的最小值
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int a[1010][2];
4. int Min[1010];
5. int main()
6. {
7.   // 请在此输入您的代码
8.   int n;
9.   cin >> n;
10.   for(int i = 0;i < n;i++)
11.     for(int j = 0;j < 2;j++)
12.         cin >> a[i][j];
13.   int ma = 0x3f3f3f3f;
14.   int mi = 0;
15.   for(int i = 0;i < n;i++)
16.   {
17.       ma = min(ma,a[i][0] / a[i][1]);
18.   }
19.   for(int i = 0;i < n;i++)
20.   {
21.     mi = ma;
22.     while(a[i][0] - mi * a[i][1] < mi)
23.     {
24.         mi--;
25.     }
26.     Min[i] = mi + 1;
27.   }
28.   sort(Min,Min + n);
29.   cout << Min[n - 1] << ' ' << ma;
30.   return 0;
31. }

复制代码

代码解释
这里有几个细节问题，因为我们找到的最大值与最小值是需要使得所有数据均满足的，所以我们的最大值是找的所有最大值中的最小值，最小值是找所有最小值的最大值，我开的Min数组就是存储所有最小值，然后进行排序，输出最大值（因为我当时不会怎么让sort从大到小，所以只能输出最后一个元素）如今会了，也记载一下吧std::sort(nums.begin(), nums.end(), std::greater<int>());需要包含头文件#include <functional>
飞机降落

由于这个问题的N只有10，所以可以直接进行暴力罗列，当时做出来这个题还黑白常开心非常爽的，因为是第一次自己做出来dfs的题目（固然对大佬来说很简单）
思绪就是利用dfs找到所有的排列，我们需要定义一个current记载当前的时间，假如当前飞机在上一架飞机降落之后才到达，那么该飞机就可以直接降落，而且让current加被骗前飞机到达时间与上一架飞机降落时间之差再加被骗前飞机降落所需要的时间。
假如当前飞机是在上一架飞机降落之前就到达了，那么该飞机就需要等候，所以假如当前飞机能等到前一架飞机降落，那么该飞机就可以降落，current加上该飞机降落需要耗费的时间。
大体思绪就是这样，详细代码中仍有一些细节问题。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int T[21],D[21],L[21];
4. bool st[21];
5. int n;
6. int current;
7. bool flag;
8. void dfs(int u)
9. {
10.     if (u == n)
11.     {
12.         flag = true;
13.         return;
14.     }
15.     for (int i = 0; i < n; i++)
16.     {
17.         if (!flag)//提前剪枝
18.         {
19.             if (!st[i])//代表当前这个元素没有被使用
20.             {
21.                 if (current <= T[i])
22.                 {
23.                     st[i] = true;
24.                     int tmp = current;//因为current在回溯过程中会改变，因此需要额外开一个tmp存储当前的current以便回溯
25.                     current += T[i] - tmp + L[i];
26.                     dfs(u + 1);
27.                     st[i] = false;
28.                     current -= T[i] - tmp + L[i];
29.                 }
30.                 else if (current <= T[i] + D[i])
31.                 {
32.                     st[i] = true;
33.                     current += L[i];
34.                     dfs(u + 1);
35.                     st[i] = false;
36.                     current -= L[i];
37.                 }
38.                 else
39.                 {
40.                     continue;//不是return，如果return会多剪枝后面的内容导致循环无法完全进行会遗漏
41.                 }
42.             }
43.         }
44.     }
45. }
46. int main()
47. {
48.   // 请在此输入您的代码
49.   int t;
50.   cin >> t;
51.   while(t--)
52.   {
53.       
54.       cin >> n;
55.       memset(T,0,sizeof T);
56.       memset(D,0,sizeof D);
57.       memset(L,0,sizeof L);
58.       memset(st,false,sizeof st);
59.       flag = false;//这五步初始化，由于是全局变量所以在每一组测试之前都需要初始化
60.       for(int i = 0;i < n;i++)
61.       {
62.           cin >> T[i] >> D[i] >> L[i];
63.       }
64.       dfs(0);
65.       if(!flag)cout << "NO" << endl;//flag表示标记是否已经找到，如果已经找到答案，那么就不需要再找，直接剪枝
66.       else cout << "YES" << endl;//避免打印多个YES
67.   }
68.   return 0;
69. }

复制代码

代码解释
起首，因为是多组测试，我们的T，D，L，flag又是全局变量，所以都是需要重新初始化。实现剪枝操作就是通过st数组以及flag，flag表示已经遍历到最后一层，那么就找到了，那么此时我们就不需要遍历其他的组合了，实现了剪枝。在回溯过程中因为我们的current会进行改变，所有需要定义一个tmp存储当前current，这样才可以实现真正的回溯过程。
第十五届

握手问题

直接就是一个小学奥数问题吧，直接让50个人握手减去七个人握手就行
详细代码如下

1. #include <iostream>
2. using namespace std;
3. int main()
4. {
5.   // 请在此输入您的代码
6.   cout << (49 + 1) * 49 / 2 - (6 + 1) * 6 / 2;
7.   return 0;
8. }

复制代码

小球反弹

这个题我们肯定不能直接盘算，我们知道，小球回到原位置，就需要水平走往返，竖
直走往返，固然小球水平走的时间与竖直走的时间肯定是一样的，我们可以假设水平走p个往返，竖直走q个往返，这样就可以推出公式dx * t= 2 * p * x,dy* t = 2 * q * y，那么两式相除可以得到p/q = y * dx / x * dy，我们令p = y * dx，q = x * dy，但是这里我们需要让p，q都除等上他们的最大公约数，为什么要这么做呢，是因为假如p与q有着公因子的话，那么就说明此时小球并不是第一次到达起点了。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int gcd(int a,int b)
4. {
5.     return b ? gcd(b,a % b): a;
6. }
7. int main()
8. {
9.   // 请在此输入您的代码
10.   //设x上走p个来回，y上走q个来回,因为分解原因，耗费的时间肯定是一样的
11.   //x上走的距离就是2p*x，dx*t = 2px,dy * t = 2qy,两者相比得到p/q = y * dx / x * dy
12.   //令p = y*dx,q=x*dy,然后让p，q都/=他们的最大公约数，如果不/=，就说明此时并不是第一次到达起点
13.   int x = 343720,y = 233333;
14.   int dx = 15,dy = 17;
15.   int p = y * dx,q = x * dy;
16.   int g = gcd(p,q);
18.   p /= g,q /= g;
20.   double t = 1.0 * 2 * p * x / dx;
21.   double ans = t * sqrt(dx* dx + dy * dy);
22.   printf("%.2lf",ans);
23.   return 0;
24. }

复制代码

好数

我的思绪就是罗列每一个数，判定他是不是好数，所以写了一个get函数来判定这个数是不是好数，我们这里可以优化一下，根据好数的定义，偶数是肯定不是好数的，所以可以特判一下。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. bool get(int n)
4. {
5.     vector<int>num;
6.     while(n)
7.     {
8.         num.push_back(n % 10);
9.         n /= 10;
10.     }
11.     bool flag = false;
12.     for(int i = 0;i < num.size();i++)
13.     {
14.         if(i % 2 == 0)//奇数位
15.         {
16.             if(num[i] % 2)
17.             flag = true;
18.             else
19.             flag = false;
20.         }
21.         else
22.         {
23.             if(num[i] % 2 == 0)
24.             flag = true;
25.             else
26.             flag = false;
27.         }
28.         if(!flag)break;
29.     }
30.     return flag;
31. }
32. int main()
33. {
34.   // 请在此输入您的代码
35.   int n;
36.   int ans = 0;
37.   cin >> n;
38.   for(int i = 1;i <= n;i++)
39.   {
40.       if(i % 2 == 0)
41.       {
42.           continue;
43.       }
44.       if(get(i))
45.       {
46.           ans++;
47.       }
48.   }
49.   cout << ans;
50.   return 0;
51. }

复制代码

R格式

我一开始以为这个题不能用高精度乘法做，因为d与另一个数都是很大的，结果背面才发现可以不用把这个2直接乘完而是每次都乘上2。所以这里就是一个高精度的乘法。
详细代码如下

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.   string s ;
6.   int n;
7.   cin >> n >> s;
8.   //先让他翻转
9.   reverse(s.begin(),s.end());
10.   int pos = s.find('.');
11.   s.erase(pos,1);
12.   int a[3050];//这里的a数组必须开大一点
13.   int len = s.size();
14.   for(int i = 0;i < len;i++)a[i + 1] = s[i] - '0';
15.   //高精度乘低精度
16.   for(int i = 0;i < n;i++)
17.   {
18.       for(int j = 1;j <= len;j++)
19.       {
20.           a[j] *= 2;//每一位都要乘上2
21.       }
22.       for(int j = 1;j <= len;j++)
23.       {
24.           if(a[j] >= 10)
25.           {
26.             a[j + 1]++;
27.             a[j] %= 10;
28.             if(j == len)len++;
29.           }
30.       }
31.   }
32.   //处理小数点后一位需不需要四舍五入
33.   if(a[pos] >= 5)a[pos + 1]++;
34.   for(int i = pos + 1;i <= len;i++)
35.   {
36.       if(a[i] >= 10)
37.       {
38.           a[i + 1]++;
39.           a[i] %= 10;
40.           if(i == len)len++;
41.       }
42.   }
43.   for(int i = len;i >= pos + 1;i--)cout << a[i];
44.   return 0;
45. }

复制代码

代码解释
就是高精度乘法的模版，我们把个位数存储到第一位，这样方便进行存储而且进位，这样的话输出就需要逆序输出，所以先用reverse逆置，这里需要记住一个细节，就是需要判定len是否需要自增，是因为进位问题，这里容易遗忘。
后记

这就是我这四天能做的大概做不了但是看了题解能明白而且自己能做出来的题目了，感觉对于我一个初学算法的小蒟蒻来说，能做出来签到题就谢天谢地了。希望我明日的蓝桥杯可以拿到省三吧。后续会恢复更新C++的学习的。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。