蓝桥杯选拔赛题解

锐评: 总体感觉这场比赛偏难，对于未入门的选手来说还是比较吃力的，但是本质上还是考察积累(据出题人说全是原题)。 对标蓝桥杯来说的话，首先ioi赛制肯定是比oi赛制简单，整体难度大差不差，可能略难一点。

A 魔法冒险的战斗加成

小登如果按照顺序做题的话就直接死了，这道题的考点还是线性dp，对于没接触过动态规划的同学，做起来还是非常难的。 当然蓝桥杯正式比赛的难度我个人觉得是:第一个程序题 < 第一个填空题 < 第二个大题 其他的题目难度可能就比较随机了。

回到题目，我们定义状态到第个怪物，第个怪物为第偶数次击败时的最大值; 到第个怪物，第个怪物为奇数次击败时的最大值。转移方程

code:

void solve() {
    int n;  cin >> n;
    vector<i64>a(n+1);
    vector dp(n+1,vector<i64>(2));
    for (int i=1;i <=n;i++){
        cin >> a[i];
    }
    i64 ans = 0;
    dp[1][0] = a[1];
    for (int i=2; i<=n; i++){
         dp[i][1] = dp[i-1][0] + 2*a[i];
         dp[i][0] = dp[i-1][1] + a[i];
        dp[i][1] = max(dp[i][1],dp[i-1][1]);
        dp[i][0] = max(dp[i][0],dp[i-1][0]);
    }
    cout << max(dp[n][0],dp[n][1]) << "\n";
}

B魔法舞会的最优搭档

本题是一个奇怪的dfs(好吧其实是我之前没见过这样优化的)。详情可以见原题此处跳转

code:

int a[20][20],n,ans;
bool vis[20];
void dfs(int now, int st){
    if (now > n){
        ans = max(ans,st);
        return;
    }
    int l = 0;
    for (int i=1; i<=2*n; i++){
        if (!vis[i]){
            l  =i;
            break;
        }
    }
    vis[l] = true;
    for (int i=1; i<=2*n; i++){
        if (!vis[i]){
            vis[i] = true;
            dfs(now+1,st^a[i][l]);
            vis[i] = false;
        }
    }
    vis[l] = false;
}
void solve(){
    cin >> n;
    for (int i=1; i<=2*n; i++){
        for (int j=i+1; j<=2*n; j++){
            cin >> a[i][j];
            a[j][i] = a[i][j];
        }
    }
    dfs(1,0);
    cout << ans << "\n";
} 

大部分人可能和我写一样的复杂度是

C 星际矿脉能量采集

一个树上问题，这题是本场最难的。 注意到只有,大概是15左右。也就意味着到节点u如果从根节点到u的路径上选择操作二的次数到了15那么包括u以及u以下的节点都会变成0。 定义状态 表示到了节点为止，的路径上已经执行了次操作二，且本次节点使用操作一的最大值; 表示到了节点为止，的路径上已经执行了次操作二，且本次节点使用操作二的最大值; 显然初始时 转移方程:

code:

int n,c,a[N];
i64 dp[N][16][2];
vector<vector<int>>g(N);
void dfs(int u, int fa){
    for (int i=0; i<=15; i++){
        dp[u][i][0] = (a[u]>>i)-c;
        dp[u][i][1] = (a[u]>>(i+1));
    }
    for (int v:g[u]){
        if (v == fa)continue;
        dfs(v,u);
    }
    for (int k=0; k<=15; k++){
        for (int v:g[u]){
            if (v ==fa)continue;
            dp[u][k][0] += max(dp[v][k][0],dp[v][k][1]);
            dp[u][k][1] += max(dp[v][min(k+1,15)][0],dp[v][min(k+1,15)][1]);
        }
    }
}
void solve() {
    cin >> n >> c;
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=1; i<n; i++){
        int a,b; cin >> a >> b;
        g[a].pb(b);  g[b].pb(a);
    }
    dfs(0,0);
    i64 ans = -INF;
    for (int k=0; k<=15; k++){
        ans = max({ans,dp[0][k][1],dp[0][k][0]});
    }
    cout << ans << "\n";
}

D 魔法药剂的品质检测

一个经典的算贡献题,简单来说就是维护一个保证 且范围内，所有数都是。

预处理一个数组, 表示的下一个不在 范围内的数的位置

然后我们计算包含每个点的贡献,显然如果 不在范围内，这个贡献显然为0，反之，我们取尝试更新求得离最近的, 得出节点的贡献为,算贡献的时候我们要保证范围内的数都是在范围内的，维护手段有多种。

code:

void solve() {
    int n,x,y;  cin >> n >> x >> y;
    vector<int>a(n+1),nxt(n+2);
    for (int i=1; i<=n; i++) cin >>a[i];
    nxt[n+1] = n+1;
    for (int i=n; i>=1; i--){
        if (a[i] >= y and a[i] <= x){
            nxt[i] = nxt[i+1];
        }
        else {
            nxt[i] = i;
        }
    }
    int l = 0, r = 0; i64 ans = 0;
    for (int i=1; i<=n; i++){
        if (a[i] < y or a[i] > x)continue;
        l = max(l,i);  r = max(r,i);
        bool f = false;
        while(a[l] != x and l <= n){
            if (a[l] > x or a[l] < y){
                f = true;
                break;
            }
            l++;
        }
        while(a[r] != y and r <= n){
            if (a[r] > x or a[r] < y){
                f = true;
                break;
            }
            r++;
        }
        if (f){
            i = max(l,r);
            continue;
        }
        int pos = max(l,r);
        ans += (nxt[pos]-pos);
    }
    cout <<ans << "\n";
}

