2020 第十一届蓝桥杯省赛第二场 B组 C/C++

门牌制作

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
int main() {
    int cnt = 0;
    rep(i, 1, 2020) {
        int now = i;
        while (now) {
            if (now % 10 == 2) ++cnt;
            now /= 10;
        }
    }
    cout << cnt << '\n';  // 624
    return 0;
}

既约分数

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
int main() {
    int cnt = 0;
    rep(i, 1, 2020) rep(j, 1, 2020) cnt += __gcd(i, j) == 1;
    cout << cnt << '\n';  // 2481215
    return 0;
}

蛇形填数

#include <bits/stdc++.h>
using namespace std;
void put(int x, int y, int val) {
    if (x == 20 and y == 20) cout << val << endl, exit(0);
    if (x == 1 and y % 2 == 1)
        put(x, y + 1, ++val);
    else if (y == 1 and x % 2 == 0)
        put(x + 1, y, ++val);
    else if ((x + y) % 2 == 1)
        put(x + 1, y - 1, ++val);
    else
        put(x - 1, y + 1, ++val);
}
int main() {
    put(1, 1, 1); // 761
    return 0;
}

跑步锻炼

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
inline bool isLeapYear(int y) {
    return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}
bool isDate(int n) {
    int y = n / 10000;
    int m = n / 100 % 100;
    int d = n % 100;
    if (m < 1 || m > 12) return 0;
    if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12)
        return d >= 1 && d <= 31;
    else if (m == 2) {
        if (isLeapYear(y))
            return d >= 1 && d <= 29;
        else
            return d >= 1 && d <= 28;
    } else
        return d >= 1 && d <= 30;
}
int nextDate(int n) {
    int y = n / 10000;
    int m = n / 100 % 100;
    int d = n % 100;
    if (m == 12) {
        if (d == 31)
            y += 1, m = 1, d = 1;
        else
            d += 1;
    } else if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10) {
        if (d == 31)
            m += 1, d = 1;
        else
            d += 1;
    } else if (m == 2) {
        if (isLeapYear(y)) {
            if (d == 29)
                m += 1, d = 1;
            else
                d += 1;
        } else {
            if (d == 28)
                m += 1, d = 1;
            else
                d += 1;
        }
    } else {
        if (d == 30)
            m += 1, d = 1;
        else
            d += 1;
    }
    return y * 10000 + m * 100 + d;
}
int main() {
    int cnt = 0, th = 5;
    for (int i = 20000101; i <= 20201001; i = nextDate(i)) {
        if (th + 1 == 1 || i % 100 == 1)
            cnt += 2;
        else
            ++cnt;
        th = (th + 1) % 7;
    }
    cout << cnt << '\n';  // 8879
    return 0;
}

七段码

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int fa[N];
void init() {
    for (int i = 0; i < N; ++i) fa[i] = i;
}
int Find(int x) {
    if (x != fa[x]) fa[x] = Find(fa[x]);
    return fa[x];
}
bool isOn[N];
void merge(int x, int y) {
    if (!isOn[x] || !isOn[y]) return;
    fa[Find(y)] = Find(x);
}
bool isOk(int sta) {
    init();
    for (int i = 1; i <= 7; ++i) {
        isOn[i] = sta & 1;
        sta >>= 1;
    }
    merge(1, 2);
    merge(1, 6);
    merge(2, 3);
    merge(2, 7);
    merge(3, 7);
    merge(3, 4);
    merge(4, 5);
    merge(5, 6);
    merge(5, 7);
    merge(6, 7);
    int blocks = 0;
    for (int i = 1; i <= 7; ++i)
        if (isOn[i]) blocks += (i == Find(i));
    return blocks == 1;
}
int main() {
    int cnt = 0;
    for (int i = 1; i < (1 << 7); ++i) cnt += isOk(i);
    cout << cnt << '\n';  // 80
    return 0;
}

成绩统计

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x, ok = 0, good = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        if (x >= 60) ++ok;
        if (x >= 85) ++good;
    }
    double r1 = ok * 100.0 / n;
    double r2 = good * 100.0 / n;
    printf("%.0lf%%\n%.0lf%%\n", r1, r2);
    return 0;
}

回文日期

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
inline bool isLeapYear(int y) {
    return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}
