《公路》题解
题目大意
公路有 n 个站点，站点i到i+1距离vi公里。
站点i油价ai元/升，只能买整数升油。
1 升油跑 d 公里，油箱无限大，初始油箱为空，从 1 开到 n，求最小总花费。
思路拆分
核心思路：在当前站点买油，买到下一个比这个站点便宜的站点才加油。
关键点：
- 油只能买整数升，距离不一定是 d 的倍数，要用ceil向上取整算需要多少升油。
- 油箱无限，贪心策略：前面更便宜就尽量前面买。
- s：累计还需要行驶的公里数；买完油之后消耗掉 need*d 公里续航。
示例图解（n=4, d=5）
假设 n=4，d=5，站点间距离为 [3, 7, 4]，油价为 [4, 2, 3, 1]，我们逐步模拟贪心过程：
| 站点 i | 累计距离 s | 当前最低油价 mind | 需要升数 need | 累计花费 sum | 说明 |
|---|---|---|---|---|---|
| 1 | 3 | 4 | ceil(3/5)=1 | 4 | 在站点1买1升油，花费4元，续航5公里，剩余s=3-5=-2 |
| 2 | 3+7=10 | min(4,2)=2 | ceil(10/5)=2 | 4+2×2=8 | 在站点2买2升油，花费4元，续航10公里，剩余s=10-10=0 |
| 3 | 0+4=4 | min(2,3)=2 | ceil(4/5)=1 | 8+2×1=10 | 在站点3买1升油，花费2元，续航5公里，剩余s=4-5=-1 |
过程解读：
- 站点1：油价4元/升，先买1升（花费4元），能跑5公里，足够开到站点2。
- 站点2：油价降到2元/升，此时已累计需要行驶10公里，买2升（花费4元），刚好跑完到站点3的距离。
- 站点3：油价3元/升，但当前最低价仍是站点2的2元/升，所以继续按2元/升买1升（花费2元），足够开到终点站点4。
最终总花费为10 元。可以看到，贪心策略的核心就是：只要遇到更便宜的油站，就按当前最低价买够到下一个更便宜油站所需的油量，从而保证全程用最低价加油。
AC代码
#include<iostream>#include<cmath>usingnamespacestd;intn,d,ans,sum;intv[100005];inta[100005];intmain(){cin>>n>>d;for(inti=1;i<n;i++){cin>>v[i];}ints=0,mind=INT_MAX;for(inti=1;i<n;i++){cin>>a[i];if(i<n)s+=v[i];mind=min(mind,a[i]);if(s>0){longlongneed=ceil(1.0*s/d);sum+=need*mind;s-=need*d;}}cout<<sum;return0;}《决斗》题解
题目大意
每个怪兽攻击 = 防御
规则：
每回合选怪兽i攻击j(i≠j)：
如果ri>rj：j被干掉，退出游戏；
否则什么都不发生。
每只怪兽最多只能攻击 1 次，不管攻击成功还是失败。
游戏结束条件：场上剩下的所有存活怪兽，全都已经发动过攻击。求：最后场上最少能剩下多少只怪兽。
双指针核心思路
本质：贪心一一配对击杀，用刚好比它大的怪兽去杀它，最大化击杀总数。
- l：等待被打死的怪兽的位置
- r：当前拿出来当打手的怪兽位置
AC代码
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;vector<int>a(n);for(inti=0;i<n;i++){cin>>a[i];}sort(a.begin(),a.end());intl=0;for(intr=0;r<n;r++){if(a[r]>a[l]){l++;}}cout<<n-l;return0;}数学核心思路
我们可以知道，最后剩下来的怪兽数量等于战斗力相同的最多的怪兽数量。
为什么？
假设有a只战斗力为x的怪兽，b只战斗力为y的怪兽（x!=y）
那么————
在双方火拼之后，剩下来的必然是max（a,b）只怪兽。因为：
- 若a>b，x>y，则剩下来a只怪兽；
- 若a>b,x<y,这剩下来b+(a-b)=a只怪兽
同理可得，a与b打完后必然剩下max(a,b)只怪兽。
数学AC代码
#include<iostream>usingnamespacestd;inta[100005],ans=0;intmain(){intn;cin>>n;for(inti=0;i<n;i++){intx;cin>>x;a[x]++;ans=max(ans,a[x]);}cout<<ans;return0;}《消消乐》题解
题目大意
每次操作删掉两个相邻相同字符，删完之后字符串拼接。
一个字符串 “可消除” 代表反复操作后能变成空串。
求原字符串所有非空连续子串里面，有多少个是可消除的。
暴力思路（50分）
枚举每个起点i，把子串s[i…n‑1]丢进栈模拟。
在模拟过程中，每一次栈变空，就代表从起点 i 到当前位置 j 的子串 s [i~j] 合法，cnt 统计数量。
#include<iostream>#include<stack>usingnamespacestd;intn;intans;intcheck(string s){stack<char>t;intcnt=0;for(inti=0;i<s.size();i++){if(!t.empty()&&t.top()==s[i]){t.pop();}else{t.push(s[i]);}if(t.empty())cnt++;}returncnt;}intmain(){string s;cin>>n;cin>>s;for(inti=0;i<n;i++){string s1=s.substr(i,n-i);ans+=check(s1);}cout<<ans;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对应I=0，l-1=-1的空栈。
字符串的比较、哈希计算时间和字符串长度成正比。最坏O(n^2)，n大超时。
#include<bits/stdc++.h>usingnamespacestd;intn;intmain(){string s;cin>>n;cin>>s;string st;unordered_map<string,longlong>mp;mp[""]=1;longlongans=0;for(inti=0;i<n;i++){charc=s[i];if(!st.empty()&&st.back()==c){st.pop_back();}else{st.push_back(c);}ans+=mp[st];mp[st]++;}cout<<ans;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)出现多少次，加到答案。
#include<bits/stdc++.h>usingnamespacestd;usingull=unsignedlonglong;longlongn,ans=0;string s;intmain(){cin>>n>>s;string st;constull base=131;unordered_map<ull,longlong>mp;vector<char>stk(n+1);vector<ull>hx(n+1);hx[0]=0;mp[0]=1;inttop=0;for(inti=0;i<n;i++){charc=s[i];if(top>0&&stk[top]==c){top--;}else{top++;stk[top]=c;hx[top]=hx[top-1]*base+(c-'a'+1);}ull cnt=hx[top];ans+=mp[cnt];++mp[cnt];}cout<<ans;return0;}
