A、能量任务
链接：https://ac.nowcoder.com/acm/contest/138881/A
来源：牛客网
有 n 个任务。执行第 i个任务前，你的当前能量必须不少于 hi；任务完成后，能量变化 di，即变为当前能量+di
每个任务必须且只能执行一次，你可以自由决定执行顺序。所有时刻能量都不能为负。
已知 hi+di≥0，因此只要执行前满足门槛，执行后就不会立刻变成负数。
求完成所有任务所需的最小初始能量。
这道题我觉得难点主要在排序上，还有就是找一个规律，我刚开始认为的是对于di<0而言，di越大越先走这个门，但是不对，后来得出结论，应该是hi+di越大越先走，还有排序上，普通的sort只能进行升序排序，所以我们要找其他方法，现在有两种比较常用的排序，首先是
sort(fu.begin(),fu.end(),[](auto &a,auto &b){ ll sa=a.first+a.second; ll sb=b.first+b.second; return sa>sb; });这个排序方法我第一次见但是很实用，就是在最基础的sort后面加上[](auto &a,auto &b)后面再跟上return 即可。
还有一种方法就是用结构体排序
bool cmp(node a,node b) { if(a.d<0||b.d<0) { if(a.d==b.d)return a.h>b.h; else if(a.d<0&&b.d<0) { int c=a.h+a.d; int d=b.h+b.d; return c>d; } else return a.d>b.d; } return a.h<b.h; }这个排序规则我比起前一个更好理解但是写起来比较复杂，是最基础的排序。
看代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int n; cin>>n; ll h,d; // res：存放d>=0 增益任务（做完能量上升/不变） vector<pair<ll,ll>>res; // fu：存放d<0 亏损任务（做完能量下降） vector<pair<ll,ll>>fu; for(int i=0;i<n;i++){ cin>>h>>d; if(d>=0) { res.emplace_back(h,d); } else{ fu.emplace_back(h,d); } } // 增益任务 pair默认先按first(h)升序排序，正好符合要求：h从小到大 sort(res.begin(),res.end()); // 亏损任务排序规则：s=h+d 从大到小 sort(fu.begin(),fu.end(),[](auto &a,auto &b){ ll sa=a.first+a.second; ll sb=b.first+b.second; return sa>sb; }); ll ans=0; // ans：最终需要的最小初始能量 ll r=0; // r：模拟当前拥有的能量，初始假定为0 // 先执行所有增益任务 for(auto x:res){ ll hi = x.first; ll di = x.second; // 当前能量不够开启任务，需要补足初始能量缺口 if(r<hi){ ans += hi - r; r = hi; // 补足后能量刚好到达门槛hi } r += di; // 完成任务，能量变化 } // 再执行所有亏损任务 for(auto x:fu){ ll hi = x.first; ll di = x.second; if(r<hi){ ans += hi - r; r = hi; } r += di; } cout<<ans<<endl; return 0; }B、三色平衡
链接：https://ac.nowcoder.com/acm/contest/138881/B
来源：牛客网
给定一个只包含字符 0、1、2 的字符串 sss。
一个子串是“平衡的”，当且仅当字符 0、1、2在该子串中出现次数相同。
求最长平衡子串的长度。空串也视为平衡，因此无解时答案为 0。
对于这道题我们先设
pre0[r]：前 r 个字符中 0 的个数
pre1[r]：前 r 个字符中 1 的个数
pre2[r]：前 r 个字符中 2 的个数
区间[l+1 ~ r]满足平衡：
(pre0[r]-pre0[l] = pre1[r]-pre1[l] = pre2[r]-pre2[l])
拆开两个等式：
(pre0[r]-pre1[r] = pre0[l]-pre1[l] \ pre1[r]-pre2[r] = pre1[l]-pre2[l])
结论：
只要两个位置l、r的二元组(c0-c1 , c1-c2)一模一样，中间这段子串就是合法平衡子串。
解题套路
- 一边遍历字符串，实时维护当前前缀总数量 c0,c1,c2；
- 算出当前状态二元组
(d1=c0-c1, d2=c1-c2)； - 哈希表记录每个二元组第一次出现的位置（存第一次！越早，区间越长）；
- 如果状态曾经出现过：计算区间长度，更新最大值；
- 如果没出现：把当前状态和下标存进哈希。
下标体系
- 虚拟初始状态：还没读任何字符，c0=c1=c2=0，状态 (0,0)，逻辑下标 = 0
- 字符串原生下标 i（0 开始），处理完 s [i] 之后，对应前缀逻辑下标 = i+1
长度公式：
旧逻辑下标 pos，当前逻辑下标 i+1
子串长度 = (i+1) - pos = i-pos+1
- 初始化不能忘！
mp[{0,0}] = 0如果不写，从字符串开头开始的合法子串识别不出来，直接错误。
易错点
- 二元组两个差值千万别算错：d1=c0-c1，d2=c1-c2，不能乱换顺序；
- 哈希只存第一次出现的下标，后来遇到相同状态不能覆盖；
- 下标体系一套用到底，不要混用两套下标；
- 长度公式不要随手乱改
+1 / -1； - map 复杂度 O (nlogn)，极限大数据可能超时；想要更快可以把 pair 编码成 long long 换 unordered_map。
代码解释
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n; // n 代表字符串长度 cin>>n; // 读取字符串长度 string s; cin>>s; // 读取由0、1、2构成的字符串 int ans=0; // ans保存最长平衡子串长度，初始0（无合法子串输出0） // map：键是二元组(d1,d2)，值是该状态第一次对应的前缀下标 map<pair<int,int>,int>mp; mp[{0,0}]=0; // 初始化：空前缀（还没读取任何字符）c0=c1=c2=0，下标记作0 int c0=0,c1=0,c2=0; // c0：0的前缀总数；c1：1的前缀总数；c2：2的前缀总数 // i 是字符串s的下标，从0到n-1（原生0下标遍历字符串） for(int i=0;i<n;i++){ // 根据当前字符，对应计数+1 if(s[i]=='0') c0++; else if(s[i]=='1') c1++; else c2++; int d1=c0-c1; // 差值1：0的总数 − 1的总数 int d2=c1-c2; // 差值2：1的总数 − 2的总数 // 二元组 (d1,d2) 相同 → 中间区间0、1、2数量相等，子串合法 if(mp.count({d1,d2})){ // 这个状态之前出现过 int pos=mp[{d1,d2}]; // 取出第一次出现时的前缀下标 ans=max(ans,i-pos+1);// 更新最长长度 } else{ // 首次出现，存入map；i+1作为前缀逻辑下标（对齐最初mp[{0,0}]=0的体系） mp[{d1,d2}]=i+1; } } cout<<ans<<endl; // 输出最长平衡子串长度 return 0; }C余数清理
链接：https://ac.nowcoder.com/acm/contest/138881/C
来源：牛客网
给定一个长度为 n 的非负整数序列和一个正整数 m。
你必须删除一个非空连续区间，并且至少保留一个元素。要求删除后剩余所有元素之和能够被 m 整除。
请最大化剩余元素的数量。如果不存在合法方案，输出 −1。
注意：删除区间后，区间左侧和右侧的元素都会保留，但不要求它们在原序列中相邻。
对于这道题我们先设总和 S，删掉区间 [L,R]，删掉和 = pre [R]-pre [L-1]
要求 ((S - (pre[r]-pre[pos]mod m = 0)（pos=L-1）
变形：(pre[pos] = (pre[R]-S) mod m)
遍历每个右端点 R，算出需要匹配的余数 tar，看左边有没有 pos 满足余数相等。
想要删除区间最短，pos 要尽量靠近 R，所以每次循环结束直接更新 map 存当前余数的最新下标，不要只存第一次。
限制条件：删除长度不能等于 n（不能把所有数字删光）。
最后没找到合法方案输出-1.
现在我们来看代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[200009]; //存储原始数组 ll n,m; //n数组长度，m模数 ll pre[200009]; //前缀和模m数组 int main(){ cin>>n>>m; ll sum=0; pre[0]=0; //前0项前缀模等于0 for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; //累加求数组全部总和 pre[i]=(pre[i-1]+a[i])%m;//计算前缀和对m取模 } ll mod_sum=sum%m; //总和取模m map<ll,ll>mp; //key:余数 value:余数最近出现的下标 mp[0]=0; //初始化pre[0]=0，下标0 int mx=-1; //答案，初始-1代表无解 for(int r=1;r<=n;r++){ //枚举删除区间右端点r ll t=(pre[r]-mod_sum)%m; //计算想要匹配的目标余数 if(t<0) t+=m; //C++负数取模修复，转为0~m-1 if(mp.count(t)){ //左边存在该余数的位置 int len=r-mp[t]; //得到删除区间的长度 if(len<n){ //不能把全部元素删掉 mx=max(mx,(int)(n-len)); //更新最大保留元素数量 } } mp[pre[r]]=r; //更新，保存当前余数最近的下标，覆盖旧值 } cout<<mx<<endl; //输出答案 return 0; }G、wnd的魔法排序
https://ac.nowcoder.com/acm/contest/138881/C
题意
n≤11，构造 1~n 全排列，相邻数字之和为质数，字典序从小到大输出所有合法排列。
核心解法：全排列回溯模板
- 质数预处理：两数最大和 21，筛 2~21 质数；
- DFS 参数 step：当前填充第 step 位；vis 数组标记数字是否已使用；
- 从小到大枚举数字天然保证字典序；
- 标准回溯流程：选数→递归填下一位→回溯撤销标记
b[i]=0；
#include<bits/stdc++.h> using namespace std; int b[12]={0}; // 标记数组，b[i]=1 代表数字i已经被选入排列，0代表未使用 int n; // 排列长度，数字范围1~n int ans[12]={0}; // ans数组保存当前搜到的合法排列，ans[step]代表第step个位置填的数 // 判断x是不是质数 bool check(int x){ if(x==2) return true; // 2是质数 // 从2枚举到sqrt(x)，尝试寻找因子 for(int i=2;i<=sqrt(x);i++){ if(x%i==0) return false; // 能整除，不是质数 } return true; // 找不到因子，是质数 } // step：当前正在填充排列的第 step 个位置 void dfs(int step){ // 递归边界：所有位置全部填完（一共n个位置，step走到n+1代表填充完毕） if(step==n+1){ // 输出完整排列 for(int i=1;i<=n;i++){ cout<<ans[i]<<" "; } cout<<endl; return ; } // 尝试枚举可以放在当前位置的数字 1~n for(int i=1;i<=n;i++){ if(b[i]==1) continue; // 数字i已经用过，跳过 // step==1：第一个位置，没有前一个数字，直接合法 // 不是第一位：前一个数字 ans[step-1] 和当前i相加必须是质数 if(step==1||check(ans[step-1]+i)){ ans[step]=i; // 当前位置填入数字i } else continue; // 和前数之和不是质数，不能选这个i b[i]=1; // 标记数字i已经被占用 dfs(step+1); // 递归填充下一个位置 b[i]=0; // 回溯：取消标记，释放数字i } } int main(){ cin>>n; // 输入排列长度n dfs(1); // 从第1个位置开始搜索 return 0; }I、遗迹核心的临界容差
链接：https://ac.nowcoder.com/acm/contest/138881/I
来源：牛客网
在星陨荒漠的深处，考古队发掘出了一条由 N 座储能核心组成的远古供能矩阵。这些核心一字排开，每一座核心都封存着一个整数灵压强度值 Ai。
相邻两座核心之间由能量导管连接。如果这两座核心的灵压值之差的绝对值超过了一个阈值 X，那么这段导管就会产生能量扰动，导致它所在的那一段连续回路整体变得不稳定。换句话说，一段连续的核心序列是稳定的，当且仅当这段序列里任意相邻两座核心的灵压差都不超过 X。
为了维持整体稳定，工程部可以在任意两座相邻核心之间插入一个空间隔离锚，隔离锚会切断该处的能量连接。这样一来，整条矩阵就被分割成若干个连续且相互隔绝的子段。只要每一个子段内部都是稳定的，整条矩阵就可以正常运转。
现在考古队想知道，最小的非负整数阈值 X 是多少，使得他们只需要插入不超过 K−1 个隔离锚（也就是把序列分成不超过 K 段），就能让所有子段都满足稳定条件
其实这道题就是简单的二分数组。
先说题：给一串数字，最多切成 k 段，每一段里面相邻两数之差不能超过 X，求能办到的最小 X。
能二分的原因：
X 越大越好办事，X 越小越难。有这种单调的规律，就适合二分猜答案。
check 函数干啥：
随便假设一个 X，从头到尾扫一遍数组。只要两个相邻数字差超过 X，这里就得切一刀。
最多 k 段，意思最多只能切 k-1 刀。
统计一共要切几刀，如果刀数没超上限，说明这个 X 够用；不够就说明 X 太小了。
二分怎么搜：
最低从 0 开始，最高直接取所有相邻差值里最大的（这个最大值一定能用，一刀不用切）。
算出中间值 mid，拿给 check 检验。
mid 可行：先保存这个答案，看看能不能找到更小的，把右边界往左挪。
mid 不行：X 太小，左边界往右挪，加大 X。
#include<bits/stdc++.h> using namespace std; typedef long long ll; // 数组a，存放序列，题目n最大2e5，全局数组防止栈溢出 ll a[200005]; ll n,k; // 二分check函数：判断阈值x是否可行 // 含义：最多切割k段，等价最多切 k-1 刀 bool check(int x){ int cnt=0; // cnt记录需要切割的次数 // 遍历相邻元素 for(int i=1;i+1<=n;i++){ // 相邻差值超过x，必须在这里切一刀 if(abs(a[i]-a[i+1])>x){ cnt++; } } // 需要切割次数 > k-1，说明x太小，不满足条件 if(cnt>k-1) return false; return true; } int main(){ cin>>n>>k; // n数组长度，k最多划分段数 ll r=0,l=0; // 二分左右边界 // 读入数组，下标从1开始 for(int i=1;i<=n;i++){ cin>>a[i]; } // 确定二分右边界r：所有相邻差值的最大值（x取这个值时不用切割，一定可行） for(int i=1;i+1<=n;i++) r=max(abs(a[i]-a[i+1]),r); int ans=0; // 二分模板：求满足条件的最小x（最小化最大值） while(l<=r){ int mid=(r+l)/2; if(check(mid)){ ans=mid; // mid可行，记录答案，尝试寻找更小的值 r=mid-1; } else { l=mid+1; // mid不可行，需要放大阈值 } } cout<<ans<<endl; return 0; }