int nextDate(int n) {
    int y = n / 10000;
    int m = n / 100 % 100;
    int d = n % 100;
    if (m == 12) {
        if (d == 31)
            y += 1, m = 1, d = 1;
        else
            d += 1;
    } else if (m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10) {
        if (d == 31)
            m += 1, d = 1;
        else
            d += 1;
    } else if (m == 2) {
        if (isLeapYear(y)) {
            if (d == 29)
                m += 1, d = 1;
            else
                d += 1;
        } else {
            if (d == 28)
                m += 1, d = 1;
            else
                d += 1;
        }
    } else {
        if (d == 30)
            m += 1, d = 1;
        else
            d += 1;
    }
    return y * 10000 + m * 100 + d;
}
int digit[10];
bool isPalindrome(int n) {
    for (int i = 1; i <= 8; ++i) {
        digit[i] = n % 10;
        n /= 10;
    }
    for (int L = 1, R = 8; L <= R; ++L, --R)
        if (digit[L] != digit[R]) return 0;
    return 1;
}
inline bool ABAB() {
    return digit[1] != digit[2] && digit[1] == digit[3] && digit[2] == digit[4];
}
int main() {
    int n;
    cin >> n;
    int x = nextDate(n);
    int ans = 0;
    while (1) {
        if (isPalindrome(x)) {
            if (!ans) ans = x;
            if (ABAB()) break;
        }
        x = nextDate(x);
    }
    printf("%d\n%d\n", ans, x);
    return 0;
}

子串分值和

将枚举区间算权值的问题转化为枚举点对总权值的贡献的问题，也就是枚举单点所能贡献的区间。

简单来说就是，将题面转化为：每个字符串内，只有第一次出现的字符才会对这个字符串产生贡献。那么枚举每个字符的贡献，处理一下它上次出现的位置即可。

#include <bits/stdc++.h>
#define ch str[i] - 'a'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int last[30], n;
char str[N];
int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += 1ll * (i - last[ch]) * (n - i + 1);
        last[ch] = i;
    }
    printf("%lld\n", ans);
    return 0;
}

一道很类似的题目：http://lx.lanqiao.cn/problem.page?gpid=T792
唯一的不同在于，权值的定义是只出现了一次的字符。那么处理一下其后第一次出现的字符位置即可。

#include <bits/stdc++.h>
#define pr(x) printf("%lld\n", (x))
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
char s[N];
#define ch s[i] - 'a'
int last[30];
int nxt[N];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) {
        if (last[ch]) nxt[last[ch]] = i;
        last[ch] = i;
    }
    memset(last, 0, sizeof last);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (!nxt[i]) nxt[i] = n + 1;
        ans += 1LL * (i - last[ch]) * (nxt[i] - i);
        last[ch] = i;
    }
    pr(ans);
    return 0;
}

平面切分

给出n条直线， $y=A_i x+B_i$

计算这些直线将平面分成了几个部分

$n\le 10^3$

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
set<pii> st;
pii a[1005];
int main() {
    int n;
    cin >> n;
    pii t;
    int p = 0;
    for (int i = 1; i <= n; ++i) {  // 去重
        cin >> t.first >> t.second;
        if (!st.count(t)) {
            a[++p] = t;
            st.insert(t);
        }
    }
    int ans = 1;  // 初始就是一个平面
    pair<long double, long double> u;
    set<pair<long double, long double> > points;
    for (int i = 1; i <= p; ++i) {
        for (int j = i + 1; j <= p; ++j) {
            if (a[i].first == a[j].first) continue;
            u.first = 1.0L * (a[j].second - a[i].second) /
                      (a[i].first - a[j].first);            //交点的x坐标
            u.second = a[i].first * u.first + a[i].second;  //交点的y坐标
            points.insert(u);
        }
        ans += points.size() + 1;
        // 其他直线 将 i直线 切割为 线上的交点数量+1部分
        points.clear();
    }
    cout << ans << '\n';
    return 0;
}

字串排序

