CSP-S 2021 廊桥分配 CSP-S 2023 密码锁 CSP-J 2023 小苹果 洛谷 P2985 Chocolate Eating S 题解

洛谷 P2985 Chocolate Eating S

题意梳理

1. 有 N 块巧克力，必须按顺序吃，一共 D 天。
2. 幸福值初始cur=0；每晚睡觉后，幸福值向下取整减半。
3. 某天吃若干巧克力：吃完巧克力后的幸福值，就是当天的幸福值。
4. 目标：最大化D 天中每天睡前幸福值的最小值（最大化最小值，经典二分答案模型）。
5. 输出：最大的最低幸福值；输出每一块巧克力在哪一天吃掉。
   注意：数据范围很大，所以总和可以很大，要用long long防止溢出。

核心思想：二分答案

“最大化最小值” 标准套路：二分判定答案 mid：
check(x)函数：判断是否存在吃巧克力方案，保证每一天结束时幸福值都≥x，并且全部巧克力在 D 天内按顺序吃完。

如果check(x)=true：说明可以做到每天最低至少 x，尝试找更大，记录方案，二分右边界：l=mid+1。
如果check(x)=false：做不到，只能往小找：r=mid‑1。
二分范围：l=0，r=text所有巧克力幸福总和。

check函数完整解析

boolcheck(longlongx){longlongcur=0,s=0;//cur：当前幸福；s：已经吃掉的巧克力块数for(inti=1;i<=d;i++)//枚举第i天{cur/=2;//睡一觉，前一天晚上幸福减半，来到新一天起床//只要今天结束幸福还达不到x，就继续吃巧克力（按顺序）while(cur<x&&s<n){s++;cur+=a[s];b[s]=i;//记录第s块巧克力是第i天吃}if(cur<x)//今天吃完所有剩下巧克力依旧达不到x → x不可行{returnfalse;}}//循环走完D天，剩下没吃完的巧克力，全部丢在最后一天d吃for(inti=s+1;i<=n;i++){b[i]=d;}returntrue;}

完整AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,d;inta[50010],b[50010],c[50010];// check(x): 是否可以保证D天，每天结束幸福>=xboolcheck(longlongx){longlongcur=0;ints=0;//s:已经吃掉的巧克力数目for(inti=1;i<=d;i++){cur/=2;//睡一晚，幸福减半，新一天开始//当前幸福不足x，继续吃巧克力while(cur<x&&s<n){s++;cur+=a[s];b[s]=i;}if(cur<x)returnfalse;//今天无论如何达不到x}//D天走完，剩下全部放最后一天for(inti=s+1;i<=n;i++){b[i]=d;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>d;longlongsum=0;for(inti=1;i<=n;i++){cin>>a[i];sum+=a[i];}longlongl=0,r=sum,ans=0;while(l<=r){longlongmid=(l+r)/2;if(check(mid)){ans=mid;copy(begin(b),end(b),begin(c));l=mid+1;}else{r=mid-1;}}cout<<ans<<'\n';for(inti=1;i<=n;i++){cout<<c[i]<<'\n';}return0;}

CSP-J 2023 小苹果

题意理解

n个苹果从左到右排成一列。每天操作：从第 1 个开始，每隔 2 个拿走 1 个。剩下苹果保持原顺序重新排成新序列。
问两个值：

1. 一共多少天拿完全部苹果。
2. 原始编号为n的苹果，会在第几天被拿走。

代码拆分

整个代码可以分为两个部分，计算总天数与哪天拿n；

第一部分：总天数

intx=n;while(x>0){x-=(x+2)/3;cnt++;}

(x+2)/3是计算今天拿走了多少个（x+2是为了向上取整）。

第二部分：哪天拿走n

intday=0;while(true){day++;if(n%3==1){break;}n=n-ceil(n/3.0);}

注意：这里的n不再是原始总苹果数，代表：原始编号为 n 的苹果，在当前这一轮序列里的位置

今天要拿走的是：位置满足pos%3 =1 的苹果。
如果 pos%3 ==1：这个苹果就在今天被拿走，循环结束，day 就是答案。
如果没有被拿走，它会留在序列中，需要计算它下一轮的新位置，继续下一天。
新位置 = 原位置 − 前面被拿走苹果的个数。

完整AC代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;//第一部分：求拿完所有苹果总天数cntintx=n;intcnt=0;while(x>0){// 本轮拿走ceil(x/3) = (x+2)/3x-=(x+2)/3;cnt++;}//第二部分：求原始编号n的苹果在哪一天被拿走intpos=n;// pos：该苹果在当前一轮序列的位置（1‑based）intday=0;while(true){day++;if(pos%3==1)// 当前位置模3等于1，今天被拿走{break;}//没被拿走，更新为下一轮的位置pos=pos-ceil(pos/3.0);}cout<<cnt<<" "<<day;return0;}

CSP-S 2023 密码锁

题意简述

5 位密码锁，每一位是 0‑9 环形（9 下一个是 0）。锁车操作：从正确密码出发，恰好执行一次操作，操作二选一：
转动某 1 个拨圈任意幅度；
转动一对相邻拨圈，两个拨圈转动幅度完全相同。
现在给出 n 个锁车后的状态（全部不等于正确密码）。求：有多少种 5 位密码，满足：给出的每一个状态，都可以由该密码通过恰好一次合法锁车操作得到。
数据范围：1<=n<=8。

题目分析

由于总密码空间=100000，可以暴力枚举全部候选密码。

核心函数详细解释

boolcheck(inta[],intb[][5]){// 遍历每一个给出的锁后状态for(inti=0;i<n;i++){ints=0;//统计a(正确密码)与b[i](锁后状态)有多少位不一样for(intj=0;j<5;j++){if(b[i][j]!=a[j])s++;}// s=0：等于原密码，题目说锁后状态不能是正确密码；s>2超过最多改动2位，直接falseif(s>2||s==0)return0;if(s==1)continue;//只改1位，合法，下一个状态// s==2：恰好两位不同，必须是相邻，偏移模10相等for(intj=0;j<5;j++){if(b[i][j]!=a[j]){// j位不同，j+1必须也要不同，否则不是相邻两位if(b[i][j+1]==a[j+1])return0;// 计算两个位置的偏移模10，必须相等elseif((b[i][j]-a[j]+10)%10==(b[i][j+1]-a[j+1]+10)%10){break;//满足条件，退出j循环，该状态合法}elsereturn0;//偏移不等，非法}}}returntrue;//n个状态全部校验通过，这是一个合法正确密码}

注意：j只会找到第一个不一样的下标，要求j与j+1同时不一样，偏移相等，就满足 “相邻两位改动、偏移相同”。

完整AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,a[6],b[10][5],ans=0;boolcheck(inta[],intb[][5]){for(inti=0;i<n;i++){ints=0;for(intj=0;j<5;j++){if(b[i][j]!=a[j])s++;}if(s>2||s==0)return0;if(s==1)continue;for(intj=0;j<5;j++){if(b[i][j]!=a[j]){if(b[i][j+1]==a[j+1])return0;elseif((b[i][j]-a[j]+10)%10==(b[i][j+1]-a[j+1]+10)%10){break;}elsereturn0;}}}returntrue;}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0;j<=4;j++){cin>>b[i][j];}}for(inti=100000;i<=199999;i++)//这里有一个枚举小技巧：如果不想五重循环的话，可以这样做。{intx=i;for(intj=4;j>=0;j--){a[j]=x%10;x/=10;}if(check(a,b)){ans++;}}cout<<ans;return0;}

