[C++知识库]2020年 第十一届 蓝桥杯省赛 C/C++ B 组 学习总结

试题A：门牌制作

答案：624
解析：枚举数字 1 ~ 2020 然后用取余一位一位取，如果有2就让答案 ++

#include <iostream>
using namespace std;
int res;
int main()
{
  for(int i = 1; i <= 2020; i ++)
  {
      int t = i; //按位取数
      while(t)
      {
        if(t % 10 == 2) res ++; //如果需要 数字2 
         t /=10;
      }
  }
  cout << res;
  return 0;
}

试题B：既约分数

答案：2481215
解析：重点就是求最大公约数 gcd ,如果等于 1 就是既约分数

#include <iostream>
using namespace std;
int res = 0;
int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}
int main()
{
  for(int i = 1; i <= 2020; i ++)
    for(int j = 1; j <= 2020; j ++)
    {
      if(gcd(i, j) == 1) res++;
    }
  cout << res;
  return 0;
}

试题C：蛇形填数

答案：761
解析：本题可以通过找规律的方式求解
解法1 ：

1 2 6 7 15 16 28 29
3 5 8 14 17 27 30
4 9 13 18 26 31
10 12 19 25 32
11 20 24 33 41
21 23 34 40
22 35 39
36 38
37
找出 i 行 i列的数 ： 1 5 13 25 41
1 5 差 4 ；5 13差8 ；13 25 差 12 ； 25 41 差16
所以第二行第二列 为 1 + （2 - 1）* 4 = 5
第三行第三列 为 1 + (2 - 1) 4 + (3 - 1) * 4=13
第n行第n列 为 1 + （2 - 1） 4 + (3 - 1) * 4 +…+(n - 1) * 4

#include <iostream>
using namespace std;
int main()
{
  int res = 1, d = 4;
  for(int i = 2; i <= 20; i ++)
  {
    int add = d * (i - 1);
    res += add;
  }
  cout << res;
  return 0;
}

解法2
还看到更简单的规律 ：第n行n列 = n * n + (n - 1) * (n - 1)

cout << 20 * 20 + 19 * 19;

解法3
有些同学可能表示找不到规律，那也可以直接模拟蛇形填数。
代码转载:蛇形填数-Cyril_KI的代码

#include<iostream>
using namespace std;

int mp[20][20], row = 0, col = 0, cnt = 1;
int main() {
    mp[0][0] = 1; //第一行第一列为 1 ； 从0 下标开始
    while(!mp[19][19])  //直到第20行20列有值
    { 
        mp[row][++col] = ++cnt;        //右移 每次都是走一格

        while(col)        //左下方； 向左下移动到 边界 列为 0
        {           
            mp[++row][--col] = ++cnt;
        }
        
        mp[++row][col] = ++cnt;    //下移一格
      
        while(row) //右上方 ；向右上方移动到 边界 行为0
        {  
            mp[--row][++col] = ++cnt;
        }
    }
    cout << mp[19][19];  
    return 0;
}

试题D：跑步训练

答案：8879

解析：模拟日期变化，枚举2000 - 2020 年 然后12个月的每一天，
月份下的二月需要特判是不是闰年 需要加多一天。然后星期几的话用一个数每天 ++ 然后模 7 即可，这样就是七天一循环。

#include <iostream> 
using namespace std;
typedef long long LL;
int mon[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; //月份表示mon[i] 表示 i 月
int loop(int x) //求闰年 如果是闰年直接返回 1 让二月份加 1 即可
{
    int y = 0;
    if(x % 4 ==0 && x % 100 != 0 || x % 400 == 0) y = 1;
    return y;
}
int main()
{
  int res = 0; //跑步公里
  int zh = 6; //记录是星期几 6 表示星期日； 0表示星期日； 1 表示星期一
  for(int year = 2000; year <= 2020; year ++)
  {
      for(int month = 1; month <= 12; month ++)
      {
          int maxday = mon[month];
          if(month == 2) maxday += loop(year);
          for(int day = 1; day <= maxday; day ++)
        {
             res ++;
             if(day == 1 || zh == 1) res ++;
             zh = (zh + 1) % 7; 
             if(year == 2020 && month == 10 && day == 1)
             {
                 cout << res;
                 return 0;
             }
        }    
    }
  }
  return 0;
}

试题E ：七段码

可以移步上方链接处，之前已经写了，这里就不占篇幅了。

试题F：成绩统计

#include <iostream>
using namespace std;
  int n, score, acnt, bcnt;
void p(int a)
{
  a = a * 1000 / n; //避免 /n 后的精度问题  先 *1000 
  if(a % 10 >= 5) a = a / 10 + 1; //舍弃位 大于5 就 舍弃后进一
  else a = a / 10;  //小于5 直接舍弃
  cout << a << "%" << endl;
}
int main()
{
  cin >> n;
  for(int i = 0; i < n; i ++)
  {
    cin >> score;
    if(score >= 85) acnt ++ ;
    else if(score >= 60) bcnt ++ ;
  }
  p(bcnt + acnt);
  p(acnt);
  return 0;
}

试题G：回文日期

解析：枚举年份直接造出回文日期，然后判断是否合法

#include <iostream>
using namespace std;
int mo[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int loop(int x) //闰年判断
{
    int y = 0;
    if(x % 4 && x % 100 != 0 || x % 400 == 0) y = 1;
    return y;
}
int main()
{
  int year, month, day;
  int x; cin >> x;
  year = x / 10000;

  for(int i = year; i <= 9999; i ++)
  {
      month = (i % 10 * 10) + i /10 % 10;
      if(month > 12 || month < 1) continue; //月份不合法
      day = (i / 100 % 10 * 10) + i / 1000;
      if(day > mo[month] + loop(i) || day < 1) continue; //月内日不合法
      if(i * 10000 + month * 100 + day == x) continue; //发现与输入的日期重复了 跳过
      printf("%02d%02d%02d\n",i,month,day);
      break;
  }

   for(int i = year; i <= 9999; i ++)
  {
      int a = i / 10 % 10; int b = i % 10; //取出年后两位 为A B
      if(a != i / 1000 || b != i / 100 % 10) continue; //不等于前两位A B 说明年不符合ABAB
      month = b * 10 + a;
      if(month > 12 || month < 1) continue;//月份不合法
      day = b * 10 + a;
      if(day > mo[month] + loop(i) || day < 1) continue; //月内日不合法
      if(i * 10000 + month * 100 + day == x) continue; //重复
      printf("%02d%02d%02d\n",i,month,day);
      break;
  }
  return 0;
}

试题H：字串分值和

解析：直接模拟的就会超时，所以还是需要找规律，这里有个叫贡献值的概念，理论第一个字符A在前5个字符串中共享了5次（默认以先出现的字母计算贡献）


有个类似的题也可以看看 ：子串分值

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100010;
string s;
int pre[27];
long long res; //26个字母 
int main()
{
  cin >> s;
  s = " " + s;
  int n = s.size();
  for(int i = 1; i < n; i ++)
  {
  	int k = s[i] - 'a';
  	res += (long long)(i - pre[k]) * (n - i);
  	pre[k] = i;
  }
   
  cout << res;
  return 0;
}

试题 I：平面切分

还是看这位大佬的解析吧平面切分 作者： saye
解释的非常清晰了，我只能膜拜。

试题J：字串排序

可以看看字串排序（DP）作者：Dripping.

这个也只能通过部分数据