E 魔法学院奖学金线

签到题，把所有点压在一个数组里排序后找一下中位数就好了

code:

void solve() {
    int m,n;  cin >> m >> n;
    vector<int>vec;
    for (int i=1; i<=m; i++){
        int x;  cin >> x;
        vec.pb(x);
    }
    for (int i=1; i<=n; i++){
        int x;  cin >> x;
        vec.pb(x);
    }
    sort(all(vec));
    if (vec.size()&1){
        cout << vec[vec.size()/2]*2;
    }
    else {
        i64 ans = vec[vec.size()/2] + vec[vec.size()/2-1];
        cout << ans << "\n";
    }
}

F 魔法雪橇载客赛

我们想象现在所有🦌都坐在雪橇上体重为，现在我们把一只🦌拿出来去拉雪橇，相当于往拉🦌的地方增加了，一个经典的贪心模型，我们按照排序做就好了。

code:

void solve() {
    int n;  cin >> n;
    i64 sum = 0;
    vector<pll>a(n+1);
    priority_queue<i64>q;
    for (int i=1; i<=n; i++){
        i64 w,p;  cin >> w >> p;
        a[i] = {w,p};
        sum += w;
        q.push(w+p);
    }
    i64 s = 0;
    while(q.size() and s < sum){
        s += q.top();
        q.pop();
    }
    cout << q.size() << "\n";
}

G 魔法图书馆的书架整理

我们明确对于坐标的书，如果前面有那么最后坐标就是

首先把所有书按照排序，去动态维护一个每个前面有多少行空行，并求得坐标的行。同理，求也一样

code:

struct node{
    i64 a,b,id;
};
void solve() {
    i64 h,w,n;  cin >> h >> w >> n;
    vector<node>a(n+1);
    for (int i=1; i<=n; i++){
        i64 c,d;  cin >> c >>d;
        a[i] = {c,d,i};
    }
    auto cmp1 = [&](node x, node y) ->bool{
        return x.a < y.a;  
    };
    auto cmp2= [&](node x, node y) -> bool{
        return x.b < y.b;  
    };
    sort(All(a),cmp1);
    i64 nx1 = 0, sum = 0;
    for (int i=1; i<=n;i++){
        auto [c,d,id] = a[i];
        sum += max(c-nx1-1,0ll);
        nx1 = c;
        a[i].a -= sum;
    }
    sort(All(a),cmp2);
    nx1 = 0;  sum = 0;
    for (int i=1; i<=n; i++){
        auto [c,d,id] = a[i];
        sum += max(d-nx1-1,0ll);
        nx1 = d;
        a[i].b -= sum;
    }
    vector<pii>ans(n+1);
    for (int i=1; i<=n; i++){
        auto [x,y,id] = a[i];
        ans[id] = {x,y};
    }
    for (int i=1; i<=n; i++){
        auto [x,y] = ans[i];
        cout << x << " " << y << "\n";
    }
}

H 魔法学院的课程规划

拓扑排序的模板题，没什么好说的，没学过当然不会。

code:

void solve() {
    int n,m;  cin >> n >> m;
    vector<vector<int>>g(n+1);
    vector<int>deg(n+1);
    for (int i=1; i<=m;i++){
        int a,b; cin >> a >> b;
        g[b].pb(a); deg[a]++;
    }
    vector<int>ans;  queue<int>q;
    for (int i=0; i<n; i++){
        if (!deg[i]){
            ans.pb(i);
            q.push(i);
        }
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        for (int v:g[u]){
            deg[v]--;
            if (!deg[v]){
                ans.pb(v);
                q.push(v);
            }
        }
    }
    if (ans.size() == n){
        cout << "Yes\n";
        for (auto i:ans){
            cout << i << " ";
        }
        return;
    }
    cout << "No\n";
}

头文件

#include <bits/stdc++.h>
#define lowbit(x) (x & - (x))
#define pii pair<int,int>
#define pil pair<int,long long>
#define pli pair<long long,int>
#define pss pair<string,string>
#define pll pair<long long,long long>
#define pdd pair<double,double>
#define fir first
#define sec second
#define Y(s) cout << s << "\n"
#define all(a) a.begin(),a.end()
#define All(a) a.begin()+1,a.end()
#define MP make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define i64 long long
#define i128 __int128_t
#define ull unsigned long long
#define ld long double
#define ll long long
using namespace std;
const int N = 3e5+100,M = 1e6,inf = 1e9,mod=998244353;
const long long INF = 1e18;
const double pi = 3.1415926535897932385,eps = 1e-9;
i64 ksm(i64 a, i64 b){
	i64 res = 1;
	while(b){
		if (b&1){
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}