在博客上写好后直接粘过来的，好像有几张图片不行了，更好的阅读体验： https://www.cnblogs.com/ZhengLijie/p/13908680.html

2020年第十一届蓝桥杯C/C++ B组省赛题解

试题A：门牌制作

【问题描述】

小蓝要为一条街的住户制作门牌号。 这条街一共有 $2020$ 位住户，门牌号从 $1$ 到 $2020$ 编号。 小蓝制作门牌的方法是先制作 $0$ 到 $9$ 这几个数字字符，最后根据需要将字 符粘贴到门牌上，例如门牌 $1017$ 需要依次粘贴字符 $1、0、1、7$，即需要 $1$ 个 字符 $0$，$2$ 个字符 $1$，$1$ 个字符$7$。 请问要制作所有的 $1$ 到 $2020$ 号门牌，总共需要多少个字符 $2$？

思路：

从$1$枚举到$2020$，挨个转化为字符串，统计$2$的数目即可，可以直接用$count$函数。

代码：

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

void i2s(int num, string &ss) {
    stringstream temps;
    temps << num;
    temps >> ss;
}

int main() {
    int res = 0;
    for (int i = 1; i <= 2020; i++) {
        string numS;
        i2s(i, numS);
        res += count(numS.begin(), numS.end(), '2');
    }
    cout << res << endl;
    return 0;
}

答案：624

试题B：既约分数

【问题描述】

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。 例如，$\frac{3}{4}$ , $\frac{5}{2}$ , $\frac{1}{8}$, $\frac{7}{1}$ 都是既约分数。 请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

思路：

枚举

代码：

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;
typedef long long LL;

