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

文章目录

1.握手问题

题目描述：

解题思路1（组合数学）

按照题目描述来说，会议有五十人，如果不加任何限制条件，这五十个人两两握手的次数是：

     t 
    
   
     o 
    
   
     t 
    
   
     a 
    
   
     l 
    
   
     = 
    
   
     49 
    
   
     + 
    
   
     48 
    
   
     + 
    
   
     47 
    
   
     + 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     + 
    
   
     1 
    
   
  
    total=49+48+47+........+1 
   
  
total=49+48+47+........+1

利用高斯求和的得出：

     t 
    
   
     o 
    
   
     t 
    
   
     a 
    
   
     l 
    
   
     = 
    
   
     50 
    
   
     ∗ 
    
   
     49 
    
   
     / 
    
   
     2 
    
   
  
    total=50*49/2 
   
  
total=50∗49/2

如果加上限制条件的话，题目给定的其中有七个人不会相互握手，需要用上面总的不加限制的减去七个人相互握手的次数。

     c 
    
   
     n 
    
   
     t 
    
   
     = 
    
   
     6 
    
   
     + 
    
   
     5 
    
   
     + 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     . 
    
   
     + 
    
   
     1 
    
   
     = 
    
   
     7 
    
   
     ∗ 
    
   
     6 
    
   
     / 
    
   
     2 
    
   
  
    cnt=6+5+......+1=7*6/2 
   
  
cnt=6+5+......+1=7∗6/2

上述两式作差即可
编写代码：

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

解题思路2（暴力枚举）

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

#include<iostream>
using namespace std;intmain(){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;return0;}

2.小球反弹

问题描述：

做题思路

这道题我们肯定不能直接做的，这道题给定了

     d 
    
   
     x 
    
   
     : 
    
   
     d 
    
   
     y 
    
   
  
    dx:dy 
   
  
dx:dy的值说明这道题我们应该分解来做，将小球的反弹的路径分解为x方向和y方向来做。

我们首先假设x方向上经过了p个来回，y方向上经历了q个来回，因为是分解的缘故，所以两个分解方向上的时间是相同的。
所以可以得出两个等式：

     d 
    
   
     x 
    
   
     ∗ 
    
   
     t 
    
   
     = 
    
   
     2 
    
   
     p 
    
   
     x 
    
   
  
    dx*t=2px 
   
  
dx∗t=2px（由于这里一半的路程是x，所以一个来回的路程是2x，乘以来回就是总路程）
 
  
   
   
     d 
    
   
     y 
    
   
     ∗ 
    
   
     t 
    
   
     = 
    
   
     2 
    
   
     q 
    
   
     x 
    
   
  
    dy*t=2qx 
   
  
dy∗t=2qx

将这两个式子进行比例

       d 
      
     
       x 
      
     
     
     
       d 
      
     
       y 
      
     
    
   
     = 
    
    
     
     
       p 
      
     
       x 
      
     
     
     
       q 
      
     
       y 
      
     
    
   
  
    \frac{dx}{dy}=\frac{px}{qy} 
   
  
dydx​=qypx​

得到这个式子之后我们可以利用gcd对这个式子的左边进行约分。
可以得出：

     p 
    
   
     = 
    
   
     d 
    
   
     x 
    
   
     ∗ 
    
   
     y 
    
   
  
    p=dx*y 
   
  
p=dx∗y和 
 
  
   
   
     q 
    
   
     = 
    
   
     d 
    
   
     y 
    
   
     ∗ 
    
   
     x 
    
   
  
    q=dy*x 
   
  
q=dy∗x

算出q或者p之后可以利用公式计算t：

     t 
    
   
     = 
    
   
     2 
    
   
     p 
    
   
     x 
    
   
     / 
    
   
     d 
    
   
     x 
    
   
  
    t=2px/dx 
   
  
t=2px/dx

