第十一届蓝桥杯省赛C++A组-部分题解

题意：统计 \([1,2020]\) 所有整数中，数码 \(2\) 出现的次数

分析：直接暴力枚举即可：

inline int f(int n){
      int ans=0;
      while(n) ans+=(n%10==2),n/=10;
      return ans;
}
...
int ans=0;
for(int i=1;i<=2020;i++) ans+=f(i);

输出为 \(624\)

B 既约分数

题意：对于满足 \(\displaystyle a,b\in Z，{a\over b}\) 为最简分数的分数称为既约分数，求 \(1\leq a,b\leq 2020\) 的既约分数个数

分析：暴力枚举 \(a,b\) ，用 gcd 判是否互质

int ans=0;
for(int a=1;a<=2020;a++)
      for(int b=1;b<=2020;b++)
            ans+=(__gcd(i,j)==1);

输出为 \(2481215\)

C 蛇形矩阵

题意：给出如下矩阵，求第 \(20\) 行 \(20\) 列

1 2 6 7 ...
3 5 8 ...
4 9 ...
10 ...
...

分析：考虑令 \(f_n\) 为第 \(n\) 行 \(n\) 列的值

不难看出，\(f_n\) 转移至 \(f_{n+1}\) 需要自己所在斜线走一半+下一条斜线走完+\(f_{n+1}\) 所在斜线走一半

根据各斜线的长度，不难列出转移方程 \(f_{n+1}=f_n+n-1+2n+n+1=f_n+4n\) ，可解出 \(\displaystyle f_n=4\sum_{i=1}^{n-1}i+f_1=2n(n-1)+1\)

代入 \(n=20\) 得到 \(f_{20}=761\)

D 七段码

题意：求多少种不同的七段码表示方法，各个亮起的灯管互相连接，且至少有一个灯管亮起

分析：用数组储存灯管间的连接情况，枚举 \(2^7\) 种情况，用 bfs 检查是否满足，统计答案即可

#include<bits/stdc++.h>
using namespace std;
bool connect[7][7]={
    {0,1,0,0,0,1,0},
    {1,0,1,0,0,0,1},
    {0,1,0,1,0,0,1},
    {0,0,1,0,1,0,0},
    {0,0,0,1,0,1,1},
    {1,0,0,0,1,0,1},
    {0,1,1,0,1,1,0}
};
inline int isconnect(int S){
    int que[16],Head=0,Tail=0,NS=0;
    bool vis[16]={0};
    for(int i=0;i<7;i++) if( (S>>i)&1 ){
        que[++Tail]=i;
        vis[i]=1;
        break;
    }
    while(Head<Tail){
        int now=que[++Head];
        NS|=1<<now;
        for(int i=0;i<7;i++)
            if( ((S>>i)&1)&&connect[now][i]&&!vis[i] ){
                que[++Tail]=i;
                vis[i]=1;
            }
    }
    return NS==S;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Ans=0;
    for(int i=1;!(i>>7);i++) Ans+=isconnect(i);
    cout<<Ans;
    cout.flush();
    return 0;
}

输出为 \(80\)

E 直线与圆

题意：用 \(20\) 条直线与 \(20\) 个圆，求最多能将平面分为几个部分

分析：任意线（包括直线与曲线）之间，不交于同一点，则能将平面分为尽可能多的部分

根据欧拉定理 \(V-E+F-T=1,T=0\) ，求解出 \(F=1+E-V\) ，只需求解出点数 \(V\) 与边数 \(V\) 即可求解

根据我们的分析，任意两直线即可有一交点，个数为 \(\displaystyle (^{20}_2)\) ；任意两圆之间有两个交点，个数为 \(\displaystyle 2\cdot (^{20}_2)\) ；任意圆与直线之间有两个交点，个数为 \(20\times 20\times 2\)

故 \(\displaystyle V=(^{20}_2)+2\cdot (^{20}_2)+20\times 20\times 2=1370\)

同样根据我们的分析，一条直线被剩余的 \(19\) 条直线各交于一点，被 \(20\) 个圆各交于两点，故线上有 \(19+20\times 2=59\) 个点，一条直线被分为 \(60\) 条边；一个圆被剩余的 \(19\) 个圆、 \(20\) 条直线各交于两点，共 \((19+20)\times 2=78\) 个点，一个圆被分为 \(78\) 条边

故 \(\displaystyle E=60\times 20+78\times 20=2760\)

