普及-

CF2231B Another Sorting Problem 思路 思维好题。 首先题目允许最多一次操作，选择一个正整数 $k$ 和一个子序列，将该子序列的所有元素加上 $k$。问能否使数组变为非递减序列。 如果开始的序列就满足条件，则直接特判掉。 由于只能加不能减，且只能操作一次，这意味着如果某个位置 $i$ 需要增加（因为 $a_i>a_{i+1}$），那么 $i$ 及其之后的某些元素一定被选中。 这就相当于把整个数组划分为两个互补的子序列，且两个子序列内都是有序的（若无序，同时加 $k$ 还是无序）。 那么我们首先找出所有逆序对位置，这些逆序对的前一个数一定被选中，后一个数一定不选中，不然就会导致无序。 如果存在连续的逆序对（如位置 $i$ 和 $i+1$ 都是某逆序对的前一个数），则不可能，因为同一个位置不可能既被选中又未被选中。 在这一步中，我们可以计算出 $k$ 的最小上界 $L$。 再按照选中和未选中划分数组，找到从每个选中段到未选中段的最大差值，这决定了 $k$ 的最大下界 $K$。 然后判断 $K\le L$ 是否成立即可得出有没有合法 $k$。 代码 ...

CF2225B Alternating String 简化题意 给定一段 01 数组 $a$。 选择一段区间 $[l,r]$，将其翻转，可以将其取反，问能否实现一次操作后数组中每个 $a_i\ne a_{i-1}$。 思路 最后若能得到合法数组，有两种情况： $a_i=i \bmod 2$； $a_i=1-i\bmod 2$。 那么我们只需要将初始值全部取反，就可以使第二种与第一种处理方法相同。 而要翻转的区间端点一定是在原数组中不合法的点。 考虑若翻转多奇数个合法点，则可以通过取反操作使其与翻转不合法点等价。 而多翻转偶数个合法点本身就与翻转不合法点等价。 所以遍历一遍整个数组，记录最左和最右的不合法点 $l,r$。 然后若 $[l,r]$ 内存在两个相邻点相等，那我也没招了，不管对整个区间取几次反都不能成功，这种情况直接不成立，排除掉。 其他情况一定可以通过取反成立，不再赘述。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

CF2220B OIE Excursion 思路 首先每个时间点都可以在原地停留，向左或向右。 先考虑 $m=2$ 的情况。 对于 $i$ 号位置，若可以到达，则可能可以通过一些调整使其在除 $a_i$ 之外的其他时间到达。 考虑什么时候做不到调整，即 $a_i=a_{i+1}$ 时，不论怎样通过这一段都需要至少 $3$ 秒的空档期，无法通过。 那么对这个东西进行推广，若有 $i\in[l,r]$，所有 $a_i$ 相等，则至少要 $(r-l+1)+1$ 的时间才可以通过，而我们拥有 $m$ 秒的时间，进行比大小即可。 所以线性地扫描一遍，判断每段连续的区间长度加一与 $m$ 的大小关系即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>#define fir first#define sec second #define int long ...

CF2204B Right Maximum 思路 注意到每次都会取出最右边的 $\max$ 值，所以我们将原数组中的每个位置改为以值为第一关键字，位置为第二关键字，从大到小排序。 每次遍历到的值若在现在删除的最左边的值右边，直接跳过，否则它成为最左边且被删除的值，将删除次数加一。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define per(i,s,e) f...

CF2204C Spring 思路 推式子题，显然利用容斥。 以下按照名字首字母简称题中的三个人。 我们发现每天的取水人共有 $7$ 种情况。 A B C AB AC BC ABC 而这就是一个很简单的容斥。 我们画一个图： 对于某人独有的部分，此人会获得 $6$ 单位的水； 对于两人共有的部分，两人都会获得 $3$ 单位的水； 对于三人共有的部分，三人都会获得 $2$ 单位的水。 所以对于 A，她能获得的水量是 $A\times6+AB\times3+AC\times3+ABC\times2$。 但是这样还是太难算了，考虑简化。 我们将某种取水的情况并入它的所有子集，此时，A 代表一整个大圆，AB 代表原来的 AB+ABC，以此类推。 此时，对于 A，她能获得的水量是 $A-AB\times3-AC\times3+ABC\times 2$。 因为 A 导致多算了六次 AB 和 AC 以及 ABC，而 AB 和 AC 只需要三次，所以减掉三次，然后又导致少算了 $3\times2=6$ 次 ABC，而 ABC 需要两次，所以还要算 $-6+6+2=2$ 次。 B 和 C 的...

