A - Appender水题题意说的是如果我们的单词以e结尾则在后面r否则则在最后面er#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string str; cin str; if (*(str.end() - 1) e) cout str r endl; else cout str er endl; return 0; }B - Wild Card水题题意说的给你两个长度一致的字符串S和T其中字符串T种有‘’这个可以被替换成任意的字母问你是否可以通过有限次的替换把T变成S可以的话输出Yes否则输出No。其实就是看S和T在相同的位置上是否匹配就可以了。#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; string s, t; cin s t; for (int i 0; i n; i) { if (t[i] ! s[i] t[i] ! *) { cout No endl; exit(0); } } cout Yes endl; return 0; }C - Third Largest Number题意给我们一个长度为N的整数序列A (A1, A2, …, AN)让我们去挑选出在序列A (A1, A2, …, Ak)取出第三大的整数本质维护一个长度为三的数组这个数组始终满足单调递减即可。但是为什么这去做是对的呢证明设当前数组为B(b1,b2,b3) B(b_1,b_2,b_3)B(b1​,b2​,b3​)并且始终满足b1≥b2≥b3 b_1\ge b_2\ge b_3b1​≥b2​≥b3​其中 (b1,b2,b3) 表示目前遇到的三个最大数。当加入新数字 (x) 时只需要将 (x) 插入到正确的位置并删除最小的数。为什么这样做是正确的因为原来没有被保存的数字都不大于 (b_3)。加入一个新数字后新的前三大数字只可能来自b1, b2, b3, x b_1,\ b_2,\ b_3,\ xb1​,b2​,b3​,x所以只要在这四个数字中保留最大的三个就能得到新的前三大数字。不断处理所有数字后数组中的第三个数字 (b_3) 就是整个序列中的第三大数字。因此我们只需要维护最大的三个数和每次新进来的那个数就可以#include bits/stdc.h using namespace std; #define endl \n int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; vectorint a(n 1); for (int i 0; i n; i) cin a[i]; int x a[0], y a[1], z a[2]; cout min({x, y, z}) endl; for (int i 3; i n; i) { int nn a[i]; int num[4] {x, y, z, nn}; sort(num, num 4, greaterint()); x num[0], y num[1], z num[2]; cout z endl; } return 0; }D - Automat哎依旧差一点第四题我的二分学的和够死一样题意在我们的Atcoder公司里面有两种售卖机一种卖甜点一种卖饮料每个公司的员工只有一元和K元的货币而我们的饮料售卖机只收K元货币甜点两种货币都收问我们如何花钱我们可以得到数量最多的甜品饮料数量思考刚开始我看样例我想到了肯定和这个饮料怎么去买有关系我第一种想法是饮料和甜点都排序然后按照最便宜的去一次购买然后很容易我就想到了反例。第二种想法两个分别排序然后先去购买甜点剩下的钱去购买饮料后面我自己也想到了反例自己pass了。然后我就开始陷入了长时间的思考最后我灵光乍现想到了我们先去枚举卖多少个饮料然后剩下的钱去全买甜点。但是至于为什么这个思路对我自己也不是很会证明因此一下的证明借助chatgpt为什么这样做可以保证最优核心思想枚举全局决策 局部贪心。假设最优方案购买了 (d) 个饮料。固定饮料数量 (d)如果要买 (d) 个饮料那么一定可以选择最便宜的 (d) 个饮料。因为如果方案中买了一个更贵的饮料却没买更便宜的饮料那么将其替换后消耗的 (K) 元钞票不会更多得到的 1 元找零不会更少。因此方案不会变差。甜品同理买完这 (d) 个饮料后如果还能买 © 个甜品那么这 © 个甜品也一定可以选择最便宜的 © 个。所以将甜品排序并维护前缀和就可以求出当前剩余金额下最多能买多少个甜品。为什么不会漏掉最优解真正的最优方案一定对应某个饮料数量d*。我们枚举所有可能的饮料数量d 0, 1, 2, ..., M因此一定会枚举到d d*对于固定的d*选择最便宜的d*个饮料不会比原方案更差再用剩余的钱购买尽可能多的最便宜甜品也不会比原方案更差。因此对所有d的情况取最大值就一定能够得到全局最优解。核心枚举最优解中的饮料数量再对固定数量下的商品选择进行贪心。#include bits/stdc.h using namespace std; #define ll long long int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, m, k, x, y, ans 0; cin n m k x y; vectorll a(n 1, 0), qa(n 1, 0); vectorll b(m 1, 0), qb1(m 1, 0), qb2(m 1, 0); for (ll i 1; i n; i) cin a[i]; for (ll i 1; i m; i) cin b[i]; sort(a.begin() 1, a.end()); sort(b.begin() 1, b.end()); for (int i 1; i n; i) qa[i] qa[i - 1] a[i]; for (int i 1; i m; i) { qb1[i] qb1[i - 1] b[i]; qb2[i] qb2[i - 1] ((b[i] - 1) / k 1); } for (ll i 0; i m; i) { if (y qb2[i]) break; ll ny y - qb2[i]; ll nx qb2[i] * k - qb1[i] x; ll nsum ny * k nx; ll ans2 i, ans1 0; auto pos upper_bound(qa.begin(), qa.end(), nsum); ans1 pos - qa.begin() - 1; ans max(ans, ans1 ans2); } cout ans endl; return 0; }E - Min-Max Swap题意给我们一个长度为N的排列P以及M个区间[L_i,R_i]。每次在当前排列的这个区间里找到最小值和最大值然后交换它们所在的位置。按顺序做完M次操作后输出最终的排列。1. 我是怎么想到线段树的如果每次都从头扫描[L_i,R_i]找最小值、最大值和它们的位置一次最坏要O(N)M次最坏就是O(NM)。N和M都可以到2×10^5这个做法太慢了。关键是每次操作之后排列会变化下一次查询必须基于更新后的排列。因此我需要同时支持查询一个区间里的最小值、最大值以及它们的位置交换后修改两个位置的值后续查询能立即看到修改后的值。这就是“区间查询 单点修改”的场景。差分适合处理预先给定的区间加减不能直接维护每次交换之后的区间最值这里用线段树更合适。2. 线段树的本质线段树把数组下标递归地分成左右两段每个节点负责一个区间并保存这段区间的统计信息。这题的统计信息是区间最小值及其位置 区间最大值及其位置如果一个区间被分成左右两段而且能用左右两段的信息快速算出整段的信息就可以把查询拆成若干个已经存好答案的小区间再把它们合并。单点修改时只需要沿着根节点到对应叶子的路径更新信息。所以线段树的关键是先想清楚两件事一个节点要保存什么信息两个子区间的信息怎么合并3.Node一个区间保存的信息只保存最小值和最大值还不够因为操作要交换的是它们所在的位置。所以每个节点保存两个数对mn {最小值, 最小值的位置} mx {最大值, 最大值的位置}structNode{pairint,intmn;pairint,intmx;};本题给的是排列数值互不相同。pair按“先比较值、再比较位置”的顺序比较因此min能选出最小值对应的数对max能选出最大值对应的数对。4.merge和pushup合并左右区间mergeNode接收左右子区间的信息返回合并后的信息合并后的 mn 左右两边中更小的 mn 合并后的 mx 左右两边中更大的 mxpushup(u)则把合并结果写回当前节点u。可以记成mergeNode算出父区间的信息 pushup把算出的信息保存到 tr[u]NodemergeNode(constNodeleft,constNoderight){Node res;res.mnmin(left.mn,right.mn);res.mxmax(left.mx,right.mx);returnres;}voidpushup(intu){tr[u]mergeNode(tr[u*2],tr[u*21]);}5.build根据初始排列建树当l r时当前区间只有一个位置所以它的最小值和最大值都是p[l]。否则先建左右子树再用pushup合并出当前节点的信息。build(u, l, r) ├── l r初始化叶子节点 └── 否则建左右子树再 pushup(u)6.query查询[L,R]的最值和位置这里要区分两组下标[l,r]当前线段树节点负责的区间 [L,R]这次要查询的区间查询时分三种情况当前节点的区间完全落在查询范围内直接返回tr[u]查询范围完全在左边或右边只递归对应的子树查询范围跨过mid左右都查再用mergeNode合并。完整覆盖时直接返回已经保存的信息不必继续访问区间中的每个位置这正是区间查询能快起来的原因。7.update单点修改update的参数含义是u 当前线段树节点编号 [l,r] 当前节点负责的区间 pos 要修改的数组下标 value 这个位置的新值递归找到pos对应的叶子并更新它然后沿途调用pushup重新计算祖先节点的区间最值。8. 主流程每次操作按这个顺序做build(1, 1, n)根据初始排列建树query(1, 1, n, L, R)得到当前区间的最小值位置和最大值位置在原数组p中交换这两个位置对这两个位置分别调用update让线段树同步到最新排列所有操作完成后输出p。注意只交换数组p不够线段树里还存着旧信息所以交换后必须更新这两个位置。9. 复杂度建树O(N)每次区间查询O(log N)每次操作有两次单点更新O(log N)总时间复杂度O(N M log N)空间复杂度O(N)线段树数组开约4N个节点完整代码#includebits/stdc.husingnamespacestd;constintN2e510;structNode{pairint,intmn;pairint,intmx;};Node tr[N*4];intp[N];NodemergeNode(constNodeleft,constNoderight){Node res;res.mnmin(left.mn,right.mn);res.mxmax(left.mx,right.mx);returnres;}voidpushup(intu){tr[u]mergeNode(tr[u*2],tr[u*21]);}voidbuild(intu,intl,intr){if(lr){tr[u].mn{p[l],l};tr[u].mx{p[l],l};return;}intmid(lr)/2;build(u*2,l,mid);build(u*21,mid1,r);pushup(u);}Nodequery(intu,intl,intr,intL,intR){if(LlrR)returntr[u];intmid(lr)/2;if(Rmid)returnquery(u*2,l,mid,L,R);if(Lmid)returnquery(u*21,mid1,r,L,R);Node leftquery(u*2,l,mid,L,R);Node rightquery(u*21,mid1,r,L,R);returnmergeNode(left,right);}voidupdate(intu,intl,intr,intpos,intvalue){if(lr){tr[u].mn{value,pos};tr[u].mx{value,pos};return;}intmid(lr)/2;if(posmid)update(u*2,l,mid,pos,value);elseupdate(u*21,mid1,r,pos,value);pushup(u);}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;for(inti1;in;i)cinp[i];build(1,1,n);for(inti1;im;i){intL,R;cinLR;Node resquery(1,1,n,L,R);intmnpres.mn.second;intmxpres.mx.second;swap(p[mnp],p[mxp]);update(1,1,n,mnp,p[mnp]);update(1,1,n,mxp,p[mxp]);}for(inti1;in;i)coutp[i](in?\n: );return0;}