LL gcd(LL a, LL b) {
    a = abs(a), b = abs(b);
    while (b != 0) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    int res = 0;
    for (int i = 1; i <= 2020; i++) {
        for (int j = 1; j <= 2020; j++) {
            if (gcd(i, j) == 1) {
                res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

答案：2481215

试题C：蛇形填数

如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。

容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列 的数是多少？

思路：

找规律：

用$excel$做几行后对角线直接找规律

可以看到 这就是一个公差每次增大4的数列，1与5之间是4，5与13之间是8，13与25之间是12.。。。以此类推即可。

编程实现：

把它看成一个“堆”数，然后第一重循环枚举的是每一个反对角线，里边两重循环，如果是奇数对角线则从右上往左下枚举，如果是偶数对角线则从左下往右上枚举。

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;
typedef long long LL;

int main() {
    int a[45][45];
    for (int i = 1, cnt = 1; i <= 45; i++) { //i枚举的是反对角线
        if (i & 1) { //奇数对角线从左向右，偶数对角线从右向左
            for (int x = i, y = 1; x >= 1 && y <= i; x--, y++) {
                a[x][y] = cnt++;
            } 
        } else {
            for (int x = 1, y = i; x <= i && y >= 1; x++, y--) {
                a[x][y] = cnt++;
            }
        }
    }
    cout << a[20][20] << endl;
    return 0;
}

答案：761

试题D：跑步锻炼

小蓝每天都锻炼身体。 正常情况下，小蓝每天跑 $1$ 千米。如果某天是周一或者月初（$1$ 日），为了 激励自己，小蓝要跑 $2$ 千米。如果同时是周一或月初，小蓝也是跑 $2$ 千米。 小蓝跑步已经坚持了很长时间，从 $2000$ 年 $1$ 月 $1$ 日周六（含）到 $2020$ 年 $10$ 月 $1$ 日周四（含）。请问这段时间小蓝总共跑步多少千米？

思路：

1.对着日历表数，不过貌似比赛的时候我数错了。。。。。

2.编程实现：

实在没想出来怎么模拟这玩意，于是参考了网上的答案，确实厉害，没有省一的我菜的安详。

参考博客：https://blog.csdn.net/qq_44378358/article/details/109133954

代码：

#include <iostream>

using namespace std;
typedef long long LL;

int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isRunYear(int y) {
    if ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {
        return true;
    }
    return false;
}

int getDay(int y, int m) { //获取当前月有多少天
    if (m != 2) {
        return day[m];
    } else if (isRunYear(y)){
        return 29;
    } else {
        return 28;
    }
}

int changeWeek(int &xingQi) {
    int x = xingQi;
    xingQi++;
    if (xingQi == 8) {
        xingQi = 1;
    }
    return x;
}

int main() {
    int num = 0; //除了每天必跑1公里之外加练的
    int sumday = 0;
    int week = 6;
    for (int y = 2000; y <= 2020; y++) {
        for (int m = 1; m <= 12; m++) {
                for (int d = 1; d <= getDay(y, m); d++) {
                    if (changeWeek(week) == 1 || d == 1) {
                        num++;
                    }
                    sumday++;
                    if (y == 2020 && m == 10 && d == 1) {
                        cout << sumday + num << endl;
                        system("pause");
                        return 0;
                    }
                }
            }
        }
    return 0;
}

答案：8879

试题$E$：七段码

【问题描述】

上图给出了七段码数码管的一个图示，数码管中一共有 $7$ 段可以发光的二 极管，分别标记为 $a, b, c, d, e, f, g$。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。

例如：$b$ 发光，其他二极管不发光可以用来表达一种字符。

例如：$c$ 发光，其他二极管不发光可以用来表达一种字符。

这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。

例如：$a, b, c, d, e$ 发光，$f, g$ 不发光可以用来表达一种字符。

例如：$b, f$ 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

思路：

**参考博客：**https://blog.csdn.net/kieson_uabc/article/details/109297342#comments_13672258

运用$DFS$ + 回溯 + 记录所有路径 + $set$去重。

自己想到了这个思路了，但是也是做了一下午后参考了一下网上相同思路的答案，终于做了出来。

这个思路建图是：这样’\0’也是可以走的，最后记录路径的时候只需要删除空格即可。

  a  b '\0'
  f  g  c
'\0' e  d 

我把图建成了这样，于是也出现了很多问题，把代码写的特别繁琐，最后也不想改了

0 a 0
f 0 b
1 g 1
e 0 c
0 d 0 

还有就是回溯的问题，想用那个$string$库的$pop.back()$来进行回溯，但还是因为菜啊！回溯用的不行，最后也只好放弃了，而这个思路用一个$deleteSpace$函数每一次都会整体改变字符串，根本不用考虑字符串回溯问题了，让代码变的特别简洁，哎，就这样吧。

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
char r[8];
char g[3][3] = {{'a', 'b','\0'}, {'f', 'g', 'c'}, {'\0', 'e', 'd'}};
set<string> st;
bool vis[3][3];
int cnt = 0;
int dx[8] = {-1, 0, 1, 0}, dy[8] = {0, 1, 0, -1};

void deleteSpace(string ss) {
    memset(r, '\0', sizeof r);
    int k = 0;
    for (int i = 0; i < ss.size(); i++) {
        if (ss[i] != '\0') {
            r[k++] = ss[i];
        }
    }
    sort(r, r + k);
}

void dfs(int a, int b, string s) {
    vis[a][b] = true;
    for (int i = 0; i < 4; i++) {
        int x = a + dx[i], y = b + dy[i];
        if (x >= 0 && x < 3 && y >= 0 && y < 3 && !vis[x][y]) {
            deleteSpace(s + g[x][y]);
            st.insert(r);
            dfs(x, y, r);
        }
    }
    vis[a][b] = false;
}

int main() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (g[i][j] != '\0') {
                string s = "";
                s += g[i][j];
                st.insert(s);
                dfs(i, j, s);
            }
        }
    }
    /*
    for (set<string> :: iterator it = st.begin(); it != st.end(); it++) {
        cout << *it << endl;
    }*/
    cout << st.size() << endl;
    system("pause");
    return 0;
}

试题$F$：成绩统计

【问题描述】

小蓝给学生们组织了一场考试，卷面总分为 $100$ 分，每个学生的得分都是 一个 $0$ 到 $100$ 的整数。 如果得分至少是 $60$ 分，则称为及格。如果得分至少为 $85$ 分，则称为优秀。 请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。

【输入格式】

输入的第一行包含一个整数 $n$，表示考试人数。 接下来 $n$ 行，每行包含一个 $0$ 至 $100$ 的整数，表示一个学生的得分。

【输出格式】

输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。

【样例输入】

7
80
92
56
74
88
100
0

【样例输出】

71%
43%

【评测用例规模与约定】

对于 $50%$的评测用例，$1 ≤ n ≤ 100$。 对于所有评测用例，$1 ≤ n ≤ 10000$

代码：

#include <iostream>

using namespace std;

int main() {
    double n;
    double a = 0, b = 0;
    scanf("%lf", &n);
    for (double i = 0; i < n; i++) {
        double grade;
        scanf("%lf", &grade);
        if (grade >= 85) {
            a++;
        }
        if (grade >= 60) {
            b++;
        }
    }
    printf("%.0f%%\n%.0f%%\n", (double)(a / n)*100, (double)(b / n)*100);
    cout << round((a / n) * 100) << "%" << endl; //round是自动四舍五入函数
    cout << round((b / n) * 100) << "%" << endl;
    return 0;
}

试题$G$:回文日期

【问题描述】

$2020$ 年春节期间，有一个特殊的日期引起了大家的注意：$2020$ 年 $2$ 月 $24$ 日。因为如果将这个日期按 $”yyyymmdd”$ 的格式写成一个 $8$ 位数是 $20200202$， 恰好是一个回文数。我们称这样的日期是回文日期。 有人表示 $20200202$ 是 “千年一遇” 的特殊日子。对此小明很不认同，因为 不到 $2$ 年之后就是下一个回文日期：$20211202$ 即 $2021$ 年 $12$ 月 $2$ 日。 也有人表示 $20200202$ 并不仅仅是一个回文日期，还是一个 $ABABBABA$ 型的回文日期。对此小明也不认同，因为大约 $100$ 年后就能遇到下一个 $ABABBABA$ 型的回文日期：$21211212$ 即 $2121$ 年 $12$ 月 $12$ 日。算不上 “千 年一遇”，顶多算 “千年两遇”。 给定一个 $8$ 位数的日期，请你计算该日期之后下一个回文日期和下一个 $ABABBABA$ 型的回文日期各是哪一天。

【输入格式】

输入包含一个八位整数 $N$，表示日期。

【输出格式】

输出两行，每行 $1$ 个八位数。第一行表示下一个回文日期，第二行表示下 一个 $ABABBABA$ 型的回文日期。

【样例输入】

20200202

【样例输出】

20211202
21211212

【评测用例规模与约定】

对于所有评测用例，$10000101 ≤ N ≤ 89991231$，保证 $N$ 是一个合法日期的 $8$ 位数表示。

思路：

知道真相的我眼泪掉下来，原来这道题$0$分了，这竟然跑了大概有$3$s这怎么能得分啊，样例都过不去，$sstream$效率太低了。然后去网上看好像可以直接打表！我怎么没想到啊-_-！算了一下符合$ABABBABA$格式的还不到100个数，打表岂不是净赚$20$分，说不定就能进国赛了，还有$ABABBABA$格式$A$与$B$不能相等，否则成了$AAAAAAAA$格式了，考试的时候也没想到啊！

然后问了一下大佬，说只需要枚举年份就可以，我恍然大悟了，马上花了40分钟把代码写出来，然后秒出结果！

代码：

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;
typedef long long LL;

void i2s(int num, string &s) { //数字转字符串
    stringstream ss;
    ss << num;
    ss >> s;
}

void s2i(int &num, string s) { //字符串转数字
    stringstream ss;
    ss << s;
    ss >> num;
}

bool isLeap(int year) {
    if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)) {
        return true;
    }
    return false;
}

