2022年第十三届蓝桥杯省赛C++ B组第一场

A. 九进制转十进制

分析

直接手算即可，就不编程了，答案 为 $2\times 9^3 +2 \times9+ 2 =1478$

B. 顺子日期

分析

此题目前有有争议，题意没有交代清楚如 012 算不算顺子。

本人考虑的是 012 计算在内的。前面 2022 肯定无法接后面 34 这个月份构成顺子，则直接枚举每一个月每一天即可，之后判断月份和日期构成的 mmdd 格式是否存在顺子即可。此外，2022显然不是闰年，二月不用+1。

答案：14

代码

#include<bits/stdc++.h>

using namespace std;

int ms[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int s = 0;
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= ms[i]; j++) {
            char t[10];
            sprintf(t, "%02d%02d", i, j);

            if (t[0] + 1 == t[1] && t[1] + 1 == t[2]) {
                s++;
                continue;
            }
            if (t[1] + 1 == t[2] && t[2] + 1 == t[3]) s++;
        }
    }
    cout << s << endl;

    return 0;
}

C. 刷题统计

分析

模拟

直接计算其需要多少完整的周，之后判断剩下的几天内可以完成。

代码

• 已过100%用例

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
LL a, b, n;

int main() {
    cin >> a >> b >> n;
    LL week = a * 5 + b * 2;
    LL m = n / week;
    LL s = m * 7;
    LL res = n % week;
    if (res == 0) {
        cout << s << endl;
        return 0;
    }
    int i = 1;
    for (; i <= 7; i++) {
        LL d = i >= 6 ? b : a;
        res -= d;
        if (res <= 0) break;
    }
    cout << s + i << endl;

    return 0;
}

D. 修剪灌木

分析

模拟，数学

当第 $i$ 棵数被修剪后，若当前方向向右，则向右走 $n - i$ 天，再倒回来，走 $n - i$ 天回到第 $i$ 棵树的位置，则两次修剪第 $i$ 棵树间隔了 $2 \times (n - i)$ 天，同时，期间树木长高到最高了 $2 \times (n - i)$；同理，若再往左边走，两次修剪间隔 $2 \times (i - 1)$ 天，期间树木长高到最高 $2 \times (i - 1)$ 。比较两个方向的最高高度即为第 $i$ 棵树的最大高度。

代码

• 已过100%用例

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        printf("%d\n", max(n - i, i - 1) * 2);
    }

    return 0;
}

E. X 进制减法

分析

模拟

每个进制位由低一位的位决定，每个进制尽量取较小的(>=2)。

代码

• 已过100%用例

#include<bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
typedef long long LL;
vector<int> a, b;
int n, ma, mb;

int main() {
    cin >> n >> ma;
    for (int i = 0, x; i < ma; i++) {
        scanf("%d", &x);
        a.push_back(x);
    }
    cin >> mb;
    for (int i = 0, x; i < mb; i++) {
        scanf("%d", &x);
        b.push_back(x);
    }

    //从低位到高位
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    LL pre = 0; //前面几位的值
    for (int i = ma - 1; i >= 0; i--) {
        LL t = pre + a[i];
        if (mb > i) t -= b[i];
        t = (t + MOD) % MOD;
        if (i == 0) {
            pre = t;
            break;
        }

        //i > 0，当前位置需乘上后一位的进制，为后一位两个数中最大值 + 1
        int mx = a[i - 1];
        if (mb > i - 1) mx = max(mx, b[i - 1]);
        pre = t * max(2, mx + 1) % MOD;
    }
    cout << pre << endl;

    return 0;
}

F. 统计子矩阵

分析

前缀和，双指针

统计矩阵前缀和，用 $s[i][j]$ 表示 以 $[1, 1]$ 为左上角，$[i, j]$ 为右下角的矩阵内的节点和。

之后枚举子矩阵的上下限 $r_1,r_2$，再利用双指针从左往右扫一趟累加满足条件的子矩阵左右两边即可。

代码

• 已过100%用例

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 510;
int m, n, k;
int s[N][N], ts[N];
//s[j][i] 表示第 j 列的 1-i 行前缀和

//C语言网要用快读，不然会被卡
template<typename T>
void read(T &x) {
    x = 0;
    T f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + (c ^ 48);
        c = getchar();
    }
    x = f * x;
}

