2020蓝桥杯A组省赛第二场

试题A 门牌制作

本题总分：$5$ 分

【问题描述】

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

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【解题思路】

暴力枚举。

利用$for$循环，从$1$到$2020$。并利用一个变量$count$来记录数字$2$出现了几次，最后输出即可。

#include <bits/stdc++.h>

using namespace std;

int calc_2(int x)
{
    int ret = 0;
    while (x)
    {
        if (x % 10 == 2)
            ret++;
        x /= 10;
    }
    return ret;
}

void Solve()
{
    int count = 0;
    for (int i = 1; i <= 2020; i++)
        count += calc_2(i);

    printf("%d\n", count);
}

int main()
{
    Solve();

    return 0;
}

运行输出答案为 $624$。

试题B: 既约分数

本题总分：$5$ 分

【问题描述】

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

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【解题思路】

还是暴力枚举。

分子分母均从$1$到$2020$枚举，用变量$count$记录答案，如果分子分母的最大公约数 $(\ gcd\ )$ 为$1$，则$count++$。

#include <bits/stdc++.h>

using namespace std;

int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }

void Solve()
{
    int count = 0;
    for (int i = 1; i <= 2020; i++)
        for (int j = 1; j <= 2020; j++)
            if (gcd(i, j) == 1)
                count++;

    printf("%d\n", count);
}

int main()
{
    Solve();

    return 0;
}

运行输出答案为 $2481215$。

试题C: 蛇形填数

本题总分：$10$ 分

【问题描述】

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

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

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【解题思路】

模拟。

按红线记录层数，第$20$行$20$列的数应当在第$39$层。奇数层数字的增长方向为右上，偶数层数字增长方向为右下。

首先算出前38层共有多少数，再加上第39层的前半部分数，即可算出第20行20列的数。

$$\dfrac{38\times(38+1)}{2}+\left\lfloor\dfrac{39}{2}\right\rfloor = 761$$

试题D: 七段码

本题总分：$10$ 分

【问题描述】

小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有$7$ 段可以发光的二极管，分别标记为$a, b, c, d, e, f, g$。小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：$b$ 发光，其他二极管不发光可以用来表达一种字符。
例如：$c$ 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：$a, b, c, d, e$ 发光，$f, g$ 不发光可以用来表达一种字符。
例如：$b, f$ 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【解题思路】

搜索。

此题可以先用排列组合算一下所有的选法一共$\sum\limits_{i=0}^7C^i_7=2^7=128$种。

所以也可以把所有情况都列举出来，然后手动去判断。

如果用代码判断，则可以将$\\ a\\sim g\\ $ 编号为$1\sim7$。并建立如下图。

使用变量$count$记录答案，通过枚举边的编号，通过$dfs$判断在仅使用枚举到的边的情况下，图中存在几个连通块，如果仅有一个，则$count++$。

#include <bits/stdc++.h>

using namespace std;

vector<int> Map[10];

int cnt = 0;
int vis[10];
int uesd[10];

void DFS(int u)
{
    uesd[u] = 1;
    for (int i = 0; i < Map[u].size(); i++)
    {
        int v = Map[u][i];
        if (uesd[v] || !vis[v])
            continue;
        DFS(v);
    }
}

bool check()
{
    vector<int> p;
    p.clear();
    memset(uesd, 0, sizeof(uesd));
    for (int i = 1; i <= 7; i++)
    {
        if (vis[i])
            p.push_back(i);
    }
    int tmp = 0;
    for (int i = 0; i < p.size(); i++)
    {
        if (!uesd[p[i]])
        {
            DFS(p[i]);
            tmp++;
        }
    }
    if (tmp == 1)
        return true;
    return false;
}

void dfs(int num)
{
    if (num == 8)
    {
        if (check())
            cnt++;
        return;
    }
    vis[num] = 0;
    dfs(num + 1);
    vis[num] = 1;
    dfs(num + 1);
}