最后得出总路程：

     总路程 
    
   
     = 
    
   
     t 
    
   
     ∗ 
    
   
     ( 
    
   
     s 
    
   
     q 
    
   
     r 
    
   
     t 
    
   
     ( 
    
   
     1 
    
    
    
      5 
     
    
      2 
     
    
   
     + 
    
   
     1 
    
    
    
      7 
     
    
      2 
     
    
   
     ) 
    
   
     ) 
    
   
  
    总路程=t*(sqrt(15^2+17^2)) 
   
  
总路程=t∗(sqrt(152+172))

编写代码：

//求最大公约数intgcd(int a,int b){return b ==0? a :gcd(b, a % b);}intmain(){//给出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);return0;}

3.好数

问题描述：

数据量：

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

遍历1到n的数，然后写一个check函数判断每个数是否是好数，这里的时间复杂度是

     n 
    
   
     ∗ 
    
   
     l 
    
   
     o 
    
   
     g 
    
   
     n 
    
   
  
    n*logn 
   
  
n∗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;}intmain(){// 请在此输入您的代码
  cin>>N;for(int i=1;i<N;i++){if(Check(i)){
      count++;}}
  cout<<count<<endl;return0;}

4.R格式

题目描述：

数据量：

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

算法思路

高精度模版题：

编写代码：

#include<iostream>#include<algorithm>#include<string>#include<cmath>
using namespace std;//数组模拟高精度：高精度*低精度constint N =2e3+10;
string s;int a[N];intmain(){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];return0;}

5.宝石组合

题目描述：

数据范围：

首先从数据量来看这道题是不能用暴力枚举的，因为暴力枚举三个数的时间复杂度是

     O 
    
   
     ( 
    
    
    
      N 
     
    
      3 
     
    
   
     ) 
    
   
  
    O(N^3) 
   
  
O(N3)了。

算法思路—唯一分解定理

首先我们要知道什么是唯一分解定理，简单来说唯一分解定理就是，任意一个大于1的正整数 ，都可以唯一地表示为若干个质数的乘积，且这些质数的顺序不影响分解的唯一性。
那么可以得出：

      N 
     
    
      1 
     
    
   
     = 
    
    
    
      p 
     
    
      1 
     
     
     
       a 
      
     
       1 
      
     
    
   
     ⋅ 
    
    
    
      p 
     
    
      2 
     
     
     
       a 
      
     
       2 
      
     
    
   
     ⋅ 
    
   
     … 
    
   
     ⋅ 
    
    
    
      p 
     
    
      n 
     
     
     
       a 
      
     
       n 
      
     
    
   
  
    N_1 = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_n^{a_n} 
   
  
N1​=p1a1​​⋅p2a2​​⋅…⋅pnan​​
 
  
   
    
    
      N 
     
    
      2 
     
    
   
     = 
    
    
    
      p 
     
    
      1 
     
     
     
       b 
      
     
       1 
      
     
    
   
     ⋅ 
    
    
    
      p 
     
    
      2 
     
     
     
       b 
      
     
       2 
      
     
    
   
     ⋅ 
    
   
     … 
    
   
     ⋅ 
    
    
    
      p 
     
    
      n 
     
     
     
       b 
      
     
       n 
      
     
    
   
  
    N_2 = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots \cdot p_n^{b_n} 
   
  
N2​=p1b1​​⋅p2b2​​⋅…⋅pnbn​​

从上面两个式子可以得出：

     gcd 
    
   
     ⁡ 
    
   
     ( 
    
    
    
      N 
     
    
      1 
     
    
   
     , 
    
    
    
      N 
     
    
      2 
     
    
   
     ) 
    
   
     = 
    
    
    
      p 
     
    
      1 
     
     
     
       min 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        1 
       
      
     
       , 
      
      
      
        b 
       
      
        1 
       
      
     
       ) 
      
     
    
   
     ⋅ 
    
    
    
      p 
     
    
      2 
     
     
     
       min 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        2 
       
      
     
       , 
      
      
      
        b 
       
      
        2 
       
      
     
       ) 
      
     
    
   
     ⋅ 
    
   
     … 
    
   
     ⋅ 
    
    
    
      p 
     
    
      n 
     
     
     
       min 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        n 
       
      
     
       , 
      
      
      
        b 
       
      
        n 
       
      
     
       ) 
      
     
    
   
  
    \gcd(N_1,N_2) = p_1^{\min(a_1,b_1)} \cdot p_2^{\min(a_2,b_2)} \cdot \ldots \cdot p_n^{\min(a_n,b_n)} 
   
  
