昨天 09:22 已编辑牛客小学算法工程师发布于湖南

关注

题解 | # 2026蓝桥杯B组省赛 #

题目一：https://www.luogu.com.cn/problem/P16232

满足 $0\leq x < y$ ，且 $x+y=2026202520242023$ ，输出有多少个 $(x,y)$ ，那么就是 $(0,2026202520242023),(1,2026202520242022),.....$

所以答案是 $\lfloor \frac{2026202520242023}{2} \rfloor+1$

题目二：https://www.luogu.com.cn/problem/P16233

如果有一盏灯，总次数为 $1$

如果有两盏灯，总次数为 $4$

如果有三盏灯，总次数为 $12$

如果有四盏灯，总次数为 $32$

手动模拟可以枚举到四盏灯，很显然一个结论是总次数等于 $n \times 2^{n - 1}$

打表代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    
    int n; cin >> n;
    vector<int> s(n);
    map<vector<int>, int> ma;
    ma[s] = 0;
    queue<vector<int> > q;
    q.push(s);
    while(q.size()){
        auto u = q.front();
        q.pop();
        for(int i = 0; i < (int)u.size(); i ++){
            auto v = u;
            if(ma[u] & 1){
                for(int j = 0; j <= i; j ++) v[j] ^= 1;
            }
            else{
                for(int j = i; j < n; j ++) v[j] ^= 1;
            }
            if(!ma.count(v)){
                ma[v] = ma[u] + 1;
                q.push(v);
            }
        }
    }
    int ans = 0;
    for(auto [v, w] : ma){
        for(int e : v) cout << e << " ";
        cout << endl;
        cout << "步数 = " << w << endl;
        ans += w;
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目三：https://www.luogu.com.cn/problem/P16234

右移一次后与原数组相同，所以就是 $a_{1}=a_{2}=a_{3}=...=a_{n}$ ，直接输出 $Y-X+1$

题目四：https://www.luogu.com.cn/problem/P16235

需要满足两个条件就输出 $T$

总人数是 $5$ 的倍数
单个位置的人数不超过总战队数

题目五：https://www.luogu.com.cn/problem/P16236

对于 $?$ 的处理，一定是前面全部都是将 $?$ 设置为 $L$ ，后面全部将 $?$ 设置为 $Q$ ，所以需要 $O(n)$ 枚举分界点位置

一开始将全部的 $?$ 设置为 $L$ ，对于每个 $?$ 的位置用 $vis[]$ 标记

然后从后向前枚举每一个位置，当然也可以从前向后枚举

考虑将一个 $?$ 从 $L$ 换成 $Q$ 的过程发生了什么，先记该位置为 $pos$

减少了该位置原来的 $L$ 与 $[pos+1,n]$ 这个区间里面的 $Q$ 形成的 $LQ$
新增了 $[1,pos-1]$ 中的 $L$ 与该位置现在的 $Q$ 形成的 $LQ$

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){

    int n; cin >> n;
    vector<char> a(n + 10);
    vector<int> vis(n + 10), pre(n + 10);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] == '?'){
            vis[i] = true;
            a[i] = 'L';
        }
    }
    for(int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + (a[i] == 'L');
    int ans = 0, now = 0, cnt = 0;
    for(int i = n; i >= 1; i --){
        if(a[i] == 'Q') cnt ++;
        else ans += cnt; 
    }
    now = ans, cnt = 0;
    for(int i = n; i >= 1; i --){
        if(vis[i]){
            now -= cnt;
            now += pre[i - 1];
            ans = max(ans, now);
            a[i] = 'Q';
        }
        if(a[i] == 'Q') cnt ++;
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目六：https://www.luogu.com.cn/problem/P16237

求的第一个整数表示最少需要添加的应急跳线数量：其实连通块的数量减 $1$

求的第二个整数表示在确保跳线总数最少的前提下，单台计算机接入跳线数量最大值的最小可能值：注意看题，“接入这种应急跳线数量最多的那一台机器，其接入的跳线数降到最低”。

需要考虑的是连通块的大小（这个连通块里面的点的数量）：

如果数量大于等于 $2$ ，那么我可以选取两个不同的点接入应急跳线，此时这个连通块的最大值为 $1$
如果数量等于 $1$ ，再如果这一个点可以只连接一条边，那么最大值为 $1$ ，否则最多只会连接两条边

设连通块大小为 $1$ 的数量为 $cnt_{1}$ ，大小大于等于 $2$ 的数量为 $cnt_{2}$

那么首先将大小大于等于 $2$ 的连通块连接起来： $2$ 个连通块连接消耗了 $2$ 个点， $3$ 个连通块连接消耗了 $4$ 个点， $n$ 个连通块连接消耗了 $2\times (n-1)$ 个

那么其他的点都是一条边也没有连接的（设数量为 $cnt_{3}$ ），所以就可以给大小为 $1$ 的连通块连接。

所以如果 $cnt_{3} \geq cnt_{1}$ ，答案就是 $1$ ，否则为 $2$ （一开始先判断答案是否为 $0$ ，即是不是一开始就是一个连通块）

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 100000 + 100;

int n, m, p[N], cnt[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void solve(){

    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        p[i] = i;
        cnt[i] = 1;
    }
    for(int i = 1; i <= m; i ++){
        int u, v; cin >> u >> v;
        int fu = find(u), fv = find(v);
        if(fu != fv){
            cnt[fv] += cnt[fu];
            p[fu] = fv;
        }
    }
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for(int i = 1; i <= n; i ++){
        if(i == p[i]){
            if(cnt[i] == 1) cnt1 ++;
            else{
                cnt2 ++;
                cnt3 += cnt[i];
            }
        }
    }
    cout << (cnt1 + cnt2 - 1) << " ";
    if(cnt1 + cnt2 == 1) cout << 0 << endl;
    else{
        cnt3 -= 2 * (cnt2 - 1);
        if(cnt3 >= cnt1) cout << 1 << endl;
        else cout << 2 << endl;
    }
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目七：https://www.luogu.com.cn/problem/P16238

显然只与 $a$ 数组和 $b$ 数组的差有关系，设 $c[i]=b[i]-a[i]$

那么在一个区间上修改全部加上 $k$ ，如果 $c[i]=k$ ，那么就表明 $a[i]+k=b[i]$ 满足题意，但是还得考虑一个东西就是如果这个区间里面一开始存在 $c[i]=0$ ，那么加上 $k$ 后， $c[i] \ne 0$ ，对答案的贡献就会减少

首先统计所有 $c[i]=0$ 的个数设为 $cnt$ ，那么答案最少就为 $cnt$

然后考虑区间修改带来的影响：区间里面的 $c[i]=k$ 数量减去区间里面 $c[i]$ 等于 $0$ 的数量就是一个区间影响

查询区间 $c[i]=0$ 的个数可以用前缀和
一个很重要的贪心是区间上修改时，一定满足 $c[l]=c[r]$ ，这样可以满足 $c[i]=k$ 数量最大的同时减少 $c[i]$ 等于 $0$ 的数量

所以可以想到将每个数出现的位置存下来，用 $map<int, vector<int> > ma$ 存储

那么在 $vector$ 里面，对于 $i,j$ 来讲：

$c[i]=k$ 的个数为 $j-i+1$ 个，它们对应的位置为 $v[i],v[j]$ ，那么 $c[i]=0$ 的个数为 $pre[v[j]]-pre[v[i]]$ ，所以区间的贡献为 $(j-i+1)-(pre[v[j]] - pre[v[i]])$ ，分离变量为 $(j-pre[v[j]]+1)-(i-pre[v[i]])$

那么我们就可以直接依次遍历 $vector$ 里面的每一个数，然后当前的就是 $j$ ，同时维护 $(i-pre[v[i]])$ 的最小值

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

void solve(){
    int n; cin >> n;
    vector<int> a(n + 10), b(n + 10), c(n + 10), pre(n + 10);
    int cnt = 0;
    map<int, vector<int> > ma;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++){
        cin >> b[i];
        c[i] = b[i] - a[i];
        pre[i] = pre[i - 1] + (c[i] == 0);
        if(c[i] == 0) cnt ++;
        else ma[c[i]].push_back(i);
    }    
    int ans = cnt, now = 0;
    for(auto [x, v] : ma){
        now = 1;
        if((int)v.size() > 1){
            int MIN = 0 - pre[v[0]];
            for(int i = 1; i < (int)v.size(); i ++){
                now = max(now, (i - pre[v[i]]) - MIN + 1);
                MIN = min(MIN, i - pre[v[i]]);
            }
        }
        ans = max(ans, cnt + now);
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目八：https://www.luogu.com.cn/problem/P16239

给了 $n$ 个球员的初始能力 $a_{i}$ ，以及每训练一天增加的能力 $b_{i}$ ，那么如果给第 $i$ 个球员 $k_{i}$ 天的训练时间，则他的能力变为 $(a_{i} + k_{i} \times b_{i})$ 。一共有 $m$ 天的训练时间，要求所有的球员训练时间之和为 $m$ ，即 $\sum_{i=1}^{n}{k_{i}}=m$ ，求 $\prod_{i=1}^{n}{(a_{i}+k_{i} \times b_{i})}$ 的最大值

$\prod_{i=1}^{n}{(a_{i}+k_{i} \times b_{i})} = \prod_{i=1}^{n}{(b_{i} \times (\frac{a_{i}}{b_{i}} + k_{i}))} = \prod_{i=1}^{n}{b_{i}} \times \prod_{i=1}^{n}{ (\frac{a_{i}}{b_{i}} + k_{i})}$ ，其中 $\prod_{i=1}^{n}{b_{i}}$ 为常数，所以只与 $(\frac{a_{i}}{b_{i}} + k_{i})$ 有关

对于 $k_{i}$ 的取值，贪心的是优先选择 $\frac{a_{i}}{b_{i}}$ 小的，因为：例如 $a \times b \times c \times d$ （ $a \leq b \leq c \leq d$ ），如果给最小的 $a$ 加上 $1$ ，那么总值就会加上 $b \times c \times d$ ，而 $b, c, d$ 是最大的那三个数，所以优先选择最小的那个数可以使得总乘积最大

设 $MIN= min(\frac{a_{1}}{b_{1}},\frac{a_{2}}{b_{2}},...,\frac{a_{n}}{b_{n}}),$ 那么 $MIN$ 是满足单调性的，即 $MIN$ 只会增加不会减少，对于 $m$ 次增加值，可以用浮点数二分找到 $MIN$ 的值：

首先对于 $\frac{a_{i}}{b_{i}}$ 增加到 $MIN$ 假设要 $k$ 次，那么 $\frac{a_{i}}{b_{i}}+k \geq MIN$ ，所以 $k = \lceil (MIN - \frac{a_{i}}{b_{i}} \rceil$ ，用 $ceil()$ 函数，然后对 $0$ 取最大值

int cnt = 100;
double l = 0, r = 2e14, pos = 0;
while(cnt --){
    double mid = (l + r) / 2.0;
    if(check(mid)){
        pos = mid;
        l = mid;
    }
    else r = mid;
}

因为浮点数二分直接循环 $100$ 次就可以了

如果总次数比 $m$ 说明 $MIN$ 取大了，寻找更小值

否则说明 $MIN$ 还可以取更大值，寻找更大值

bool check(double x){
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        double v = (double)a[i] / (double)b[i];
        int cur = (int)ceil(x - v);
        cur = max(0LL, cur);
        cnt += cur;
        if(cnt > m) return false;
    }
    return true;
}

那么现在得到 $MIN$ 后，然后对每一个 $a_{i}$ 进行操作

 priority_queue<Node , vector<Node>, cmp> q;
for(int i = 1; i <= n; i ++){
    double v = (double)a[i] / (double)b[i];
    int cur = (int)ceil(pos - v);
    cur = max(0LL, cur);
    a[i] += cur * b[i];
    m -= cur;
    q.push({a[i], b[i], i});
}

$m$ 为了让 $a_{i} \geq MIN$ 已经用了很多了，可以保证 $m<n$ ，因为如果 $m \geq n$ ，则可以直接让所有的 $a_{i}$ 都在加上一个值，这样 $MIN$ 就不是最大的了
用优先队列模拟剩下最小的 $a_{i}$ 加 $b_{i}$ 的情况；同时需要记录下标，因为最终答案需要用到

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 100000 + 100;
const int mod = 998244353;

int n, m;
int a[N], b[N];

bool check(double x){
    int cnt = 0;
    for(int i = 1; i <= n; i ++){
        double v = (double)a[i] / (double)b[i];
        int now_cnt = ceil(x - v);
        now_cnt = max(0LL, now_cnt);
        cnt += now_cnt;
        if(cnt > m) return false;
    }
    return true;
}

struct Node{
    double x, y, id;
};

struct cmp{
    bool operator() (const Node &a, const Node &b) const{
        return a.x * b.y > a.y * b.x;
    }
};

void solve(){
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];

    int cnt = 100;
    double l = 0, r = 2e14, pos = 0;
    while(cnt --){
        double mid = (l + r) / 2;
        if(check(mid)){
            pos = mid;
            l = mid;
        }
        else r = mid;
    }

    priority_queue<Node, vector<Node>, cmp> q;
    for(int i = 1; i <= n; i ++){
        double v = (double)a[i] / (double)b[i];
        int now_cnt = ceil(pos - v);
        now_cnt = max(0LL, now_cnt);
        a[i] += now_cnt * b[i];
        m -= now_cnt;
        q.push({a[i], b[i], i});
    }
    while(m --){
        int x = q.top().x;
        int y = q.top().y;
        int id = q.top().id;
        a[id] += y;
        q.pop();
        q.push({a[id], y, id});
    }

    int ans = 1;
    for(int i = 1; i <= n; i ++){
        a[i] %= mod;
        ans = (ans * a[i]) % mod;
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}