int main() {
//    cin >> m >> n >> k;
    read(m), read(n), read(k);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
//            scanf("%d", &s[j][i]);
            read(s[j][i]);
            s[j][i] += s[j][i - 1];
        }
    }

    LL ans = 0;
    for (int r1 = 1; r1 <= m; r1++) { //上边距
        for (int r2 = r1; r2 <= m; r2++) {    //下边距
            for (int j = 1; j <= n; j++) {  //计算限定上下界的第 j 列的元素和
                ts[j] = s[j][r2] - s[j][r1 - 1];
            }
            int ss = 0; //表示[L, R-1]的前缀和，若 L == R则为0
            //枚举并累加以 R 为右端点且满足条件的区间
            for (int L = 1, R = 1; R <= n;) {    //L,R双指针从左往右扫描
                int t = ts[R];          //限定上下边的情况，当前第R列的和
                if (ss + t <= k) {        //限定上下边的情况，若当前 [l, R-1] 区间内的和加上第 R 列满足条件
                    ans += (R - L + 1);   //则以 L 到 R 为左端点，R 为右端点的子区间都满足条件，更新答案
                    ss += t;
                    R++;
                } else {      //不满足条件，左指针右移，缩小区间，即减小区间和
                    ss -= ts[L];
                    if (++L == R + 1) {   //若超过右指针，则说明 R 这一列的和都大于 k，右指针向右移动更新
                        ss = 0;
                        R++;   //更新后 L == R
                    }
                }
            }
        }
    }
    printf("%lld\n", ans);

    return 0;
}

G. 积木画

分析

动态规划

见下图。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define gcd __gcd
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define lowbit(x) (x & -x)

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e7 + 5, MOD = 1e9 + 7;
int n, f[N][4];

int main(){
    cin >> n;
    f[0][3] = 1;
    fir(i, 1, n) {
        f[i][0] = f[i - 1][3];

        f[i][1] = f[i - 1][2];
        if(i >= 2) {
            f[i][1] = (f[i][1] + f[i - 2][3]) % MOD;
        }

        f[i][2] = f[i - 1][1];
        if(i >= 2) {
            f[i][2] = (f[i][2] + f[i - 2][3]) % MOD;
        }

        f[i][3] = (f[i - 1][1] + f[i - 1][2]) % MOD;
        f[i][3] = (f[i][3] + f[i - 1][3]) % MOD;
        if(i >= 2) {
            f[i][3] = (f[i][3] + f[i - 2][3]) % MOD;
        }
    }
    cout << f[n][3] << endl;

    return 0;
}

H. 扫雷

分析

bfs, dfs

见代码！

代码

• 已过100% 用例

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 5e4 + 5, MAXN = 1e9;
bool v[N];
struct P {
    int x, y, r, cnt;
} p[N];
unordered_map<LL, int> mp;
int n, m, s, tot;

//hash坐标，x 和 y 在 [0, 1e9] 共有 1e9 + 1 种取值
inline LL get(LL x, LL y) {
    return x * (MAXN + 1) + y;
}