gcd(N1​,N2​)=p1min(a1​,b1​)​⋅p2min(a2​,b2​)​⋅…⋅pnmin(an​,bn​)​
 
  
   
   
     lcm 
    
   
     ⁡ 
    
   
     ( 
    
    
    
      N 
     
    
      1 
     
    
   
     , 
    
    
    
      N 
     
    
      2 
     
    
   
     ) 
    
   
     = 
    
    
    
      p 
     
    
      1 
     
     
     
       max 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        1 
       
      
     
       , 
      
      
      
        b 
       
      
        1 
       
      
     
       ) 
      
     
    
   
     ⋅ 
    
    
    
      p 
     
    
      2 
     
     
     
       max 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        2 
       
      
     
       , 
      
      
      
        b 
       
      
        2 
       
      
     
       ) 
      
     
    
   
     ⋅ 
    
   
     … 
    
   
     ⋅ 
    
    
    
      p 
     
    
      n 
     
     
     
       max 
      
     
       ⁡ 
      
     
       ( 
      
      
      
        a 
       
      
        n 
       
      
     
       , 
      
      
      
        b 
       
      
        n 
       
      
     
       ) 
      
     
    
   
  
    \operatorname{lcm}(N_1,N_2) = p_1^{\max(a_1,b_1)} \cdot p_2^{\max(a_2,b_2)} \cdot \ldots \cdot p_n^{\max(a_n,b_n)} 
   
  
lcm(N1​,N2​)=p1max(a1​,b1​)​⋅p2max(a2​,b2​)​⋅…⋅pnmax(an​,bn​)​

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

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

     x 
    
   
     + 
    
   
     y 
    
   
     + 
    
   
     z 
    
   
     + 
    
   
     max 
    
   
     ⁡ 
    
   
     ( 
    
   
     x 
    
   
     , 
    
   
     y 
    
   
     , 
    
   
     z 
    
   
     ) 
    
   
     − 
    
   
     max 
    
   
     ⁡ 
    
   
     ( 
    
   
     x 
    
   
     , 
    
   
     y 
    
   
     ) 
    
   
     − 
    
   
     max 
    
   
     ⁡ 
    
   
     ( 
    
   
     x 
    
   
     , 
    
   
     z 
    
   
     ) 
    
   
     − 
    
   
     max 
    
   
     ⁡ 
    
   
     ( 
    
   
     y 
    
   
     , 
    
   
     z 
    
   
     ) 
    
   
  
    x+y+z+\max(x,y,z)-\max(x,y)-\max(x,z)-\max(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;constint N =1e5+10;int a[N];//fac是存储因子的二维数组，s是求的最大值
vector<int> fac[N], s[N];intmain(){//遍历数组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;}}return0;}

6.数字接龙

问题描述：

数据量：

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

算法思路----DFS

编写代码：

#include<iostream>#include<string>
using namespace std;constint N =20;int a[N][N];
bool vis[N][N];int n, k;//方向数组：   0  1 2 3 4 5 6  7int dx[8]={-1,-1,0,1,1,1,0,-1};int dy[8]={0,1,1,1,0,-1,-1,-1};
string res;voiddfs(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)){//可以搜索，将点标记为true
            vis[bx][by]= true;dfs(bx, by, a[bx][by], s +to_string(i), dep +1);//最优性剪枝if(!res.empty())return;
            vis[bx][by]= false;//回溯}}}intmain(){
    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;return0;}

7.拔河

问题描述：

数据量：

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

算法思路

编写代码：

#include<iostream>#include<set>#include<climits>
using namespace std;#definelllonglongconstint N =1e3+10;int a[N], s[N];//前缀和和数组
multiset<int> ms;intmain(){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;return0;}