CSP 2023 公路、消消乐， 2024 决斗 题解

《公路》题解题目大意公路有 n 个站点站点i到i1距离vi公里。站点i油价ai元/升只能买整数升油。1 升油跑 d 公里油箱无限大初始油箱为空从 1 开到 n求最小总花费。思路拆分核心思路在当前站点买油买到下一个比这个站点便宜的站点才加油。关键点油只能买整数升距离不一定是 d 的倍数要用ceil向上取整算需要多少升油。油箱无限贪心策略前面更便宜就尽量前面买。s累计还需要行驶的公里数买完油之后消耗掉 need*d 公里续航。示例图解n4, d5假设 n4d5站点间距离为 [3, 7, 4]油价为 [4, 2, 3, 1]我们逐步模拟贪心过程站点 i累计距离 s当前最低油价 mind需要升数 need累计花费 sum说明134ceil(3/5)14在站点1买1升油花费4元续航5公里剩余s3-5-223710min(4,2)2ceil(10/5)242×28在站点2买2升油花费4元续航10公里剩余s10-1003044min(2,3)2ceil(4/5)182×110在站点3买1升油花费2元续航5公里剩余s4-5-1过程解读站点1油价4元/升先买1升花费4元能跑5公里足够开到站点2。站点2油价降到2元/升此时已累计需要行驶10公里买2升花费4元刚好跑完到站点3的距离。站点3油价3元/升但当前最低价仍是站点2的2元/升所以继续按2元/升买1升花费2元足够开到终点站点4。最终总花费为10 元。可以看到贪心策略的核心就是只要遇到更便宜的油站就按当前最低价买够到下一个更便宜油站所需的油量从而保证全程用最低价加油。AC代码#includeiostream#includecmathusingnamespacestd;intn,d,ans,sum;intv[100005];inta[100005];intmain(){cinnd;for(inti1;in;i){cinv[i];}ints0,mindINT_MAX;for(inti1;in;i){cina[i];if(in)sv[i];mindmin(mind,a[i]);if(s0){longlongneedceil(1.0*s/d);sumneed*mind;s-need*d;}}coutsum;return0;}《决斗》题解题目大意每个怪兽攻击 防御规则每回合选怪兽i攻击j(i≠j)如果rirjj被干掉退出游戏否则什么都不发生。每只怪兽最多只能攻击 1 次不管攻击成功还是失败。游戏结束条件场上剩下的所有存活怪兽全都已经发动过攻击。求最后场上最少能剩下多少只怪兽。双指针核心思路本质贪心一一配对击杀用刚好比它大的怪兽去杀它最大化击杀总数。l等待被打死的怪兽的位置r当前拿出来当打手的怪兽位置AC代码#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorinta(n);for(inti0;in;i){cina[i];}sort(a.begin(),a.end());intl0;for(intr0;rn;r){if(a[r]a[l]){l;}}coutn-l;return0;}数学核心思路我们可以知道最后剩下来的怪兽数量等于战斗力相同的最多的怪兽数量。为什么假设有a只战斗力为x的怪兽b只战斗力为y的怪兽x!y那么————在双方火拼之后剩下来的必然是maxa,b只怪兽。因为若abxy则剩下来a只怪兽若ab,xy,这剩下来b(a-b)a只怪兽同理可得a与b打完后必然剩下max(a,b)只怪兽。数学AC代码#includeiostreamusingnamespacestd;inta[100005],ans0;intmain(){intn;cinn;for(inti0;in;i){intx;cinx;a[x];ansmax(ans,a[x]);}coutans;return0;}《消消乐》题解题目大意每次操作删掉两个相邻相同字符删完之后字符串拼接。一个字符串 “可消除” 代表反复操作后能变成空串。求原字符串所有非空连续子串里面有多少个是可消除的。暴力思路50分枚举每个起点i把子串s[i…n‑1]丢进栈模拟。在模拟过程中每一次栈变空就代表从起点 i 到当前位置 j 的子串 s [i~j] 合法cnt 统计数量。#includeiostream#includestackusingnamespacestd;intn;intans;intcheck(string s){stackchart;intcnt0;for(inti0;is.size();i){if(!t.empty()t.top()s[i]){t.pop();}else{t.push(s[i]);}if(t.empty())cnt;}returncnt;}intmain(){string s;cinn;cins;for(inti0;in;i){string s1s.substr(i,n-i);anscheck(s1);}coutans;return0;}90分未优化字符哈希核心模型关键知识点定义f(i)把原串前缀 s[0~i]做栈消消乐之后得到的栈字符串。子串s[l~i]是可消除的 当且仅当f(i)f(l-1)}。证明f(i)前缀0~i消完之后栈状态。f(l-1)前缀0~l-1消完之后栈状态。如果两者完全一样说明中间这一段[l,i]抵消干净了正好为空子串合法。所以问题转化遍历 i统计前面有多少个l-1使得f(l‑1)f(i)累加数量就是答案。mp[st]记录之前该栈状态出现过多少次。mp[“”]1对应I0l-1-1的空栈。字符串的比较、哈希计算时间和字符串长度成正比。最坏O(n^2)n大超时。#includebits/stdc.husingnamespacestd;intn;intmain(){string s;cinn;cins;string st;unordered_mapstring,longlongmp;mp[]1;longlongans0;for(inti0;in;i){charcs[i];if(!st.empty()st.back()c){st.pop_back();}else{st.push_back(c);}ansmp[st];mp[st];}coutans;return0;}AC思路其实就是改用数组stk[] 整数top手动模拟栈。hx[top]栈内当前元素的多项式哈希值。栈长度为 top 时hx[top]就是这个栈状态的唯一 hash。压入字符hx[top]hx[top‑1]*base val©弹出字符直接top–自动复用旧的 hx 值不需要重新算核心要点f(x)字符串前 x 个字符跑一遍消消乐栈得到的栈。如果两个前缀的栈一模一样中间这一段正好互相抵消为空。遍历 i用哈希把f(i)压缩成数字map 统计前面f(i)出现多少次加到答案。#includebits/stdc.husingnamespacestd;usingullunsignedlonglong;longlongn,ans0;string s;intmain(){cinns;string st;constull base131;unordered_mapull,longlongmp;vectorcharstk(n1);vectorullhx(n1);hx[0]0;mp[0]1;inttop0;for(inti0;in;i){charcs[i];if(top0stk[top]c){top--;}else{top;stk[top]c;hx[top]hx[top-1]*base(c-a1);}ull cnthx[top];ansmp[cnt];mp[cnt];}coutans;return0;}