第十五届蓝桥杯C++B组省赛

1.握手问题

题目描述：

解题思路1（组合数学）

按照题目描述来说，会议有五十人，如果不加任何限制条件，这五十个人两两握手的次数是：
$total=49+48+47+........+1$
利用高斯求和的得出：$total=50\ast 49/2$
如果加上限制条件的话，题目给定的其中有七个人不会相互握手，需要用上面总的不加限制的减去七个人相互握手的次数。
$cnt=6+5+......+1=7\ast 6/2$
上述两式作差即可
编写代码：

#include<iostream>
using namespace std;
int main()
{int total = 50 * 49 / 2;int cnt = 7 * 6 / 2;cout << total - cnt << endl;return 0;
}

解题思路2（暴力枚举）

将每个人握手的情况枚举出来即可。

#include<iostream>
using namespace std;
int main()
{int ans = 0;for (int i = 1;i <= 50;i++){for (int j = i + 1;j <= 50;j++){//排除掉七人的情况if (!(i >= 1 && i <= 7 && j >= 1 && j <= 7)){ans++;}}}cout << ans << endl;return 0;
}

2.小球反弹

问题描述：

做题思路

这道题我们肯定不能直接做的，这道题给定了$dx:dy$的值说明这道题我们应该分解来做，将小球的反弹的路径分解为x方向和y方向来做。
我们首先假设x方向上经过了p个来回，y方向上经历了q个来回，因为是分解的缘故，所以两个分解方向上的时间是相同的。
所以可以得出两个等式：
$dx\ast t=2px$（由于这里一半的路程是x，所以一个来回的路程是2x，乘以来回就是总路程）
$dy\ast t=2qx$

将这两个式子进行比例
$\frac{dx}{dy}=\frac{px}{qy}$
得到这个式子之后我们可以利用gcd对这个式子的左边进行约分。
可以得出：$p=dx\ast y$和$q=dy\ast x$
算出q或者p之后可以利用公式计算t：$t=2px/dx$
最后得出总路程：$总路程=t\ast (sqrt(15^2+17^2))$

编写代码：

//求最大公约数
int gcd(int a, int b)
{return b == 0 ? a : gcd(b, a % b);
}
int main()
{//给出x方向和y方向的速度 int dx = 15, dy = 17;//给出x方向和y方向上的距离int x = 343720, y = 233333;//求出多少来回int q = dy * x, p = dx * y;//求最大公约数int g = gcd(p, q);p /= g, q /= g;//计算时间int t = 2 * p * x / dx;//求路程double ans = t * sqrt(15 * 15 + 17 * 17);printf("%.2lf\n", ans);return 0;
}

3.好数

问题描述：

数据量：

算法思路（暴力解法）—不会超时

遍历1到n的数，然后写一个check函数判断每个数是否是好数，这里的时间复杂度是$n\ast logn$
编写代码：

#include <iostream>
using namespace std;
int N,count;bool Check(int n)
{int i=1;while(n!=0){int tail=n%10;if(i%2==1){if(tail%2!=1)return false;}else{if(tail%2!=0)return false;}i++;n/=10;}return true;
}int main()
{// 请在此输入您的代码cin>>N;for(int i=1;i<N;i++){if(Check(i)){count++;}}cout<<count<<endl;return 0;
}

4.R格式

题目描述：

数据量：

可以看到这道题的数据量是很大的，涉及到了幂次，肯定不可能直接去算，这道题很显然是考察的是高精度算法（高精度*低精度）

算法思路

高精度模版题：

编写代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;//数组模拟高精度：高精度*低精度
const int N = 2e3 + 10;
string s;
int a[N];
int main()
{int n;cin >> n >> s;//反转操作reverse(s.begin(), s.end());//确定小数点的位置int pos = s.find(".");s.erase(pos, 1);//删除小数点，方便后续计算int len = s.size();for (int i = 0;i < len;i++)  a[i + 1] = s[i] - '0';//高精度*低精度for (int i = 1;i <= n;i++){//顺序扫描，均*2for (int j = 1;j <= len;j++) a[j] *= 2;//处理大于10的位数for (int j = 1;j <= len;j++){if (a[j] >= 10){a[j + 1]++;a[j] %= 10;if (j == len) len++;}}}//处理小数点后的第一位，进行四舍五入if (a[pos] >= 5)a[pos + 1]++;for (int i = pos + 1;i <= len;i++){if (a[i] >= 10){a[i + 1]++;a[i] %= 10;if (i == len)len++;}}//打印的时候倒序打印for (int i = len;i >= pos + 1;i--) cout << a[i];return 0;
}

5.宝石组合

题目描述：

数据范围：

首先从数据量来看这道题是不能用暴力枚举的，因为暴力枚举三个数的时间复杂度是$O(N^3)$了。

算法思路—唯一分解定理

首先我们要知道什么是唯一分解定理，简单来说唯一分解定理就是，任意一个大于1的正整数 ，都可以唯一地表示为若干个质数的乘积，且这些质数的顺序不影响分解的唯一性。
那么可以得出：
$N_1=p_1^{a_1}\cdot p_2^{a_2}\cdot \dots \cdot p_n^{a_n}$

$N_2=p_1^{b_1}\cdot p_2^{b_2}\cdot \dots \cdot p_n^{b_n}$

从上面两个式子可以得出：
$\gcd (N_1,N_2)=p_1^{\min (a_1,b_1)}\cdot p_2^{\min (a_2,b_2)}\cdot \dots \cdot p_n^{\min (a_n,b_n)}$

$\mathrm{lcm}(N_1,N_2)=p_1^{\max (a_1,b_1)}\cdot p_2^{\max (a_2,b_2)}\cdot \dots \cdot p_n^{\max (a_n,b_n)}$

假设Ha，Hb，Hc的分解出来的相同的质数的幂次分别是x，y，z那么可以得出：

上面的式子可以转换为幂次是：

$x+y+z+\max (x,y,z)-\max (x,y)-\max (x,z)-\max (y,z)$
相当于我们只需要求出上面式子的最大值即可。

编写代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
//fac是存储因子的二维数组，s是求的最大值
vector<int> fac[N], s[N];
int main()
{//遍历数组for (int i = 1;i <= 1e5;i++){for (int j = i;j <= 1e5;j += i){//i是j的因子fac[j].push_back(i);}}//输入n个数int n;cin >> n;for (int i = 1;i <= n;i++)cin >> a[i];//保证字典序最小sort(a + 1, a + n + 1);for (int i = 1;i <= n;i++){//处理i的每个因子for (int j = 0;j < fac[a[i]].size();j++){//s[fac[a[i]][j]].push_back(a[i]);}}for (int i = 1e5;i >= 0;i--){if (s[i].size() >= 3){cout << s[i][0] << ' ' << s[i][1] << ' ' << s[i][2] << endl;break;}}return 0;
}

6.数字接龙

问题描述：

数据量：

根据数据量来看这道题考察的应该是DFS，但是在DFS中应该还涉及到回溯，因为当走到不满足条件的时候需要进行回溯。

算法思路----DFS

编写代码：

#include<iostream>
#include<string>
using namespace std;
const int N = 20;
int a[N][N];
bool vis[N][N];
int n, k;
//方向数组：   0  1 2 3 4 5 6  7
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
string res;void dfs(int x, int y, int prev, string s, int dep)
{//当搜到终点的时候，且搜索深度是n的时候，意思就是每种情况都搜索完了if (x == n && y == n && dep == n * n) {if (res.empty())res = s;return;}for (int i = 0;i < 8;i++){//生成邻接点int bx = x + dx[i];int by = y + dy[i];//过滤越界节点if (bx<1 || bx>n || by<1 || by>n)continue;//过滤访问过的节点if (vis[bx][by] == true)continue;//防止交叉搜索if (i == 1 && vis[x - 1][y] && vis[x][y + 1])continue;if (i == 3 && vis[x + 1][y] && vis[x][y + 1])continue;if (i == 5 && vis[x + 1][y] && vis[x][y - 1])continue;if (i == 7 && vis[x - 1][y] && vis[x][y - 1])continue;//保证路径数值为0 1 2 3 .....k-1if ((a[bx][by] < k && a[bx][by] == prev + 1) || (prev + 1 == k && a[bx][by] == 0)){//可以搜索，将点标记为truevis[bx][by] = true;dfs(bx, by, a[bx][by], s + to_string(i), dep + 1);//最优性剪枝if (!res.empty())return;vis[bx][by] = false;//回溯}}
}int main()
{cin >> n >> k;for (int i = 1;i <= n;i++)for (int j = 1;j <= n;j++)cin >> a[i][j];string emp;//标记起点vis[1][1] = true;dfs(1, 1, 0, emp, 1);if (res.empty())cout << -1;else cout << res << endl;return 0;
}

7.拔河

问题描述：

数据量：

对于这种涉及到区间和的题来说，大概率都是用前缀和算法解决

算法思路

编写代码：

#include<iostream>
#include<set>
#include<climits>
using namespace std;#define ll long longconst int N = 1e3 + 10;
int a[N], s[N];//前缀和和数组
multiset<int> ms;int main()
{int n;cin >> n;for (int i = 1;i <= n;i++){cin >> a[i];//前缀和s[i] = s[i - 1] + a[i];}//用set去维护所有的区间和for (int i = 1;i <= n;i++){for (int j = 1;j <= n;j++){//维护区间和ms.insert(s[j] - s[i - 1]);}}int ans = LONG_MAX;for (int i = 1;i <= n;i++){for (int j = 1;j < i;j++){//枚举以i结尾的区间，因为这里i-1只会有一个人，所以应该是j-1int sum = s[i] - s[j - 1];//找到与该区间和sum相似的区间和auto it = ms.lower_bound(sum);if (it != ms.end()){ans = min(ans, abs(*it - sum));}if (it != ms.begin()){it--;ans = min(ans, abs(*it - sum));}}//删除以i开头且以j结尾的区间，防止后续查询区间的时候出现区间重叠/交叉问题for (int j = i;j <= n;j++) ms.erase(ms.find(s[j] - s[i - 1]));}cout << ans << endl;return 0;
}