void bfs(int k) {
    queue<int> qu; //队列存放有雷的坐标点的下标
    qu.push(k);
    while (qu.size()) {
        int u = qu.front();
        qu.pop();

        LL dr = 1LL * p[u].r * p[u].r;
        //在当前坐标点爆炸后的爆炸范围内搜索是否存在未引爆的点
        //遍历横坐标，注意题目保证 x 和 y 在 [0,1e9] 范围内
        for (int x = max(0, p[u].x - p[u].r); x <= p[u].x + p[u].r && x <= MAXN; x++) {
            LL dx = 1LL * (x - p[u].x) * (x - p[u].x);

            //向上遍历纵坐标
            for (int y = p[u].y; 1LL * (y - p[u].y) * (y - p[u].y) + dx <= dr && y <= MAXN; y++) {
                LL id = get(x, y);
                if (mp.find(id) == mp.end()) continue; //该坐标不存在雷，跳过
                int index = mp[id];
                if (v[index]) continue; //该坐标已经访问过，跳过

                qu.push(index);     //该坐标背引爆，加入对列，后续查找其能引爆的雷
                s += p[index].cnt;  //答案更新
                v[index] = true;    //标记该坐标点为已经引爆
            }
            //向下遍历纵坐标
            for (int y = p[u].y - 1; 1LL * (y - p[u].y) * (y - p[u].y) + dx <= dr && y >= 0; y--) {
                LL id = get(x, y);
                if (mp.find(id) == mp.end()) continue;
                int index = mp[id];
                if (v[index]) continue;

                qu.push(index);
                s += p[index].cnt;
                v[index] = true;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1, x, y, r; i <= n; i++) {
        scanf("%d%d%d", &x, &y, &r);
        //将其坐标和下标放到map，方便后面枚举坐标时，能快速找到是否存在对应的雷
        LL id = get(x, y);
        if (mp.find(id) != mp.end()) { //该坐标存在雷，则更新
            int index = mp[id];     //坐标对应的下标
            if (p[index].r < r) p[index].r = r;     //取该点的最大半径，能引爆更多的雷
            p[index].cnt++;     //当前坐标点的雷的数量增加
        } else {
            mp[id] = ++tot;
            p[tot] = {x, y, r, 1};
        }
    }

    for (int i = 1, x, y, r; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &r);
        p[tot + 1] = {x, y, r, 0};  //放在最末尾
        bfs(tot + 1);   //计算从当前点引爆能引爆的雷的数量
    }
    cout << s << endl;

    return 0;
}

I. 李白打酒加强版

分析

动态规划

代码中写的很清楚！

代码

• 暴力骗分，40%样例

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 110, MOD = 1e9 + 7;
int n, m;

int main() {
    cin >> n >> m;
    LL s = 0;
    for (int i = 0; i < 1 << (m + n); i++) {    //枚举每种方案，1为酒馆,0为花 
        if (i & 1) continue; //若最后一个不为花 ，则不为合法方案，跳过 
        int cn = 0;    //统计该序列中遇到酒馆的次数 
        for (int j = 0; j < m + n; j++) {
            if (i >> j & 1) cn++;
        }
        if (cn != n) continue; //如果酒馆次数不等于目标次数，跳过

        LL t = 2;    //当前酒的斗数 
        bool f = true;
        for (int j = m + n - 1; j >= 0; j--) {
            if (i >> j & 1) t *= 2;
            else {
                if (--t == -1) {    //若为0且遇到花店，为不合法方案 
                    f = false;
                    break;
                }
            }
        }
        if (f && t == 0) s++;
    }
    cout << s << endl;

    return 0;
} 

• DP，100%样例

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 110, MOD = 1e9 + 7;
int n, m, f[N][N][N];
LL s;

int main() {
    cin >> n >> m;
    f[0][0][2] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 && j == 0) continue;
            if (i == n && j == m) {  //最后特判，结尾遇到花，只能从f[n][m - 1][1]转移过来
                f[i][j][0] = f[i][j - 1][1];
                break;
            }
            for (int k = 0; k <= m; k++) {  //酒最多 m 斗，否则就算接下来全部 m 次花，都不能到达0的状态。
                //1.遇到花店得到的
                if (j && k < m) f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % MOD;
                //2.遇到酒馆得到的，注意这里酒是加倍，则一定是偶数状态才转移过来了
                if (i && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % MOD;
            }
        }
    }
    cout << f[n][m][0] << endl;

    return 0;
}

J. 砍竹子

分析

模拟

先给出两个输入样例，第一个样例是官方的，第二个是自己乱造的。

样例1

6
2 1 4 2 6 7

样例2

10
20 22 30 40 42 50 60 70 80 2222

对于上图的两个输入样例分别如下：

首先，对于每个高度（$1\le h_i \le 10^{18}$），其最多可以被砍掉六次变为 1。

我们将每颗竹子执行砍操作直到变为1，得到结果如上图所示。可以看到，在对应的每列连续相同的高度的竹子（用同一个框框起来）可以一起被砍掉，最后的结果即为画的框的数量。

代码

#include<bits/stdc++.h>

using namespace std;

#define sync ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define frein freopen("in.txt", "r", stdin)
#define gcd __gcd
#define pb push_back
#define fi first
#define se second
#define fir(i, a, b) for(int i = a; i <= b; i++)
#define rif(i, b, a) for(int i = b; i >= a; i--)
#define lowbit(x) (x & -x)
#define pl (p << 1)
#define pr (p << 1 | 1)
#define hmid(l, r) ((l + r) >> 1)

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 5;
int n;
vector<LL> g[N];

inline LL cutdown(LL x) {
    return (LL) sqrt((x >> 1) + 1);
}

int main() {
    // frein;
    cin >> n;
    LL x;
    fir(i, 1, n) {
        scanf("%lld", &x);
        g[i].pb(x);
        while (x > 1) {
            x = cutdown(x);
            g[i].pb(x);
        }
        reverse(g[i].begin(), g[i].end());
    }

    int tot = 0;
    fir(j, 1, 6) {
        LL pre = 0;
        fir(i, 1, n) {
            if (j < int(g[i].size())) {
                if (pre == 0) {
                    tot++;
                    pre = g[i][j];
                } else if (pre != g[i][j]) {
                    tot++;
                    pre = g[i][j];
                }
            } else if (pre) pre = 0;
        }
    }
    cout << tot << endl;

    return 0;
}