2020蓝桥杯C/C++ B组第二场

试题A :门牌制作

题意：计算1——2020有多少个2出现
直接暴力跑一边统计就好

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
int cnt(int x) {
    int re = 0;
    while(x) {
        if(x % 10 == 2) ++re;
        x /= 10;
    }return re;
}
signed main() {
    ll ans = 0;
    for(int i = 1; i <= 2020; ++i) {
        ans += cnt(i);
    }cout << ans << endl;//624
    return 0;
}

试题 B：既约分数

题意：求分子、分母均在[1,2020]的区间内时，分子、分母的最大公约数为1的情况有多少种
两重循环暴力即可，这里使用STL的__gcd()函数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
signed main() {
    ll ans = 0;
    for(int i = 1; i <= 2020; ++i) {
        for(int j = 1; j <= 2020; ++j) {
            if(__gcd(i, j) == 1) ++ans;
        }
    }cout << ans << endl;//2481215
    return 0;
}

试题 C：蛇形填数

题意：按蛇形填数，求第20行20列的数字是多少
可以直接模拟。但是因为求的元素比较特殊，行号和列号一致，这里推一下通式，设： $b_i = a_{ij}$
所以： $b_1 = 1, b_2 = 5, b_3 = 13, b_4 = 25, b_5 = 41$ ，则： $b_2 - b_1 = 4,b_3-b_2 = 8, b_4 - b_3 = 12$
即： $b_{n+1} - b_{n} = 4n$ 成立，累加可得： $b_n = 2n(n-1)+1$ ，其中 $b_1 = 1$ 所求为 $b_{20}$ ，代入可得答案为： $761$
下面给出模拟的代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int mod = 1000000009;
typedef long long ll;
ll dp[64][64];
signed main() {
    int cnt = 1;
    for(int i = 1; i <= 50; ++i) {
        if(i & 1) {//从下往上
            for(int x = i, y = 1; x >= 1 && y <= i; --x, ++y) {
                dp[x][y] = cnt++;
            }
        }else {//从上往下
            for(int x = 1, y = i; x <= i && y >= 1; ++x, --y) {
                dp[x][y] = cnt++;
            }
        }
    }cout << dp[20][20] << endl;//761
    return 0;
}

试题 D：跑步锻炼