void BuildMap()
{
    Map[1].push_back(2), Map[1].push_back(6);
    Map[2].push_back(1), Map[2].push_back(3), Map[2].push_back(7);
    Map[3].push_back(2), Map[3].push_back(4), Map[3].push_back(7);
    Map[4].push_back(3), Map[4].push_back(5);
    Map[5].push_back(4), Map[5].push_back(6), Map[5].push_back(7);
    Map[6].push_back(1), Map[6].push_back(5), Map[6].push_back(7);
    Map[7].push_back(2), Map[7].push_back(3), Map[7].push_back(5), Map[7].push_back(6);
}

void Solve()
{
    BuildMap();

    dfs(1);

    cout << cnt;
}

int main()
{
    Solve();

    return 0;
}

运行输出答案为$80$。

试题E：平面分割

本题总分：$15$ 分

【问题描述】

$20$ 个圆和$20$ 条直线最多能把平面分成多少个部分？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

【解题思路】（转载）

作者：$Bluevarpi$
链接：https://www.zhihu.com/question/426034179/answer/1529833661
来源：知乎
著作权归作者所有。

我们将问题推广到更一般的情况：

设$m$个圆和$n$条直线做多能把平面分成$f(m,n)$个部分。

我们首先考虑$m$个圆的情况：

$2$个圆最多有$2$个交点，则$m$个圆最多有$2 \cdot \dbinom{m}{2}=m(m-1) $个交点。

每个圆都与其它$m-1$个圆各交于$2$个点，所以每个圆上都有$2(m-1)$个交点，则每个圆都被分割成了$2(m-1)$个小段，因此$m$个圆有$2m(m-1)$个小段

法一：

每增加一个圆弧小段就增加$2$个区域，因此第$m$个圆使平面增加了$2(m-1)$个区域。

则$f(m,0)=f(m-1,0)+2(m-1)$

等号两边对$2$到$m$进行求和，即

$\sum\limits_{k=2}^m f(k,0)=\sum\limits_{k=2}^m[f(k-1,0)+2(k-1)]$

注意到

$\sum\limits_{k=2}^mf(k,0)=\sum\limits_{k=2}^mf(k-1,0)+f(k,0)-f(1,0)$

则有

$f(m,0)=\sum\limits_{k=2}^m2(k-1)+f(1,0)$

显然，$1$个圆和$0$条直线将平面分成$2$个部分，即$f(1,0)=2$

$\therefore f(m,0)=m^2-m+2$

法二：根据平面图的欧拉公式(Euler’s formula)[^1]

$V-E+F=2$ (包括外边的平面)

$\therefore f(m,0)=F=2-V+E=2-m(m-1)+2m(m-1)=m^2-m+2$

于是我们就得到了$m$个圆最多将平面分割为$m^2-m+2$个部分

下面加入$n$条直线的情况

不难发现，第$n$条直线与其它$n-1$条直线最多交于$n-1$个点，与$m$个圆最多交于$2m$个点，如下图所示：

因此第$n$条直线与原来的图形最多交于$2m+(n-1)=2m+n-1$个点，则此时比$n-1$条直线的情况增加了$2m+n$个区域，

即$f(m,n)=f(m,n-1)+2m+n$

等号两边对$2$到$n$求和

$\sum\limits_{k=2}^nf(m,k)=\sum\limits_{k=2}^n[f(m,k-1)+2m+k]$

注意到

$\sum\limits_{k=2}^n=\sum\limits_{k=2}^n f(m,k-1)+f(m,n)-f(m,1)$

$\therefore f(m,n)=\sum\limits_{k=2}^n(2m+k)+f(m,1)$

因为$1$条直线和$m$个圆最多可将平面分为$(m^2-m+2)+2m=m^2+m+2$个部分，即$f(m,1)=m^2+m+2$

$\therefore f(m,n)=m^2+\dfrac{1}{2}n^2+2mn-m+\dfrac{1}{2}n+1$

我们再回归到本题

已知$(m,n)=(20,20)$，则$f(m,n)=1391$

故$20$个圆和$20$条直线最多能把平面分成$1391$个部分

参考

[^ 1]: 维基百科-欧拉示性数 https://en.m.wikipedia.org/wiki/Euler_characteristic

试题F：成绩统计

本题总分：$15$ 分

【问题描述】