因此得到答案： \(\displaystyle F=1+2760-1370=1391\)

F 成绩分析

题意：给出 \(n\) 个学生的成绩，求最高分、最低分与平均值

分析：直接在输入的时候储存最大值、最小值和分数和，最后分数和除去人数得到平均分

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N,S,MinS,MaxS,SumS;
    cin>>N>>S;
    MinS=MaxS=SumS=S;
    for(int i=2;i<=N;i++)
        cin>>S,MinS=min(MinS,S),MaxS=max(MaxS,S),SumS+=S;
    cout<<MaxS<<'\n'<<MinS<<'\n'<<fixed<<setprecision(2)<<SumS*1.0/N;
    cout.flush();
    return 0;
}

G 回文年份

题意：输入一个日期，输出严格后于日期的第一个 ABCDDCBA 型日期，和第一个 ABABBABA 型日期。保证有解。

分析：第一种日期，直接枚举对应月份的对应日期，进行翻转，储存好 \(366\) 个日期后排序，查找第一个比输入大的即可（数据量太小，懒得写二分了）。第二种日期，由于月份和日期相同，直接枚举月份，进行翻转，储存好 \(12\) 个日期后和第一个储存方法相同。

#include<iostream>
#include<algorithm>
using namespace std;
int Day1[512],Day2[512];
inline int built(int month,int day){
    return ((day%10*10+day/10)*100+(month%10*10+month/10))*10000+month*100+day;
}
inline void pre(){
    int cntday[]={0,31,29,31,30,31,30,31,31,30,31,30,31},CntDay1=0;
    for(int month=1;month<=12;month++)
        for(int day=1;day<=cntday[month];day++)
            Day1[++CntDay1]=built(month,day);
    sort(Day1+1,Day1+367);
    for(int month=1;month<=12;month++)
        Day2[month]=built(month,month);
    sort(Day2+1,Day2+13);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pre();
    int N;
    cin>>N;
    for(int i=1;i<=366;i++) if(Day1[i]>N) {
        cout<<Day1[i]<<'\n';
        break;
    }
    for(int i=1;i<=12;i++) if(Day2[i]>N) {
        cout<<Day2[i]<<'\n';
        break;
    }
    cout.flush();
    return 0;
}

H 子串序列

题意：求一个字符串 \(S\) 的所有子串中，每个子串出现仅一次的字符个数和

分析：对于每一个字符单独考虑：对于第 \(i\) 个字符 \(c\) ，设其前面第一个与之相同的字符出现的位置为 \(pre_i\) （没有则为 \(0\)），后面第一个为 \(nxt_i\) （没有则为 \(n+1\)）

则对于满足 \(l\in(pre_i,i],r\in [i,nxt_i)\) 的所有区间 \([l,r]\) ，仅出现一个字符 \(c\) ，故对每个区间都产生 \(1\) 的贡献，总贡献即为 \((i-pre_i)\cdot (nxt_i-i)\) ，每个统计起来即可

#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
string s;
int Pre[MAXN],Nxt[MAXN],PreIndex[26];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        if(PreIndex[s[i]-'a']) Nxt[ PreIndex[s[i]-'a'] ]=i+1;
        Pre[i+1]=PreIndex[s[i]-'a'];
        Nxt[i+1]=s.size()+1;
        PreIndex[s[i]-'a']=i+1;
    }
    ll Ans=0;
    for(int i=1;i<=s.size();i++) Ans+=1ll*(i-Pre[i])*(Nxt[i]-i);
    cout<<Ans;
    cout.flush();
    return 0;
}

I 荒岛探测

题意：给定一个三角形荒岛，在荒岛上的某个人距离两给定点的距离之和不得超过给定值 \(L\) ，问其可覆盖的面积大小

分析：（口胡算法，现场未实现）

动点到两顶点距离之和不超过某定值，图形为一椭圆。问题等价于给定椭圆与给定三角形的交集图形大小。

在椭圆上逆时针顺序取 \(10^6\) 个点，按序连接，构成 \(10^6\) 个向量。将这些向量与三角形的三个向量求解半平面交，若有交集，则输出大小；否则输出 \(0\)

J 字串排序

题意：求解一字符串，满足条件：按照冒泡排序算法，需要交换的次数为给定次数 \(V\) ；若有多解，输出最短的；若仍有多杰，输出字典序最小的

分析：待补