洛谷 P2985 Chocolate Eating S题意梳理有 N 块巧克力必须按顺序吃一共 D 天。幸福值初始cur0每晚睡觉后幸福值向下取整减半。某天吃若干巧克力吃完巧克力后的幸福值就是当天的幸福值。目标最大化D 天中每天睡前幸福值的最小值最大化最小值经典二分答案模型。输出最大的最低幸福值输出每一块巧克力在哪一天吃掉。注意数据范围很大所以总和可以很大要用long long防止溢出。核心思想二分答案“最大化最小值” 标准套路二分判定答案 midcheck(x)函数判断是否存在吃巧克力方案保证每一天结束时幸福值都≥x并且全部巧克力在 D 天内按顺序吃完。如果check(x)true说明可以做到每天最低至少 x尝试找更大记录方案二分右边界lmid1。如果check(x)false做不到只能往小找rmid‑1。二分范围l0rtext所有巧克力幸福总和。check函数完整解析boolcheck(longlongx){longlongcur0,s0;//cur当前幸福s已经吃掉的巧克力块数for(inti1;id;i)//枚举第i天{cur/2;//睡一觉前一天晚上幸福减半来到新一天起床//只要今天结束幸福还达不到x就继续吃巧克力按顺序while(curxsn){s;cura[s];b[s]i;//记录第s块巧克力是第i天吃}if(curx)//今天吃完所有剩下巧克力依旧达不到x → x不可行{returnfalse;}}//循环走完D天剩下没吃完的巧克力全部丢在最后一天d吃for(intis1;in;i){b[i]d;}returntrue;}完整AC代码#includebits/stdc.husingnamespacestd;intn,d;inta[50010],b[50010],c[50010];// check(x): 是否可以保证D天每天结束幸福xboolcheck(longlongx){longlongcur0;ints0;//s:已经吃掉的巧克力数目for(inti1;id;i){cur/2;//睡一晚幸福减半新一天开始//当前幸福不足x继续吃巧克力while(curxsn){s;cura[s];b[s]i;}if(curx)returnfalse;//今天无论如何达不到x}//D天走完剩下全部放最后一天for(intis1;in;i){b[i]d;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinnd;longlongsum0;for(inti1;in;i){cina[i];suma[i];}longlongl0,rsum,ans0;while(lr){longlongmid(lr)/2;if(check(mid)){ansmid;copy(begin(b),end(b),begin(c));lmid1;}else{rmid-1;}}coutans\n;for(inti1;in;i){coutc[i]\n;}return0;}CSP-J 2023 小苹果题意理解n个苹果从左到右排成一列。每天操作从第 1 个开始每隔 2 个拿走 1 个。剩下苹果保持原顺序重新排成新序列。问两个值一共多少天拿完全部苹果。原始编号为n的苹果会在第几天被拿走。代码拆分整个代码可以分为两个部分计算总天数与哪天拿n第一部分总天数intxn;while(x0){x-(x2)/3;cnt;}(x2)/3是计算今天拿走了多少个x2是为了向上取整。第二部分哪天拿走nintday0;while(true){day;if(n%31){break;}nn-ceil(n/3.0);}注意这里的n不再是原始总苹果数代表原始编号为 n 的苹果在当前这一轮序列里的位置今天要拿走的是位置满足pos%3 1 的苹果。如果 pos%3 1这个苹果就在今天被拿走循环结束day 就是答案。如果没有被拿走它会留在序列中需要计算它下一轮的新位置继续下一天。新位置 原位置 − 前面被拿走苹果的个数。完整AC代码#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;//第一部分求拿完所有苹果总天数cntintxn;intcnt0;while(x0){// 本轮拿走ceil(x/3) (x2)/3x-(x2)/3;cnt;}//第二部分求原始编号n的苹果在哪一天被拿走intposn;// pos该苹果在当前一轮序列的位置1‑basedintday0;while(true){day;if(pos%31)// 当前位置模3等于1今天被拿走{break;}//没被拿走更新为下一轮的位置pospos-ceil(pos/3.0);}coutcnt day;return0;}CSP-S 2023 密码锁题意简述5 位密码锁每一位是 0‑9 环形9 下一个是 0。锁车操作从正确密码出发恰好执行一次操作操作二选一转动某 1 个拨圈任意幅度转动一对相邻拨圈两个拨圈转动幅度完全相同。现在给出 n 个锁车后的状态全部不等于正确密码。求有多少种 5 位密码满足给出的每一个状态都可以由该密码通过恰好一次合法锁车操作得到。数据范围1n8。题目分析由于总密码空间100000可以暴力枚举全部候选密码。核心函数详细解释boolcheck(inta[],intb[][5]){// 遍历每一个给出的锁后状态for(inti0;in;i){ints0;//统计a(正确密码)与b[i](锁后状态)有多少位不一样for(intj0;j5;j){if(b[i][j]!a[j])s;}// s0等于原密码题目说锁后状态不能是正确密码s2超过最多改动2位直接falseif(s2||s0)return0;if(s1)continue;//只改1位合法下一个状态// s2恰好两位不同必须是相邻偏移模10相等for(intj0;j5;j){if(b[i][j]!a[j]){// j位不同j1必须也要不同否则不是相邻两位if(b[i][j1]a[j1])return0;// 计算两个位置的偏移模10必须相等elseif((b[i][j]-a[j]10)%10(b[i][j1]-a[j1]10)%10){break;//满足条件退出j循环该状态合法}elsereturn0;//偏移不等非法}}}returntrue;//n个状态全部校验通过这是一个合法正确密码}注意j只会找到第一个不一样的下标要求j与j1同时不一样偏移相等就满足 “相邻两位改动、偏移相同”。完整AC代码#includebits/stdc.husingnamespacestd;intn,a[6],b[10][5],ans0;boolcheck(inta[],intb[][5]){for(inti0;in;i){ints0;for(intj0;j5;j){if(b[i][j]!a[j])s;}if(s2||s0)return0;if(s1)continue;for(intj0;j5;j){if(b[i][j]!a[j]){if(b[i][j1]a[j1])return0;elseif((b[i][j]-a[j]10)%10(b[i][j1]-a[j1]10)%10){break;}elsereturn0;}}}returntrue;}intmain(){cinn;for(inti0;in;i){for(intj0;j4;j){cinb[i][j];}}for(inti100000;i199999;i)//这里有一个枚举小技巧如果不想五重循环的话可以这样做。{intxi;for(intj4;j0;j--){a[j]x%10;x/10;}if(check(a,b)){ans;}}coutans;return0;}CSP-S 2021 廊桥分配题目大意机场一共有 n 个廊桥可以分配一部分给国内区剩下给国际区。国内航班只能使用国内区廊桥国际航班只能使用国际区廊桥。飞机严格按照抵达时间先后到达遵循先到先得如果本区还有空闲廊桥则占用廊桥停靠没有空闲廊桥就停靠远机位。远机位数量无限。给定所有国内、国际航班的抵达、离开时刻请你把 n 个廊桥划分给国内和国际求能够停靠廊桥的飞机数量的最大值。解题思路这道题有点像力扣上的“会议室安排”。使用小根堆维护正在被占用廊桥的飞机的离开时间。处理每一架航班[l,r]将堆中所有离开时间小于l的元素弹出代表飞机飞走廊桥释放如果堆内元素数量小于 k代表还有空闲廊桥该飞机停靠廊桥将离开时间入堆计数 1否则没有廊桥可用去远机位。暴力做法枚举国内分配 i 个廊桥国际分配n-i个廊桥对每一个 i 都完整模拟一遍航班。暴力超时的原因对于不同的廊桥数量重复模拟同一批航班大量重复运算。优化我们希望只模拟一次全部 n 个廊桥直接得到分配每个廊桥对应的答案。给廊桥编号1,2,3…n遵循规则每次优先选择编号最小的空闲廊桥。维护两个堆b_id小根堆存储 pair (飞机离开时间廊桥编号)记录哪些廊桥正在被占用q_id小根堆存储空闲廊桥的编号。模拟过程初始化1到n全部廊桥放入空闲堆遍历每一个航班先把已经飞走的飞机对应的廊桥释放归还到空闲编号堆如果存在空闲廊桥取出编号最小的廊桥给当前航班记录这个廊桥承接了 1 架飞机res[id] 代表编号为 id 的廊桥一共承接多少架飞机。对res数组求前缀和得到pd[x]国内分配 x 个廊桥可以停靠的飞机总数pg[x]国际分配 x 个廊桥可以停靠的飞机总数。最后枚举所有分配方案国内拿 i 个廊桥国际拿n-i个廊桥求ansmax(ans,pd[i]pg[n-i])(0in)#includeiostream#includealgorithm#includequeueusingnamespacestd;intn,m1,m2;vectorintjs(vectorpairint,intv,intk){vectorintres(k1,0);priority_queuepairint,int,vectorpairint,int,greaterpairint,intb_id;//廊桥的编号和离开时间priority_queueint,vectorint,greaterintq_id;//空闲的廊桥编号for(inti1;ik;i){q_id.push(i);}for(inti0;iv.size();i){intlv[i].first;intrv[i].second;// 释放已经离开的飞机归还廊桥编号while(!b_id.empty()b_id.top().firstl){intidb_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty()){continue;}intidq_id.top();q_id.pop();res[id];b_id.push({r,id});}returnres;}intmain(){cinnm1m2;vectorpairint,intd(m1);vectorpairint,intg(m2);for(inti0;im1;i){cind[i].firstd[i].second;}for(inti0;im2;i){cing[i].firstg[i].second;}sort(d.begin(),d.end());sort(g.begin(),g.end());intans0;vectorintcdjs(d,n);vectorintcgjs(g,n);vectorintpd(n1,0),pg(n1,0);//前缀和数组for(inti0;in;i){pd[i]pd[i-1]cd[i];pg[i]pg[i-1]cg[i];}for(inti0;in;i){ansmax(ans,pd[i]pg[n-i]);}coutans;return0;}