P15400 [NOISG 2026 Prelim] Hungry Cats 依旧水题解。 思路 题面过于诡异，此后的描述中用单位代指猫，大小代指快乐值。 先将所有单位按照快乐值大小排序。 首先注意到每个单位只能吞一次，所以第二大的只能被最大的吞掉。 就算有和它一样大的，在吞掉更小的之后比它更大，此时也无法再次吞单位，故无法吞掉它。 所以以此类推，所有单位都只能被比它大的第一个单位吞掉。 故从小到大枚举，从第三小的开始枚举，如果有两个单位相差一（吞前一个后相等）或相等（吞前一个后更大），则输出 NO 并 return 0;，否则输出 YES。 对于第一小的，它不会吞任何其它单位，故只判断最小的两个是否相等。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii p...

CF2208B Cyclists 思路 首先考虑若要选的那个胜利条件最开始就在最后面，该怎么选。 显然是找前面 $k-1$ 个花费最大的卡牌，将它们保留，然后将其它的卡牌挪到最后面，最后胜利条件就会位于第 $k$ 个位置，直接挪动它。 此时就回到了跟原情况等价的一种局面，可以花费一定的代价稳定地获取一次胜利条件，用剩余的花费除以一定的代价得到答案。 那如果胜利条件最开始不在最后面呢？ 那就想办法将它挪动到最后面。 若开始时它在前 $k$ 个，直接挪动。 否则，留下在它前面且最大的 $k-1$ 个，挪动其它卡牌，再挪动胜利条件。 最后所有情况都到了它开始就在最后的局面，按照前面提到的方法计算次数即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include<bits/stdc++.h>#define fir first#define sec second #define ...

CF2194B Offshores 思路 很简单的题，没想明白为什么有人切了 CD 没切。 问了一下 @WBJ0429 为什么做那么慢，得知他以为可以进行多次转移，把某个银行中剩余的钱作为“补给”，在最后 $10$ 分钟才发现。 实则这是错的。 ▶ [证伪] 设有银行 $A,B,C$，我们的最终目标是 $C$。 有两种方法（从 $A$ 到 $B$ 和从 $B$ 到 $A$ 只是交换编号，不多赘述），分别是 $A\to B\to C$ 和 $A\to C,B\to C$。 显然 $C$ 中有多少钱不影响最终的结果相对大小。 则第一种转移情况会使得在 $B\to C$ 这一步时转移的钱数变少，因为 $A\to B$ 的一部分再转移一次显然不到 $cnt_a\times y$，而 $B$ 中的剩余部分又不足以再转移一次。 故从每个银行出发只转移一次一定优于转移多次。 我们知道若要使得某银行中的存款数达到最大，则需要把其他银行中所有能转...

AT_abc444_d [ABC444D] Many Repunit Sum 思路 注意到每一步操作 $i$ 都是把 $1$ 到 $a_i$ 的数位的数值加 $1$ 显然类似高精度的实现。 然而直接枚举不行，因为只有一次查询，所以考虑支持区间修改的差分。 最后做一次前缀和，再处理一次进位即可。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define...

CF2191B MEX Reordering 思路 将数组从小到大排序，这样前面一定会出现 $a$ 个 $0$，然后在 $a$ 之后的后缀数组的 MEX 值一定是 $0$，不会与前缀数组相同，而在 $a$ 及 $a$ 之前的前缀数组的 MEX 值一定是 $1$，只要后面有至少一个 $1$ 出现就行了。 而如果没有任何一个 $1$，且存在两个及以上的 $0$，那一定有出现以某点为分界的前缀和后缀 MEX 值都为 $1$，一定不行；若全局没有出现 $0$，则所有前缀和后缀的 MEX 值皆为 $0$，也一定不行。 所以直接按照上面判断就行了。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(i...