题解 | 湖南工业大学蓝桥杯省赛选拔赛

update 2025/3/3 G题已更新

题解链接：https://blog.nowcoder.net/n/47b9455b10a44284b7d9c7b9a42e13f3

比赛链接：https://ac.nowcoder.com/acm/contest/102926

密码：lqbhut31

A 603

概要

链接：https://ac.nowcoder.com/acm/contest/102926/A

估测难度：1600

算法：线性动态规划

时间复杂度:

题意

给一个纯数字字符串，其中不包含"603"子串的子序列有多少个？

思路

第一时间可能会联想到组合数学，通过组合数去处理。

然后就会发现越想越复杂，需要同时维护若干种拼接。虽然这种方法也能在O(n)下解决问题，但是思考难度和代码实现过于复杂。

所以我们使用动态规划解决问题。

对于拼接一个已知的字符串(如："603","石碑文")等，dp是一个经典的方法。

设计状态：dp[1]存以6结尾的串的数量，dp[1]存以60结尾的串的数量，dp[0]存除前两者以外，并不以"603"结尾的所有串的数量

状态转移见代码注释

代码

using namespace std;

using i64 = long long;
constexpr int M=998244353;

void solve() {
    int n; cin>>n;
    string s; cin>>s;
    
    vector<i64> dp(3); dp[0] = 1;//初始时有一个空串
    for(int i=0; i<n; ++i) {
        //拷贝一个 dp 数组名为 f
        auto f = dp;
        //将s[i]加入到当前串尾部, 枚举f[0], f[1], f[2]三个状态依次转移
        if(s[i] == '6') {
            dp[1] += f[0];
            dp[1] += f[1];
            dp[1] += f[2];
        } else if(s[i] == '0') {
            dp[0] += f[0];
            dp[2] += f[1];
            dp[0] += f[2];
        } else if(s[i] == '3') {
            dp[0] += f[0];
            dp[0] += f[1];
            //dp[0] += f[2];此状态无法转移，否则会构成“603”
        } else {
            dp[0] += f[0];
            dp[0] += f[1];
            dp[0] += f[2];
        }
        dp[0] %= M;
        dp[1] %= M;
        dp[2] %= M;
    }
    //最后需要将全不选的情况(即空串)除去, -1
    cout<<((dp[0]+dp[1])%M+dp[2]-1+M)%M<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

B 打打打打结

概要

链接：https://ac.nowcoder.com/acm/contest/102926/B

估测难度：1200

算法：二分答案

时间复杂度: 2

题意

给 n 条线段，在每条线段上选一个点，最大化相邻点之间的最短距离。

思路

看到最大最小一眼二分就完了, 直接干。

排序之后直接选最左边线段的左端点作为第一个。

然后now依次+mid，前提是 a[i].l <= now+mid <= a[i].r;

如果a[i].l > now + mid, now = a[i].l;

如果a[i].r < now + mid, 直接return false

代码

using namespace std;

using i64 = long long;

void solve() {
    int n; cin>>n;
    
    vector<pair<int,int>> a(n+1);
    for(int i=1; i<=n; ++i) {
        int x, len; cin>>x>>len;
        a[i] = {x, x+len};
    }
    sort(a.begin()+1, a.end());
    
    auto check = [&](int x) {
        int now = a[1].first;
        for(int i=2; i<=n; ++i) {
            if(a[i].first <= now+x and now+x <= a[i].second) {
                now += x;
            } else if(a[i].first > now+x) {
                now = a[i].first;
            } else {
                return false;
            }
        } return true;
    };
    
    i64 l = 0, r = 1e9;
    while(r-l > 1) {
        int mid = l+r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout<<l<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

C 邮票

概要

链接：https://ac.nowcoder.com/acm/contest/102926/C

估测难度：1400

算法：概率论(数学)

时间复杂度:

题意

有 n-1 种普通邮票(同种凑齐两张获胜)和 1 张特殊邮票(拿到立刻获胜)， 每次等概率抽取邮票，期望抽取次数是多少。

思路

状态转移：当手里已经有一张该种普通邮票时，该种普通邮票也可以视为特殊邮票。

随着拿的次数越来越多，若此时还未获胜，特殊邮票会越来越多，每拿一次之后都增加一种特殊邮票， 所以第 次拿的胜率是 。

因此，我们只需要枚举拿的次数 ，拿第 次的概率就是失败率的前缀积 p(初始为1.0, 显然没拿的时候100%失败), ans = ∑ i * p;

代码

using namespace std;

using i64 = long long;

void solve() {
    double n; cin>>n;
    
    double ans = 0, p = 1;//p为拿第i次的概率
    for(int i=1; i<=n; ++i) {
        ans += 1.0 * p;
        p = p * (n-i) / n;//失败率的前缀积
    }
    cout<<fixed<<setprecision(2)<<ans<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

D 遗迹探险

概要

链接：https://ac.nowcoder.com/acm/contest/102926/D

估测难度：1300

算法：线性动态规划

时间复杂度:

题意

从左上角走到右下角，只能向右或向下走，找到一条路径——其中每个节点的前缀和都是非负数，输出这样的路径中终点权值最大的。如果没有，输出-1

思路

对于每个位置只能从上放或者左方转移过来，直接两层循环枚举

状态转移 f[i][j] = max(f[i][j-1], f[i-1][j]) + a[i][j];

当f[i][j] < 0 时，标记为-无穷，禁止通过。

代码

using namespace std;

using i64 = long long;
constexpr i64 INF=1e18;

void solve() {
    int n, m; cin>>n>>m;
    
    vector a(n+1, vector<i64>(m+1));
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            cin>>a[i][j];
        }
    }
    
    vector f(n+1, vector<i64>(m+1, -INF)); f[1][1] = a[1][1];//初始化
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            if(i > 1) f[i][j] = max(f[i][j], f[i-1][j] + a[i][j]);
            if(j > 1) f[i][j] = max(f[i][j], f[i][j-1] + a[i][j]);
            if(f[i][j] < 0) f[i][j] = -INF;//无法经过，标记为-无穷
        }
    }
    cout<<(f[n][m]>0?f[n][m]:-1)<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

E maximum matrix

概要

链接：https://ac.nowcoder.com/acm/contest/102926/E

估测难度：1400

算法：二分答案，前缀和

时间复杂度: 2

题意

给一个仅有0/1组成的矩阵，在里面找到最大的 全0方阵 和 全1方阵，分别输出面积

思路

对原矩阵做二维前缀和。

二分最大方阵的边 L，暴力枚举所有位置，如果该方阵前缀和 == L * L * t，有合法解return true。

代码

using namespace std;

using i64 = long long;

void solve() {
    int n, m; cin>>n>>m;
    
    vector s(n+1, vector<i64>(m+1));
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            cin>>s[i][j];
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];
        }
    }
    
    auto check = [&](int x, int t) {
        for(int i=x; i<=n; ++i) {
            for(int j=x; j<=m; ++j) {
                if(s[i][j] - s[i-x][j] - s[i][j-x] + s[i-x][j-x] == x*x*t) {
                    return true;
                }
            }
        } return false;
    };
    auto Find = [&](int t) {
        int l = 0, r = min(n, m)+1;
        while(r-l > 1) {
            int mid = l+r >> 1;
            if(check(mid, t)) l = mid;
            else r = mid;
        }
        return 1ll*l*l;
    };
    
    cout<<Find(0)<<" ";
    cout<<Find(1)<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