bool judgeDay(int year, int month, int day) { //闰年非闰年分开判断
    int LeapMonthList[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int NoLeapMonthList[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if ( (isLeap(year) && day >= 1 && day <= LeapMonthList[month]) ||
         (!isLeap(year) && day >= 1 && day <= NoLeapMonthList[month]) ) {
             return true;
    }
    return false;
}

int main() {
    LL n;
    cin >> n;
    n /= 10000; //取得年份
    bool flag = false;
    for (int i = n + 1; i <= 8999; i++) {
        string num;
        i2s(i, num);
        //string temp = num;
        reverse(num.begin(), num.end());

        string pre = num.substr(0, 2), nex = num.substr(2, 4);
        int month, day;
        s2i(month, pre);
        s2i(day, nex);

        if (month >= 1 && month <= 12) {    //是0-12的月份
            if (judgeDay(i, month, day) && !flag) { //判断天数
                cout << i << pre << nex << endl;
                flag = true;
            }
            //判断ABABBABA
            if (judgeDay(i, month, day) && num[0] == num[2] && num[1] == num[3] && num[0] != num[1]) {
                cout << i << pre << nex << endl;
                break;
            }
        } else {
            continue;
        }
    }
    return 0;
}

考试时候的错误代码：

#include <iostream>
#include <string>
#include <sstream>
#include <ctime>
#include <algorithm>

using namespace std;
typedef long long LL;
void i2s(LL num, string &s) {
    stringstream ss;
    ss << num;
    ss >> s;
}

int main() {
    //clock_t start, end;
    //start = clock();
    LL n;
    cin >> n;
    int flag1 = 0;
    for (LL i = n + 1; i <= 89991231; i++) {
        string s;
        i2s(i, s);
        string s1 = s.substr(0, 4), s2 = s.substr(4, 8);
        reverse(s2.begin(), s2.end());
        if (s1 == s2 && flag1 == 0) {
            flag1 = 1;
            cout << i << endl;
        }
        if (s1 == s2 && s1[0] == s1[2] && s1[1] == s1[3]) {
            cout << i << endl;
            break;
        }
    }
    //end = clock();
    //cout << (double)((end - start) / CLOCKS_PER_SEC) << "s"; 
    return 0;
}

试题$H$:子串分值和

【问题描述】

对于一个字符串 $S$，我们定义 $S$ 的分值 $f(S)$ 为 $S$ 中出现的不同的字符个 数。例如 $f(”aba”) = 2$，$f(”abc”) = 3$,$ f(”aaa”) = 1$。 现在给定一个字符串 $S [0..n − 1]$（长度为 $n$），请你计算对于所有 $S$ 的非空 子串 $S [i.. j](0 ≤ i ≤ j < n)$,$f(S [i.. j])$ 的和是多少。

【输入格式】

输入一行包含一个由小写字母组成的字符串 $S$。

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

28

【样例说明】

子串    f值
a       1
ab      2
aba         2
abab        2
ababc       3
b       1
ba          2
bab         2
babc        3
a           1
ab          2
abc         3
b           1
bc          2
c           1 

【评测用例规模与约定】

对于 $20%$ 的评测用例，$1 ≤ n ≤ 10$;

对于 $40%$ 的评测用例，$1 ≤ n ≤ 100$;

对于 $50%$ 的评测用例，$1 ≤ n ≤ 1000$;

对于 $60%$ 的评测用例，$1 ≤ n ≤ 10000$;

对于所有评测用例，$1 ≤ n ≤ 100000$。

思路：

**参考博客:**https://blog.csdn.net/weixin_45483201/article/details/109137296?utm_source=app

考场上做的时候直接$O(n^3)$，然后用把切割出来的子串放到$set$中去重，然后取$set.size()$，大概8分左吧。

这题算是一道挺不错的思维题吧，也是在理解了挺久，复杂度直接到$O(n)$

1. 首先，在本题中，如果一个字符串中无重复字母，则把它定义成无重复字符串。

2. 我们可以直接认为对于每一个字符串，只有第一次在这个字符串中出现的字母对它所能形成的无重复字符串有贡献，例如对于”aba”，那么它所能行成的无重复字符串为”ab”，则我们就认为只是第一次出现的$a$和第一次出现的$b$对这个无重复字符串有贡献。其实仔细想一想，母串所能形成的每个子串中不同字母的数量和，就等价于母串中每个字母所能为母串贡献的无重复字符串数量和，（即每个字母能在多少个字符串中出现第一次）。

3. 然后就想到枚举每一个字母，统计它所能贡献的无重复字符串的数量。定义$last[i]$表示字符$i$在当前枚举点之前最后一次出现的位置，显然这个字母所能贡献的无重复字符串的左端点可以出现在$[last[i] + 1, now]$，右端点就在$[now, n]$之中，因此这样我们就是就能做到当前(类)字母只作用没有被当前(类)字母作用过的串，当前字母作用不到以它后面任意字母开头的所有子串，因此数量就是:
   $$ (i - last[i]) * (n - i + 1) $$

代码：

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
char str[N];
int last[30];

int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    LL res = 0;
    for (int i = 1; i <= n; i++) {
        res += 1ll * (i - last[str[i] - 'a']) * (n - i + 1);
        last[str[i] - 'a'] = i;
    }
    printf("%lld\n", res);
    return 0;
}

试题I：平面切分

【问题描述】

平面上有 $N$ 条直线，其中第 $i$ 条直线是 $y = A_i · x + B_i$。 请计算这些直线将平面分成了几个部分。

【输入格式】

第一行包含一个整数 $N$ 以下 $N$ 行，每行包含两个整数 $A_i , B_i$。

【输出格式】

一个整数代表答案。

【样例输入】

3
1 1
2 2
3 3

【样例输出】

6

【评测用例规模与约定】

对于 $50%$的评测用例，$1 ≤ N ≤ 4$, $−10 ≤ A_i , B_i ≤ 10$。 对于所有评测用例，$1 ≤ N ≤ 1000, −100000 ≤ A_i,B_i ≤ 100000$。

思路：

**原创作者：https://blog.csdn.net/weixin_44564818/article/details/109296327**

在一个平面内，如果所有的直线互不相交，则每添加一条直线，就会额外增加一个平面,即每添加一条非重边，非重边自身就会贡献一个平面（自身）；当这条直线与当前平面内的已有直线每产生一个不同位置的交点，这条直线对平面的总数量的贡献就额外多增加一个。

每添加一条直线时设置一个空$set$，将当前直线与当前平面内所有直线的交点$（x, y）$存入$set$，如果：

• 如果新新添加的一条直线不是重边，如果平行，那不用计算交点因此也不用存入$set$, 直接$continue$
• 如果新添加直线不是重边，如果与平面内直线相交，那么计算交点存入$set$，那么这条直线对平面的贡献个数就是$set.size() + 1$，最后判断如果此直线没有与任何一条原有直线重合则计入答案。

这里用$long double$的原因应该是为了防止精度丢失吧。

代码：

#include <iostream>
#include <set>
using namespace std;

const int N = 1e3 + 10;
typedef long long LL;
typedef long double LD;
LD s[N][2];
LL res = 0;
bool st[N];
pair<LD, LD> p; //用来记录交点

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i][0] >> s[i][1];
        set<pair<LD, LD>> points;
        for (int j = 0; j < i; j++) {
            if (st[j]) continue; //说明是重边 直接忽略
            if (s[i][0] == s[j][0]) { //如果两条直线斜率相等，判断平行还是重合
                if (s[i][1] == s[j][1]) { //如果新添加的直线是重边 退出循环 
                    st[i] = true;
                    break;
                } else {
                    continue;
                }
            }
            p.first = (s[j][1] - s[i][1]) / (s[i][0] - s[j][0]);
            p.second = s[j][0] * p.first + s[j][1];
            points.insert(p);
        }
        if (!st[i]) res += points.size() + 1; //如果st[i]不是重边 计入答案
    }
    cout << res + 1 << endl;
    return 0;
}

$J$题待补