小蓝给学生们组织了一场考试，卷面总分为$100$ 分，每个学生的得分都是一个$0$ 到$100$ 的整数。请计算这次考试的最高分、最低分和平均分。

【输入格式】

输入的第一行包含一个整数$n$，表示考试人数。

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

【输出格式】

输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

【样例输入】

7 
80 
92 
56 
74 
88 
99 
10

【样例输出】

99 
10 
71.29

【评测用例规模与约定】

对于$50\%$的评测用例， $1 \le n \le 100$。

对于所有评测用例，$1 \le n \le10000$。

【解题思路】

仅需五个变量，$n,Max,Min,Average,score$，分别存储考试人数，最高分，最低分，平均值，学生得分。在读取过程中就可以将答案求出。

#include <bits/stdc++.h>

using namespace std;

void Solve()
{
    int n, Max = 0, Min = 100, score;
    double Average = 0;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &score);
        Max = max(Max, score);
        Min = min(Min, score);
        Average += (double)score;
    }

    printf("%d\n%d\n%.2lf", Max, Min, Average / (double)n);
}

int main()
{
    Solve();

    return 0;
}

试题G：回文日期

本题总分：$20$ 分

【问题描述】

$ 2020$ 年春节期间，有一个特殊的日期引起了大家的注意：$2020$年$2$月$2$日。因为如果将这个日期按$“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 \le N \le 89991231$，保证$N$ 是一个合法日期的$8$位数表示。

【解题思路】

用$int$存$8$位的日期，直接暴力从当前日期开始枚举。

判断三点，是否为合法的日期，在合法的前提下去判断是否是回文日期，再去判断是否是$ABABBABA$型。

#include <bits/stdc++.h>

using namespace std;

