微信如何申请小程序_长沙斌网网络_需要多少钱_国内新闻最新消息简短

蓝桥杯第十二届省赛B组C++真题解析

一、空间（填空题）

​​题目链接​​：https://www.lanqiao.cn/problems/1445/learning/
​​解题思路​​：

• 进制转换关系：
  • 1 MB = 1024 KB
  • 1 KB = 1024 B
  • 1 B = 4 字节
  • 1 字节 = 8 比特（bit）
    ​​关键公式​​：
    总比特数 = 内存大小（MB） × 1024 × 1024 × 4 × 8

---

二、卡片（填空题）

​​题目链接​​：https://www.lanqiao.cn/problems/2383/learning/
​​解题思路​​：

1. 从 k 张卡片中选两张的不同组合数：
   $$C(k,2)=\frac{k(k-1)}{2}$$
2. 选两张相同卡片的组合数：直接取 k 种。
3. 使用二分法找到最小的 k，满足：
   $$\frac{k(k+1)}{2}\ge n$$
   ​​代码实现​​：

#include <iostream>
using namespace std;int main() {int n;cin >> n;int l = 0, r = n + 1;while (l < r) {long long mid = (l + r) >> 1; // 防止溢出if (mid * mid + mid >= 2 * n) r = mid;else l = mid + 1;}cout << l;return 0;
}

---

三、直线（填空题）

​​题目链接​​：https://www.lanqiao.cn/problems/1449/learning/

解题思路

1. ​​遍历所有点对​​：
   • 计算两点间的斜率 k 和截距 b。
   • ​​注意​​：为避免精度丢失，直接使用代数公式计算 b：
     $$b=\frac{x_1{y}_2-x_2{y}_1}{x_1-x_2}$$
2. ​​去重方法​​：
   • 使用 set<pair<double, double>> 存储直线参数，自动去重。
   • 垂直直线（x = c）需单独统计，共 ​​20 条​​。

代码实现

#include <bits/stdc++.h>
using namespace std;set<pair<double, double>> lines;int main() {for (int x1 = 0; x1 < 20; x1++) {for (int y1 = 0; y1 < 21; y1++) {for (int x2 = 0; x2 < 20; x2++) {for (int y2 = 0; y2 < 21; y2++) {if (x1 == x2) continue; // 跳过垂直线double k = (double)(y2 - y1) / (x2 - x1);double b = (double)(x1*y2 - x2*y1) / (x1 - x2); // 避免用 k 计算 blines.insert({k, b});}}}}cout << lines.size() + 20; // 加上垂直线数量return 0;
}

---

四、货物摆放（填空题）

​​题目链接​​：https://www.lanqiao.cn/problems/1463/learning/

解题思路

方法一：暴力法

1. ​​暴力遍历​​：
   • 三重循环遍历所有可能的因子组合 (i, j, k)。
   • 计算 i * j * k == n 的组合数。
   • ​​缺点​​：复杂度极高，存在大量无效计算。

方法二：因子分解法（优化）

1. ​​因子预处理​​：
   • 遍历 i 到 sqrt(n)，收集 n 的所有因子。
   • 因子成对存储（i 和 n/i），避免重复。
2. ​​组合遍历​​：
   • 三重循环遍历所有因子组合 (a, b, c)。
   • 统计满足 a * b * c == n 的有效组合数。
3. ​​复杂度优化​​：
   • 时间复杂度从 O(n^3) 降低到 O(m^3)（m 为因子总数）。

关键公式

$$\text{因子分解}:\forall i\in [1,\sqrt{n}],\text{if}n\mathrm{m}\mathrm{o}\mathrm{d}i=0\Rightarrow \text{保存}i\text{和}n/i$$

代码实现

#include <bits/stdc++.h>
using namespace std;
vector<long long> disvide;//开long long，有因子很大
int main()
{long long n = 2021041820210418;long long ans = 0;/*暴力for(long long i = 1; i*i*i<=n; i++ ){if(n%i==0){for(long long j=i; i*j*j<=n; j++){if(n/i%j==0){long long k = n/i/j;if(i==j&&j==k) ans++;else if(i==j||j==k||i==k) ans+=3;else ans+=6;}else continue;}}}*/for(long long i=1; i*i<=n;i++){if(n%i==0){disvide.push_back(i);long long k = n/i;if(i!=k) disvide.push_back(k);} }//存储因子for(auto a=disvide.begin(); a!=disvide.end(); a++)for(auto b=disvide.begin(); b!=disvide.end(); b++)for(auto c=disvide.begin(); c!=disvide.end(); c++){if((*a)*(*b)*(*c)==n) ans++;}cout << ans;return 0;
}

注意事项
**​​数据类型​​：**必须使用 long long 避免大数溢出。
**​​因子去重​​：**当 i 是 n 的平方根时，仅存储一次。
​​性能分析​​：**实测因子数量约为 ​​200​​ 个，总循环次数为 200^3 = 8,000,000，可快速完成。

---

五、最短路径

​​题目链接​​：https://www.lanqiao.cn/problems/1460/learning/

解题思路

动态规划（Dijkstra思想）

1. ​​问题建模​​：

   • 将节点视为图的顶点，边权为两节点的​​最小公倍数（LCM）​​。
   • ​​跳跃限制​​：每个节点 i 可跳到 i+1 到 i+21 的节点。

2. ​​状态定义​​：

   • f[j] 表示从节点 1 到节点 j 的最小路径和。

3. ​​状态转移​​：

   • 对每个节点 j，遍历其前驱节点 i（满足 j-21 ≤ i < j）。
   • 更新公式：
     $$f[j]=\min (f[j],f[i]+\text{LCM}(i,j))$$

4. ​​LCM计算​​：
   $$\text{LCM}(i,j)=\frac{i\times j}{\text{GCD}(i,j)}$$

算法特点

• ​​贪心思想​​：每次用当前最小路径更新后续节点。
• ​​复杂度​​：O(21×n)，高效处理大规模节点。

代码实现

#include <iostream>
#include <cstring>  // 包含memset函数
using namespace std;const int MAX_NODE = 2030;
long long f[MAX_NODE];  // 防止溢出// 计算最大公约数（非递归实现）
int gcd(int x, int y) {while (y != 0) {int temp = x % y;x = y;y = temp;}return x;
}int main() {// 初始化所有节点为极大值（模拟无穷大）memset(f, 0x3f, sizeof(f));f[1] = 0;  // 起点路径和为0for (int i = 1; i <= 2021; ++i) {// 限制跳跃范围：i+1 到 i+21，且不超过2021for (int j = i + 1; j <= min(i + 21, 2021); ++j) {long long cost = (long long)i * j / gcd(i, j);  // 显式转为long long防溢出f[j] = min(f[j], f[i] + cost);  // 关键状态转移}}cout << f[2021] << endl;  // 输出目标节点结果return 0;
}

---

六、时间显示

​​题目链接​​：https://www.lanqiao.cn/problems/1452/learning/

解题思路

1. ​​时间单位转换​​：

   • 1 天 = 86400 秒 = 86400000 毫秒
   • 输入毫秒数需先对 86400000 取模，得到当天的剩余毫秒数。
   • 通过整除和取模运算提取小时、分钟和秒：
     • 小时 = 总秒数 / 3600
     • 分钟 = (总秒数 % 3600) / 60
     • 秒 = 总秒数 % 60

2. ​​格式化输出​​：

   • 使用 %02d 格式保证每位数字至少占2位，不足时补前导零。

#include <bits/stdc++.h>
using namespace std;
int main()
{string s1;long long ms;cin >> ms;long long t = ms%86400000;t = ms/1000;int s = t%60;t /= 60;int min = t%60;t /= 60;if(t%24<10) s1 += '0';s1 += to_string(t%24);s1 += ":";if(min<10) s1 += '0';s1 += to_string(min);s1 += ":";if(s<10) s1 += '0';s1 += to_string(s);cout << s1;return 0;
}

---

八、双向排序

​​题目链接​​：https://www.lanqiao.cn/problems/1458/learning/

解题思路

1. ​​操作分类​​：
   • ​​操作类型0​​（降序）：对区间 [1, q] 进行降序排序。
   • ​​操作类型1​​（升序）：对区间 [q, n] 进行升序排序。
2. ​​实现方法​​：
   • 使用 sort 函数直接处理指定区间。
   • sort 的区间参数为​​左闭右开​​（begin, end+1）。

注意事项

⚠️sort函数是左开右闭的区间，默认升序，降序为sort(a,a+n, greater)；
⚠️sort（a,a+n,cmp),自定义排序，返回值为bool类型：

bool cmp(int num1, int num2) {return num1 > num2;     // 可以简单理解为 > 降序排列;  <  升序排列
}

#include <bits/stdc++.h>
using namespace std;
int a[100010];int main()
{int n,m;cin >> n >> m;for(int i=1; i<=n; i++) a[i] = i;while(m--){int p,q;scanf("%d %d",&p,&q);if(p==0){sort(a + 1, a + q + 1,greater<int>());}else if(p==1){sort(a + q , a + n +1);}}for(int i=1; i<=n; i++) cout << a[i] << " "; return 0;
}