30分可以直接暴力出

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int countBubbleSort(string s) {
    int res = 0;
    bool f = 0;
    do {
        f = 0;
        for(int i = 1, sz = s.length(); i < sz; ++i) {
            if(s[i] < s[i - 1]) {
                swap(s[i], s[i - 1]);
                ++res;
                if(!f)    f = 1;
            }
        }
    } while (f);
    return res;
}
string ans[25];
bool fin = 0;
inline int getSum(int n) {
    return (1 + n) * (n) / 2;
}
bool isFin(int n) {
    int low = getSum(n - 1);
    int up = getSum(n);
    for(int i = low ; i <= up; ++i) {
        if(ans[i] == "")return 0;
    }
    return 1;
}
void dfs(string s, int len) {
    if(fin)return;
    if(len == 0) {
        int cnt = countBubbleSort(s);
        if(ans[cnt] == "") {
            ans[cnt] = s;
            if(isFin(s.size()))fin = 1;
        }
        return;
    };
    for(char c = 'a'; c <= 'e'; ++c)dfs(s + c, len - 1);
}
int main() {
    for(int i = 2; i <= 7; ++i) {
        fin = 0;
        dfs("", i);
    }
    for(int i = 1; i <= 20; ++i)cout << ans[i] << '\n';
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
string ans[10020] = {"a","ba", "baa", "cba", "bbaa", "cbaa", "dcba", "bcbaa", "cbbaa", "dcbaa", "edcba", "bdcbaa", "ccbbaa", "dcbbaa", "edcbaa", "fedcba", "bedcbaa", "cdcbbaa", "dccbbaa", "edcbbaa", "fedcbaa"};
int main() {
    int n;
    cin >> n;
    cout << ans[n];
    return 0;
}

仔细考虑发现

答案字符串一定是非升序的，否则会浪费，即不是最优，那么lead字符一定是最大的，而严格降序必定是该长度的最后一个，位置满足公差为1的等差数列。
所以串长 $len$ ，其覆盖范围为 $(sum(len-2),sum(len-1)]$

根据第一点，即可优化暴力（剪枝）到覆盖到长度13的串，也许能40分

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
int countBubbleSort(string s) {
    int res = 0;
    bool f = 0;
    do {
        f = 0;
        for (int i = 1, sz = s.length(); i < sz; ++i) {
            if (s[i] < s[i - 1]) {
                swap(s[i], s[i - 1]);
                ++res;
                if (!f) f = 1;
            }
        }
    } while (f);
    return res;
}
string ans[125];
bool fin = 0;
inline int getSum(int n) { return (1 + n) * (n) / 2; }
bool isFin(int n) {
    int low = getSum(n - 1);
    int up = getSum(n);
    for (int i = low; i <= up; ++i) {
        if (ans[i] == "") return 0;
    }
    return 1;
}
void dfs(string s, int len) {
    if (fin) return;
    if (len == 0) {
        int cnt = countBubbleSort(s);
        if (ans[cnt] == "") {
            ans[cnt] = s;
            if (isFin(s.size())) fin = 1;
        }
        return;
    };
    if (s == "")
        for (char c = 'a'; c <= 'a' + len; ++c) dfs(s + c, len - 1);
    else
        for (char c = 'a'; c <= s.back(); ++c) dfs(s + c, len - 1);
}
int main() {
    for (int i = 2; i <= 13; ++i) {
        fin = 0;
        dfs("", i);
    }
    // for (int i = 50; i <= 100; ++i) cout << ans[i] << '\n';
    return 0;
}

a
ba   
baa  
cba  
bbaa 
cbaa 
dcba 
cbaaa
cbbaa
dcbaa
edcba
cbbaaa
ccbbaa
dcbbaa
edcbaa
fedcba
ccbbaaa
dcbbaaa
dccbbaa
edcbbaa
fedcbaa

本题暂时搁置一下，记录一下100%的思路：

完全降序的序列能最大限度利用串长，所以它是同一串长下，所能表达的最大逆序数。由此，我们可以确定每一个长度，所覆盖的范围。
而如果26个字母都用完了以后，怎么办呢？我们不妨修改题面，限制只能用ABC三个字母，那么在此情况下暴搜，可以知道，尽可能均匀分布，剩下的指标，从后往前加就可以了：ccbbaaa
现在我们确定了串长，接下来从前往后逐位尝试替换即可，测试当前是否达到该逆序数即可。此处可以通过一个前缀和的操作使复杂度降到 $O(26\log len )$

2020 第十一届蓝桥杯 省赛 第二场 B组 C/C++