int Month1[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int Month2[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline int isLeap(int x)
{
    return (!(x % 4) && (x % 100)) || (!(x % 400));
}

inline int Check_Date(int x)
{
    int Y = x / 10000;
    int M = (x / 100) % 100;
    int D = x % 100;

    if (!M || M > 12)
        return 0;
    if (isLeap(Y))
    {
        if (!D || D > Month2[M])
            return 0;
    }
    else
    {
        if (!D || D > Month1[M])
            return 0;
    }
    return 1;
}

int Check1(int x)
{
    int ix = x, y = 0;
    while (ix)
    {
        y = y * 10 + ix % 10;
        ix /= 10;
    }

    return (x == y);
}

inline int Check2(int x)
{
    //A B A B B A B A
    int pre1 = (x / 10000000), pre2 = (x / 1000000) % 10;
    int C1 = ((pre1 == ((x / 100000) % 10)) && (pre1 == (x / 100) % 10) && (pre1 == x % 10));
    int C2 = ((pre2 == (x / 10000) % 10) && (pre2 == (x / 1000) % 10) && (pre2 == (x / 10) % 10));

    return (C1 && C2);
}

void Solve()
{
    int Date;
    scanf("%d", &Date);

    int flag = 0;
    while (1)
    {
        Date++;
        if (Check_Date(Date))
        {
            if (Check1(Date) && !flag)
            {
                printf("%d\n", Date);
                flag = 1;
            }

            if (Check2(Date))
            {
                printf("%d\n", Date);
                break;
            }
        }
    }
}

int main()
{
    Solve();

    return 0;
}

试题H：子串分值

本题总分：$20$ 分

【问题描述】

对于一个字符串$S$，我们定义$S$ 的分值 $f(S)$ 为$S$中恰好出现一次的字符个数。例如$f (”aba”) = 1,\\ $ $f (”abc”) = 3,\\ $ $f (”aaa”) = 0$。

现在给定一个字符串$S[0…n-1]$（长度为$n$），请你计算对于所有$S$的非空子串 $S\left[i…j\right] (0 \le i \le j < n)$, $f (S\left[i… j\right])$ 的和是多少。

【输入格式】

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

【输出格式】

输出一个整数表示答案。

【样例输入】

ababc

【样例输出】

21

【样例说明】

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

总分值为$21$分。

【评测用例规模与约定】

对于$20\%$ 的评测用例，$1 \le n \le 10$；

对于$40\%$ 的评测用例，$1 \le n \le 100$；

对于$50\%$ 的评测用例，$1 \le n \le 1000$；

对于$60\%$ 的评测用例，$1 \le n \le 10000$；

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

【解题思路】

如果使用朴素的暴力算法，即枚举子串，再逐个数有多少个字母仅出现了一次，复杂度为$O(n^3)$。可以得到$40$分。写的好一点说不定可以拿到$50$分。所以这个题不能用直白的思路去解决。那么我们反过来，先看字母，再去求在多少个子串中仅出现了一次呢？

逐个枚举$S$中的字母。先从当前位置，向前枚举找到第一个和当前字母相同的字母。再从当前位置，向后枚举找到第一个和当前字母相同的字母，

例如：对于红色箭头指向的$a$（以下简称为$Ra$），我们要找的即为绿色箭头所指向的$a$（以下简称为$LGa,RGa$，$L,R$表示左右）。我们要求$Ra$对答案的贡献，即为在$LGa,RGa$之间，任意选择包含$Ra$的子串的方案数。由于$Ra$与$LGa$之间有$4$个字母(包含$Ra$，不包含$LGa$，下面也一样)，$Ra$与$RGa$之间有$2$个字母。故包含$Ra$的子串的个数共$4\times2=8$。

按照这种做法，复杂度最差为$O(n^2)$，可以拿到$60$分。如何再优化呢？

我们发现，要按照枚举字母，再求它的贡献的思路，$O(n)$去把每个字母都枚举一遍是必不可少的，而每次都向前枚举和向后枚举则需要重复花费大量的时间。例如上面那个例子，在枚举到$Ra$的时候，寻找$LGa$时便利了$s,d,c$,而枚举到$Ra$后面的$b$时，寻找前面的第一个$b$的过程中，又便利了$s,d,c$，这个地方显然是有优化的空间的。

我们可以通过定义数组$pos[27]$来记录从前往后遍历的过程中$a\sim z$，上次一出现的位置。这样就能在$O(n)$的复杂度内完成“当前位置，向前枚举找到第一个和当前字母相同的字母”的任务。同理，“当前位置，向后枚举找到第一个和当前字母相同的字母”也可以用一个相同的过程完成。之后我们只需要$O(n)$遍历一遍$S$，并且做做乘法，做做加法，就可以把答案求出来了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int Maxn = 100010;

char s[Maxn];
int pos[27];
int Before[Maxn], Behind[Maxn];

void Solve()
{
    scanf("%s", s + 1);

    int len = strlen(s + 1);
    for (int i = 1; i <= 26; i++)
        pos[i] = 0;
    for (int i = 1; i <= len; i++)
    {
        Before[i] = pos[s[i] - 'a' + 1];
        pos[s[i] - 'a' + 1] = i;
    }
    for (int i = 1; i <= 26; i++)
        pos[i] = len + 1;
    for (int i = len; i >= 1; i--)
    {
        Behind[i] = pos[s[i] - 'a' + 1];
        pos[s[i] - 'a' + 1] = i;
    }

    ll Ans = 0;
    for (int i = 1; i <= len; i++)
        Ans += (ll)(i - Before[i]) * (ll)(Behind[i] - i);

    printf("%lld", Ans);
}

int main()
{
    Solve();

    return 0;
}

试题I：荒岛探测

本题总分：$25$ 分

【题目描述】

科学家小蓝来到了一个荒岛，准备对这个荒岛进行探测考察。小蓝使用了一个超声定位设备来对自己进行定位。为了使用这个设备，小蓝需要在不同的点分别安装一个固定的发射器和一个固定的接收器。小蓝手中还有一个移动设备。定位设备需要从发射器发射一个信号到移动设备，移动设备收到后马上转发，最后由接收器接收，根据这些设备之间传递的时间差就能计算出移动设备距离发射器和接收器的两个距离，从而实现定位。 小蓝在两个位置已经安装了发射器和接收器，其中发射器安装在坐标$(x_A,y_A)$，接收器安装在坐标 $(x_B,y_B)$。小蓝的发射器和接收器可能在岛上，也可能不在岛上。小蓝的定位设备设计有些缺陷，当发射器到移动设备的距离加上移动设备到接收器的距离之和大于$L$ 时，定位设备工作不正常。当和小于等于$L$ 时，定位设备工作正常。为了安全，小蓝只在定位设备工作正常的区域探测考察。 已知荒岛是一个三角形，三个顶点的坐标分别为$(x_1,y_1),(x_2, y_2)(x_3, y_3)$。 请计算，小蓝在荒岛上可以探测到的面积有多大？

【输入格式】

输入的第一行包含五个整数，分别为$x_A, y_A, x_B, y_B, L$。 第二行包含六个整数，分别为$ x_1, y_1, x_2, y_2, x_3, y_3$。

【输出格式】

输出一行，包含一个实数，四舍五入保留$2$位小数，表示答案。 考虑到计算中的误差，只要你的输出与参考输出相差不超过$0.01$即可得分。

【样例输入】

10 6 4 12 12 
0 2 13 2 13 15

【样例输出】

39.99

【样例说明】

当输出为39.98、39.99或40.00时可以得分。

【评测用例规模与约定】

对于所有评测用例， 保证发射器的两个坐标不同。

$-1000\le x_A,y_A,x_B,y_B\le 1000,-1000\le x_1,y_1,x_2,y_2,x_3,y_3\le1000,-1000\le L\le 1000$

【解题思路】

不会QAQ。

试题J：字串排序

本题总分：$25$ 分

【题目描述】

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 $lan$ 排序，只需要 $1 $次交换。对于字符串 $qiao$ 排序， 总共需要 $4$ 次交换。小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要$ V$ 次交换，可是他忘了把这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母的字符串，对该串进行冒泡排序，正好需要 $V $次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

【输入格式】

输入的第一行包含一个整数V，小蓝的幸运数字。

【输出格式】

题面要求的一行字符串。

【样例输入1】

4

【样例输出1】

bbaa

【样例输入2】

100

【样例输出2】

jihgfeeddccbbaa

【评测用例规模与约定】

对于$30\%$ 的评测用例，$1 ≤ V ≤ 20$；

对于$50\%$ 的评测用例，$1 ≤ V ≤ 100$；

对于$100\%$ 的评测用例，$1 ≤ V ≤ 10000$；

【解题思路】

暂时不会，下面的是错误做法。待更新…

题目要求最短，字典序最小。我们可以大胆猜测，答案一定是一个单调不增的字符串，即从$z$降到$a$，并且一定是连续的，也就是说，不会出现$dba$这样的字符串，因为中间少了$c$。同时，对于这样的单调不增的字符串来说，将其冒泡排序，对于其中某个字符$x$而言，需要交换的次数为比他小的字符的个数的和，例如：$ccbbaa$，对于每个$c$，要交换$4$次，对于每个$b$，交换次数为$2$，故总交换次数为$4\times2+2\times2=12$

然后我们打一个表：

字符串	交换次数
$a$	$0$
$ba$	$1$
$cba$	$3$
$dcba$	$6$
$edcba$	$10$

其实根据这个表，我们可以得出一个很重要的结论：==表中的字符串，为对应长度的字符串中交换次数最多的==。例如$cba$交换次数为$3$，而$dcba$交换次数为$6$，那么交换次数为$4 \sim 6$的字符串长度一定是$4$。当字符串长度大于$26$时，交换次数最多的肯定是前面若干个$z$，随后是$yxwvu…cba$。

那么一个大胆的构造思路，就从脑中浮现出来了：

1. 计算出交换$V$次的字符串长度应该是多少，记为$length$；

2. 建立一长度为$length$且全为$a$的字符串，记为$S$；

3. 根据$V$，修改$S$中的字符。

例如$V=5$，先计算出长度应该为$4$，再令$S=”aaaa”$。此时交换次数为$1$，我们将其变成$”baaa”$，此时交换次数为$3$。再变成$”bbaa”$，此时交换次数为$4$。此时$b$和$a$的个数相同了，不能再加$b$了，改成把$b$变成$c$的过程。于是得到了$”cbaa”$，交换次数为$5$，从而将答案求出。