CSP-S 2021 廊桥分配

题目大意

机场一共有 n 个廊桥，可以分配一部分给国内区，剩下给国际区。
国内航班只能使用国内区廊桥，国际航班只能使用国际区廊桥。飞机严格按照抵达时间先后到达，遵循先到先得：

1. 如果本区还有空闲廊桥，则占用廊桥停靠；
2. 没有空闲廊桥就停靠远机位。远机位数量无限。
   给定所有国内、国际航班的抵达、离开时刻，请你把 n 个廊桥划分给国内和国际，求能够停靠廊桥的飞机数量的最大值。

解题思路

这道题有点像力扣上的“会议室安排”。使用小根堆维护正在被占用廊桥的飞机的离开时间。

处理每一架航班[l,r]：

1. 将堆中所有离开时间小于l的元素弹出，代表飞机飞走，廊桥释放；
2. 如果堆内元素数量小于 k，代表还有空闲廊桥：该飞机停靠廊桥，将离开时间入堆，计数 + 1；
3. 否则没有廊桥可用，去远机位。

暴力做法：枚举国内分配 i 个廊桥，国际分配n-i个廊桥，对每一个 i 都完整模拟一遍航班。
暴力超时的原因：对于不同的廊桥数量，重复模拟同一批航班，大量重复运算。

优化

我们希望只模拟一次全部 n 个廊桥，直接得到分配每个廊桥对应的答案。给廊桥编号1,2,3…n，遵循规则：每次优先选择编号最小的空闲廊桥。
维护两个堆：

1. b_id：小根堆，存储 pair (飞机离开时间，廊桥编号)，记录哪些廊桥正在被占用；
2. q_id：小根堆，存储空闲廊桥的编号。

模拟过程：

1. 初始化，1到n全部廊桥放入空闲堆；
2. 遍历每一个航班，先把已经飞走的飞机对应的廊桥释放，归还到空闲编号堆；
3. 如果存在空闲廊桥，取出编号最小的廊桥给当前航班，记录这个廊桥承接了 1 架飞机；
4. res[id] 代表：编号为 id 的廊桥一共承接多少架飞机。

对res数组求前缀和，得到：
pd[x]：国内分配 x 个廊桥，可以停靠的飞机总数；
pg[x]：国际分配 x 个廊桥，可以停靠的飞机总数。
最后枚举所有分配方案：国内拿 i 个廊桥，国际拿n-i个廊桥，求
ans=max(ans,pd[i]+pg[n-i])(0<=i<=n)

#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;intn,m1,m2;vector<int>js(vector<pair<int,int>>&v,intk){vector<int>res(k+1,0);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>b_id;//廊桥的编号和离开时间priority_queue<int,vector<int>,greater<int>>q_id;//空闲的廊桥编号for(inti=1;i<=k;i++){q_id.push(i);}for(inti=0;i<v.size();i++){intl=v[i].first;intr=v[i].second;// 释放已经离开的飞机，归还廊桥编号while(!b_id.empty()&&b_id.top().first<=l){intid=b_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty()){continue;}intid=q_id.top();q_id.pop();res[id]++;b_id.push({r,id});}returnres;}intmain(){cin>>n>>m1>>m2;vector<pair<int,int>>d(m1);vector<pair<int,int>>g(m2);for(inti=0;i<m1;i++){cin>>d[i].first>>d[i].second;}for(inti=0;i<m2;i++){cin>>g[i].first>>g[i].second;}sort(d.begin(),d.end());sort(g.begin(),g.end());intans=0;vector<int>cd=js(d,n);vector<int>cg=js(g,n);vector<int>pd(n+1,0),pg(n+1,0);//前缀和数组for(inti=0;i<=n;i++){pd[i]=pd[i-1]+cd[i];pg[i]=pg[i-1]+cg[i];}for(inti=0;i<=n;i++){ans=max(ans,pd[i]+pg[n-i]);}cout<<ans;return0;}