题意：每天基础跑1km，若为周一或月初，加跑1km。求从[2000/1/1, 2020/10/1]间跑的路数
直接模拟，遍历从2000/1/1到2020/10/1的所有天数，并且注意判断闰年和星期

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int arr[][16] = {{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
signed main() {
    ll ans = 0;
    int cnt = 5;//0-6设为星期一~星期天
    for(int i = 2000; i <= 2020; ++i) {
        int mon = (i == 2020) ? 10 : 12;
        int flag = ((i % 4 == 0 && i % 100 != 0) || i % 400 == 0) ? 0 : 1;//0闰、1非闰
        for(int j = 1; j <= mon; ++j) {
            int day = arr[flag][j-1];
            if(mon == 10 && j == 10) day = 1;
            for(int k = 1; k <= day; ++k) {
                if(cnt == 0 || k == 1) ans += 2;
                else ++ans;
                cnt = (cnt + 1) % 7;
            }
        }
    }cout << ans << endl;//8879
    return 0;
}

试题 E：七段码

题意：用七段码任意的凑出仅有一个联通块的数目
因为图论学的比较多，这里就不直接去算了，上图暴力穷举搜索就好。
假设从左上角开始，顺时针下每一个点分别记为 $1, 2, 3,4, 5, 6$ ，然后暴力穷举每一条边的存在情况，建无向图然后搜索联通块数目，然后统计合法的情况就可以了

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
vector <int> G[12];//6个节点
bitset<12> vis;
queue<int> q;
void bfs(int s) {
    while(!q.empty()) q.pop();
    q.push(s); vis[s] = 1;
    while(!q.empty()) {
        int from = q.front(); q.pop();
        for(int i = 0; i < G[from].size(); ++i) {
            int to = G[from][i];
            if(!vis[to]) {
                q.push(to);
                vis[to] = 1;
            }
        }
    }
}
signed main() {
    int ans = 0;
    for(int a = 0; a <= 1; ++a) {//因为情况比较少就直接开多重循环了，情况比较多可以转2进制枚举或者递归
        for(int b = 0; b <= 1; ++b) {
            for(int c = 0; c <= 1; ++c) {
                for(int d = 0; d <= 1; ++d) {
                    for(int e = 0; e <= 1; ++e) {
                        for(int f = 0; f <= 1; ++f) {
                            for(int g = 0; g <= 1; ++g) {
                                for(int i = 0; i <= 6; ++i) G[i].clear();
                                vis.reset();
                                if(a & 1) G[1].push_back(2), G[2].push_back(1);
                                if(b & 1) G[2].push_back(3), G[3].push_back(2);
                                if(c & 1) G[3].push_back(4), G[4].push_back(3);
                                if(d & 1) G[4].push_back(5), G[5].push_back(4);
                                if(e & 1) G[5].push_back(6), G[6].push_back(5);
                                if(f & 1) G[6].push_back(1), G[1].push_back(6);
                                if(g & 1) G[6].push_back(3), G[3].push_back(6);
                                int cnt = 0;
                                for(int i = 1; i <= 6; ++i) {
                                    if(vis[i] || G[i].size() == 0) continue;
                                    bfs(i);
                                    ++cnt;
                                }
                                if(cnt == 1) ++ans;
                            }
                        }
                    }
                }
            }
        }
    }cout << ans << endl;
    return 0;
}

试题 F：成绩统计

题意：给定成绩序列，统计出及格率和优秀率
直接模拟就好，记得开 $double$ ，及格人数中含优秀人数。四舍五入问题直接使用控制符指定位数 $double$ 会自动四舍五入

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
ll n;
signed main() {
    double ans1 = 0.0, ans2 = 0.0;//分别统计及格，优秀人数
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i) {
        int tmp;
        scanf("%d", &tmp);
        if(tmp < 60);
        else {
            ++ans1;
            if(tmp >= 85) ++ans2;
        }
    }
    printf("%.0lf%\n%.0lf%\n", ans1/n *100, ans2/n *100);
    return 0;
}

试题G：回文日期

题意：计算给出日期的下一个回文日期、AB回文日期
注意判断闰年
这里考虑一下直接暴力，一个一个去判断日期是否回文，然后记录。因为实在太暴力了，而且还过了蓝桥杯的评测系统，所以提一句。可以考虑优化：将 $1000 \le year \le 8999$ 的回文序列构建出来，然后查表，或者考虑剪枝优化都可以

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int year, month, day;
int arr[][16] = {{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
string turn(int num, int size) {//构造字符串
    string ans = "";
    while(num) {
        ans += num % 10 + '0';
        num /= 10;
    }
    while(ans.size() < size) ans += "0";
    reverse(ans.begin(), ans.end());
    return ans;
}

bool check1(string s) {//判断回文
    string rs = s;
    reverse(s.begin(), s.end());
    return (rs == s);
}
bool check2(string s) {//判断AB回文
    return (s[0] != s[1] && s[0] == s[2] && s[2] == s[5] && s[5] == s[7] && s[1] == s[3] && s[3] == s[4] && s[4] == s[6]);
}

signed main() {
    scanf("%4d%2d%2d", &year, &month, &day);
    string str1 = "", str2 = "";
    for(int m = month; m <= 12; ++m) {
        int dd = ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) ? 0 : 1;
        dd = arr[dd][m];
        for(int d = day; d <= dd; ++d) {
            if(m == month && d == day) continue;//当天不判断
            string tmp = turn(year, 4) + turn(m, 2) + turn(d, 2);
            if(check1(tmp)) {
                if(!str1.size()) str1 = tmp;
                if(!str2.size()) {
                    if(check2(tmp)) str2 = tmp;
                }
            }
        }
    }//判断当年

    for(int y = year + 1;!str1.size() || !str2.size(); ++y) {
        for(int m = 0; m < 12; ++m) {
            int dd = ((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) ? 0 : 1;
            dd = arr[dd][m];
            for(int d = 1; d <= dd; ++d) {
                string tmp = turn(y, 4) + turn(m + 1, 2) + turn(d, 2);
                if(check1(tmp)) {
                    if(!str1.size()) str1 = tmp;
                    if(!str2.size()) {
                        if(check2(tmp)) str2 = tmp;
                    }
                }
            }
        }
    }cout << str1 << '\n' << str2 << '\n';
    return 0;
}

试题 H：字串分值和

题意：查询字符串所有子串中，不同的字符的和的总和有多少
我们去考虑每个字符在最后的总和上的贡献，我们可以看到样例中：对字串从 $1$ 开始的，第一个字符出现了 $n$ 次、对从第 $2$ 个开始的，第二个字符出现了 $2(n-1)$ 。由此类推：第 $a_i$ 个出现了 $i(n - i + 1)$ 次，对于一次遍历过程中，我们可以将第 $i$ 个位置的字符对应的位置赋值为 $i$ ，对于此后的 $n - i + 1$ 次循环中都加上它。
在这里，我们不需要担心重复的问题，我们每更新一次，加一次和。当现在字符前有字符与它相同，则从此位开始的后续字串中，此位才存在贡献，前面存在相同的字符没有贡献

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int arr[32];
signed main() {
    string s;
    cin >> s;
    long long sum = 0;
    for(int i = 0; i < s.size(); ++i) {
        arr[s[i] - 'a'] = i + 1;
        for(int i = 0; i < 26; ++i) sum += arr[i];
    }cout << sum << endl;
    return 0;
}

试题 I：平面切分

题意：给定n条直线，求这些直线分出的面有多少个
明显和直线分平面公式有关，直线分平面时，新增的平面数 = 这条线与前面的线的交点的数目 + 1
很明显，题目中给出的直线可能会重复，有可能会存在交点，我们就要去重，然后找交点数目就可以给出答案了，我们这里算出交点，然后存放到 $set$ 中统计
易得 $x = \frac {B_2 - B_1}{A_1 - A_2}, y=\frac {A_1 B_2 - A_2 B_1} {A_1 - A_2}$ ,注意统计时不要除 $0$
我们对每一条线去统计它前面出现的线与它的交点数目，然后累加答案就好

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;

set<pair<ll, ll> > line;
int n;
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//别用sc和read
    cin >> n;
    ll ans = 2;
    for(int i = 1; i <= n; ++i)  {
        int a, b;
        cin >> a >> b;
        int tmp = line.size();
        line.insert(make_pair(a, b));
        if(i > 1 && line.size() > tmp) {//如果是重复的点就不用再算
            if(i > 1 && line.size() > tmp) {
                set<pair<double, double> > node;
                for(set<pair<ll,ll> > :: iterator it = line.begin(); it != line.end(); ++it) {
                    ll A1 = a, A2 = it->first, B1 = b, B2 = it->second;
                    if(it->first == a || A1 - A2 == 0) continue;//去除平行线
                    double x = (double) (B2 - B1) / (A1 - A2);
                    double y = (double) (A1 * B2 - A2 * B1) / (A1 - A2);
                    node.insert(make_pair(x, y));
                }
                ans += node.size() + 1;
            }
        }
    }cout << ans << endl;
    return 0;
}

试题 J：字串排序

题意：求出冒泡排序下交换次数为n的最小字典序字符串
我们知道，要求字典序最小，首先要使得字符串长度最短，并且冒泡排序在最坏的情况下要交换 $\frac {n(n-1)}{2}$ 次，所以设字符串长度为 $k$ ，则 $k(k-1) \ge 2n$ ，所以字符串的长度为： $\lceil \frac {1 + \sqrt{4n + 1}} {2} \rceil$ 。
我们可以由输入数据确定下来 $k \le 101$ ，那么直接用字符倒着排是不行的，因为最多只有 $26$ 个字母。所以我们不能直接去考虑倒排，要转换思路
~~写不动了，等日后再补~~