F 盐都不盐了

概要

链接：https://ac.nowcoder.com/acm/contest/102926/F

估测难度：900

知识点：组合数学数学 快速幂数学

https://oi-wiki.org/math/binary-exponentiation/

时间复杂度:

题意

给一堆没用的字符串拼接在一起，里面分别有多少个子序列是 "6", "66", "666"

思路

统计6的个数 cnt，输出C(1, cnt), C(2, cnt), C(3, cnt)

注意当数字取模后，不能使用除法，所以需要乘上逆元。

如 15 % 7 / 3 != 15 / 3 % 7

代码

using namespace std;

using i64 = long long;
constexpr int M=998244353;

i64 qpow(i64 a, i64 b) {
    i64 ans = 1;
    while(b) {
        if(b & 1) ans = ans*a%M;
        a = a*a%M, b>>=1;
    } return ans;
}

void solve() {
    int n; cin>>n;
    
    i64 cnt = 0;
    for(int i=1; i<=n; ++i) {
        i64 k; cin>>k;
        string s; cin>>s;
        i64 res = 0;
        for(auto c: s) {
            res += (c == '6');
        }
        cnt += 1ll * res * k;
    }
    
    i64 a = cnt%M;
    i64 b = cnt * (cnt-1)%M * qpow(2, M-2)%M;
    i64 c = cnt * (cnt-1)%M * (cnt-2)%M * qpow(6, M-2)%M;
    
    cout<<a<<" "<<b<<" "<<c<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

G 气象工程

概要

链接：https://ac.nowcoder.com/acm/contest/102926/G

估测难度：2400

算法：主席树

时间复杂度: 2

题意

给出 块木板(区间)和它的耐久，接下来发射 m 颗子弹，被击中的木板每次扣 1 点耐久，扣至0点会破碎，输出每次发射子弹后破碎的木板数

思路

不是哥们，盐豆不盐了，真以为我会啊T_T

诶嘿，我还真会。

前置芝士：主席树，可以在 2的时空复杂度保存单点修改的 所有历史数组

可以在2查询任意两个历史间数组内的第k小元素。(很高级.jpg)

首先考虑到求解第 i 块木板在什么时候破碎。

容易想到一个22的做法：

主席树保存所有历史数组，枚举 块木板，二分破碎的时间，从复杂度上来看是一个很极限的做法，实际上因为主席树常数过大，并且题目只给了 ，很无情的被卡常了。

考虑怎么优化，前面的算法只用到了主席树的存储功能，并没有非常好的使用到主席树的查询，从查询算法入手。

对于第 块木板，所有击中他的子弹中的时间是绝对有序的，我们可以在所以击中木板的子弹中查询第 小时间，就是第一颗击碎木板的子弹。

对于主席树的插入，我们从以发射位置为修改点，逐一保存每个发射位置发射之后的数组，利用主席树在任意两个历史数组间的查询功能，完成对区间 的 第 小查询。不再使用二分算法逼近，时间复杂度优化到2

代码

using namespace std;

using i64 = long long;

struct PST {
    struct SMN {
        int l, r;
        int sum;
    };
    int n, cnt; vector<SMN> tr; 
    
    PST() {}
    PST(int n) {init(n);}
    void init(int n) {
        this->n = n;
        tr.assign(n<<5|1, {});
        cnt = 0;
    }
    
    inline int build(int l, int r) {
        //初始化
        int u = ++cnt;
        tr[u].sum = 0;
        if(l==r) return u;
        int mid = l+r >> 1;
        tr[u].l = build(l, mid);
        tr[u].r = build(mid+1, r);
        return u;
    }
    inline int insert(int l, int r, int old, int pos) {
        int u = ++cnt;
        tr[u] = tr[old]; tr[u].sum++;
        if(l==r) return u;
        
        int mid = l+r >> 1;
        if(pos<=mid) tr[u].l = insert(l, mid, tr[u].l, pos);
        else tr[u].r = insert(mid+1, r, tr[u].r, pos);
        return u;
    }
    inline int query(int l, int r, int u, int v, int k) {
        if(l==r) return l;
        
        int mid = l+r >> 1;
        int x = tr[tr[v].l].sum - tr[tr[u].l].sum;
        if(k<=x) return query(l, mid, tr[u].l, tr[v].l, k);
        return query(mid+1, r, tr[u].r, tr[v].r, k-x);
    }
};

void solve() {
    int n, m; cin>>n>>m;
    
    vector<array<int,3>> a(n+1);
    for(int i=1; i<=n; ++i) {
        int l, r, k; cin>>l>>r>>k;
        a[i] = {l, r, k};
    }
    
    vector<array<int,2>> q(m+1); 
    for(int i=1; i<=m; ++i) {
        int x; cin>>x;
        q[i] = {x, i};
    }
    sort(q.begin()+1, q.end());
    
    PST X(200000); 
    vector<int> t(200001); t[0] = X.build(1, 200000);
    for(int i=1,j=1; i<=200000; ++i) {
        t[i] = t[i-1];
        while(q[j][0] == i and j<=m) {
            t[i] = X.insert(1, m, t[i], q[j][1]);
            ++j;
        }
    }
    
    vector<int> ans(m+1);
    for(int i=1; i<=n; ++i) {
        auto [l, r, k] = a[i];
        if(k > X.tr[t[r]].sum - X.tr[t[l-1]].sum) continue;
        ans[X.query(1, m, t[l-1], t[r], k)]++;
    }
    for(int i=1; i<=m; ++i) {
        cout<<ans[i]<<"\n";
    }
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}

H 查找单词

概要

链接：https://ac.nowcoder.com/acm/contest/102926/H

估测难度：800

知识点: getline

时间复杂度: O(n)

题意

给出一行文本和模式串，文本里能找到多少个模式串。

思路

暴力枚举文本每一个位置，匹配模式串

注意需要读取空格所以使用读行函数

代码

using namespace std;

using i64 = long long;

void solve() {
    string s; getline(cin, s);
    string t; getline(cin, t);
    
    int cnt = 0;
    for(int i=0; i<s.size(); ++i) {
        if(s[i] == t[0]) {
            int k = i, j = 0, f = 1;
            for( ;j<t.size() and k<s.size(); ++j,++k) {
                if(s[k] != t[j]) f = 0;
            }
            if(j != t.size()) f = 0;
            cnt += f;
        }
    }
    cout<<cnt<<"\n";
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int t=1;// cin>>t;
    while (t--) solve();
    return 0;
}