小花生

study & life record.

第十一届蓝桥杯软件赛省赛C++ A组

发表于 分类于 ，

第十一届蓝桥杯软件赛省赛C++ A组 题解。

填空题

1. 门牌制作

遍历1到2020，计数即可，624

2. 既约分数

遍历分子分母，计数gcd为1的即可，2481215

3. 蛇形填数

数学问题，1 + … + 38 + 20 = 761

4. 七段码

二进制遍历所有情况，能一遍搜完的为可行解，共有 80 种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int vis[10];
vector<int>g[10];
int cntt;

void dfs(int u, set<int>&a){
    vis[u] = 1;
    cntt++;
    for(auto &v : g[u]){
        if(a.count(v) && !vis[v]){
            dfs(v, a);
        }
    }
}

int main(){
    g[0].emplace_back(1);
    g[0].emplace_back(5);
    g[1].emplace_back(0);
    g[1].emplace_back(2);
    g[1].emplace_back(6);
    g[2].emplace_back(1);
    g[2].emplace_back(3);
    g[2].emplace_back(6);
    g[3].emplace_back(2);
    g[3].emplace_back(4);
    g[4].emplace_back(3);
    g[4].emplace_back(5);
    g[4].emplace_back(6);
    g[5].emplace_back(0);
    g[5].emplace_back(4);
    g[5].emplace_back(6);
    g[6].emplace_back(1);
    g[6].emplace_back(2);
    g[6].emplace_back(4);
    g[6].emplace_back(5);

    int res = 0;
    for(int i = 1; i < 1 << 7; i++){
        set<int>a; int cnt = 0;
        for(int k = 0; k < 7; k++){
            if(i >> k & 1) a.emplace(k), cnt++;
        }

        cntt = 0; memset(vis, 0, sizeof vis);
        dfs(*a.begin(), a);
        if(cnt == cntt) res++;
    }

    cout << res;
    return 0;
}

程序题

6. 回文日期

遍历年份生成回文子串，再判断该回文日期是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

int is_leap(int y)
{
    if (y % 4 == 0 && y % 100 != 0 || y % 400 == 0) return 1;
    else return 0;
}

bool isclca(int y, int m, int d)
{
    if (m <= 0 || m > 12) return 0;
    int days = months[m];
    if (m == 2) days += is_leap(y);
    if (d <= 0 || d > days) return 0;
    return 1;
}

int main()
{
    int day1, day2;
    cin >> day1 >> day2;
    int cnt = 0;
    int y1 = day1 / 10000, y2 = day2 / 10000;
    for (int i = y1; i <= y2; i++)
    {
        int x = i, r = i;
        for (int j = 0; j < 4; j++)
        {
            x = x * 10 + r % 10;
            r /= 10;
        }
        if (x > day2 || x < day1) continue; //操作后的日期可能不在范围内，需要特判
        int m = x % 10000 / 100;
        int d = x % 100;
        if (isclca(i, m, d) == true) cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

7. 子串分值

​ 利用乘法原理计算每一个字母占有的分值，O（n）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    string s; cin >> s;
    vector<int>v(26, -1);
    int n = s.length();
    vector<int>pre(n, -1), nex(n, n);
    for(int i = 0; i < n; i++){
        pre[i] = v[s[i] - 'a'];
        if(v[s[i] - 'a'] != -1)
            nex[v[s[i] - 'a']] = i;
        v[s[i] - 'a'] = i;
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        res += (i - pre[i]) * (nex[i] - i);
    cout << res;
    return 0;
}