题解
魔法冒险的战斗加成
https://ac.nowcoder.com/acm/contest/130157/A
蓝桥杯选拔赛题解
锐评: 总体感觉这场比赛偏难，对于未入门的选手来说还是比较吃力的，但是本质上还是考察积累(据出题人说全是原题)。 对标蓝桥杯来说的话，首先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;
}
查看22道真题和解析
