A、能量任务链接https://ac.nowcoder.com/acm/contest/138881/A来源牛客网有 n 个任务。执行第 i个任务前你的当前能量必须不少于 hi任务完成后能量变化 di即变为当前能量di每个任务必须且只能执行一次你可以自由决定执行顺序。所有时刻能量都不能为负。已知 hidi≥0因此只要执行前满足门槛执行后就不会立刻变成负数。求完成所有任务所需的最小初始能量。这道题我觉得难点主要在排序上还有就是找一个规律我刚开始认为的是对于di0而言di越大越先走这个门但是不对后来得出结论应该是hidi越大越先走还有排序上普通的sort只能进行升序排序所以我们要找其他方法现在有两种比较常用的排序首先是sort(fu.begin(),fu.end(),[](auto a,auto b){ ll saa.firsta.second; ll sbb.firstb.second; return sasb; });这个排序方法我第一次见但是很实用就是在最基础的sort后面加上[](auto a,auto b)后面再跟上return 即可。还有一种方法就是用结构体排序bool cmp(node a,node b) { if(a.d0||b.d0) { if(a.db.d)return a.hb.h; else if(a.d0b.d0) { int ca.ha.d; int db.hb.d; return cd; } else return a.db.d; } return a.hb.h; }这个排序规则我比起前一个更好理解但是写起来比较复杂是最基础的排序。看代码#includebits/stdc.h using namespace std; typedef long long ll; int main(){ int n; cinn; ll h,d; // res存放d0 增益任务做完能量上升/不变 vectorpairll,llres; // fu存放d0 亏损任务做完能量下降 vectorpairll,llfu; for(int i0;in;i){ cinhd; if(d0) { res.emplace_back(h,d); } else{ fu.emplace_back(h,d); } } // 增益任务 pair默认先按first(h)升序排序正好符合要求h从小到大 sort(res.begin(),res.end()); // 亏损任务排序规则shd 从大到小 sort(fu.begin(),fu.end(),[](auto a,auto b){ ll saa.firsta.second; ll sbb.firstb.second; return sasb; }); ll ans0; // ans最终需要的最小初始能量 ll r0; // r模拟当前拥有的能量初始假定为0 // 先执行所有增益任务 for(auto x:res){ ll hi x.first; ll di x.second; // 当前能量不够开启任务需要补足初始能量缺口 if(rhi){ ans hi - r; r hi; // 补足后能量刚好到达门槛hi } r di; // 完成任务能量变化 } // 再执行所有亏损任务 for(auto x:fu){ ll hi x.first; ll di x.second; if(rhi){ ans hi - r; r hi; } r di; } coutansendl; 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 的个数区间[l1 ~ 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算出当前状态二元组(d1c0-c1, d2c1-c2)哈希表记录每个二元组第一次出现的位置存第一次越早区间越长如果状态曾经出现过计算区间长度更新最大值如果没出现把当前状态和下标存进哈希。下标体系虚拟初始状态还没读任何字符c0c1c20状态 (0,0)逻辑下标 0字符串原生下标 i0 开始处理完 s [i] 之后对应前缀逻辑下标 i1长度公式旧逻辑下标 pos当前逻辑下标 i1子串长度 (i1) - pos i-pos1初始化不能忘mp[{0,0}] 0如果不写从字符串开头开始的合法子串识别不出来直接错误。易错点二元组两个差值千万别算错d1c0-c1d2c1-c2不能乱换顺序哈希只存第一次出现的下标后来遇到相同状态不能覆盖下标体系一套用到底不要混用两套下标长度公式不要随手乱改1 / -1map 复杂度 O (nlogn)极限大数据可能超时想要更快可以把 pair 编码成 long long 换 unordered_map。代码解释#includebits/stdc.h using namespace std; typedef long long ll; int main(){ ll n; // n 代表字符串长度 cinn; // 读取字符串长度 string s; cins; // 读取由0、1、2构成的字符串 int ans0; // ans保存最长平衡子串长度初始0无合法子串输出0 // map键是二元组(d1,d2)值是该状态第一次对应的前缀下标 mappairint,int,intmp; mp[{0,0}]0; // 初始化空前缀还没读取任何字符c0c1c20下标记作0 int c00,c10,c20; // c00的前缀总数c11的前缀总数c22的前缀总数 // i 是字符串s的下标从0到n-1原生0下标遍历字符串 for(int i0;in;i){ // 根据当前字符对应计数1 if(s[i]0) c0; else if(s[i]1) c1; else c2; int d1c0-c1; // 差值10的总数 − 1的总数 int d2c1-c2; // 差值21的总数 − 2的总数 // 二元组 (d1,d2) 相同 → 中间区间0、1、2数量相等子串合法 if(mp.count({d1,d2})){ // 这个状态之前出现过 int posmp[{d1,d2}]; // 取出第一次出现时的前缀下标 ansmax(ans,i-pos1);// 更新最长长度 } else{ // 首次出现存入mapi1作为前缀逻辑下标对齐最初mp[{0,0}]0的体系 mp[{d1,d2}]i1; } } coutansendl; // 输出最长平衡子串长度 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)posL-1变形(pre[pos] (pre[R]-S) mod m)遍历每个右端点 R算出需要匹配的余数 tar看左边有没有 pos 满足余数相等。想要删除区间最短pos 要尽量靠近 R所以每次循环结束直接更新 map 存当前余数的最新下标不要只存第一次。限制条件删除长度不能等于 n不能把所有数字删光。最后没找到合法方案输出-1.现在我们来看代码#includebits/stdc.h using namespace std; typedef long long ll; ll a[200009]; //存储原始数组 ll n,m; //n数组长度m模数 ll pre[200009]; //前缀和模m数组 int main(){ cinnm; ll sum0; pre[0]0; //前0项前缀模等于0 for(int i1;in;i){ cina[i]; suma[i]; //累加求数组全部总和 pre[i](pre[i-1]a[i])%m;//计算前缀和对m取模 } ll mod_sumsum%m; //总和取模m mapll,llmp; //key:余数 value:余数最近出现的下标 mp[0]0; //初始化pre[0]0下标0 int mx-1; //答案初始-1代表无解 for(int r1;rn;r){ //枚举删除区间右端点r ll t(pre[r]-mod_sum)%m; //计算想要匹配的目标余数 if(t0) tm; //C负数取模修复转为0~m-1 if(mp.count(t)){ //左边存在该余数的位置 int lenr-mp[t]; //得到删除区间的长度 if(lenn){ //不能把全部元素删掉 mxmax(mx,(int)(n-len)); //更新最大保留元素数量 } } mp[pre[r]]r; //更新保存当前余数最近的下标覆盖旧值 } coutmxendl; //输出答案 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#includebits/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(x2) return true; // 2是质数 // 从2枚举到sqrt(x)尝试寻找因子 for(int i2;isqrt(x);i){ if(x%i0) return false; // 能整除不是质数 } return true; // 找不到因子是质数 } // step当前正在填充排列的第 step 个位置 void dfs(int step){ // 递归边界所有位置全部填完一共n个位置step走到n1代表填充完毕 if(stepn1){ // 输出完整排列 for(int i1;in;i){ coutans[i] ; } coutendl; return ; } // 尝试枚举可以放在当前位置的数字 1~n for(int i1;in;i){ if(b[i]1) continue; // 数字i已经用过跳过 // step1第一个位置没有前一个数字直接合法 // 不是第一位前一个数字 ans[step-1] 和当前i相加必须是质数 if(step1||check(ans[step-1]i)){ ans[step]i; // 当前位置填入数字i } else continue; // 和前数之和不是质数不能选这个i b[i]1; // 标记数字i已经被占用 dfs(step1); // 递归填充下一个位置 b[i]0; // 回溯取消标记释放数字i } } int main(){ cinn; // 输入排列长度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。#includebits/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 cnt0; // cnt记录需要切割的次数 // 遍历相邻元素 for(int i1;i1n;i){ // 相邻差值超过x必须在这里切一刀 if(abs(a[i]-a[i1])x){ cnt; } } // 需要切割次数 k-1说明x太小不满足条件 if(cntk-1) return false; return true; } int main(){ cinnk; // n数组长度k最多划分段数 ll r0,l0; // 二分左右边界 // 读入数组下标从1开始 for(int i1;in;i){ cina[i]; } // 确定二分右边界r所有相邻差值的最大值x取这个值时不用切割一定可行 for(int i1;i1n;i) rmax(abs(a[i]-a[i1]),r); int ans0; // 二分模板求满足条件的最小x最小化最大值 while(lr){ int mid(rl)/2; if(check(mid)){ ansmid; // mid可行记录答案尝试寻找更小的值 rmid-1; } else { lmid1; // mid不可行需要放大阈值 } } coutansendl; return 0; }