普及-

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...

CF2183C War Strategy CF2183C Generals.io 思路 显然最后的局面一定是一段包含 $k$ 的连续区间。 若选择向离 $k$ 更远的地方扩展而放弃离 $k$ 更近的某个兵营，则显然要花费更多的时间，一定更劣。 假设我们要向左扩张 $l$ 个兵营，向右扩张 $r$ 个兵营。 则 $l\le k-1,r\le n-k$，否则会超出边界。 而扩张到这样局面的时间最小为 $l+r+\max(l,r)-1$。 证明一定能取到这个时间 我们先等待直到 $k$ 中有 $\max(l,r)$ 个士兵，耗费 $\max(l,r)-1$ 天； 然后花费 $\max(l,r)$ 天直接向外扩展到极限距离； 此时 $k$ 中又会有 $\ge\min(l,r)$ 个士兵； 再花费 $\min(l,r)$ 的时间向外扩展到极限距离。 将这些时间相加即得到 $l+r+\max(l,r)-1$。 这已经是最优方案了，无法取到更快的时间，总会在某几步造成天数的空闲（等待兵力或走重复路程）。 实现 两边拓展的距离在都可以扩展的情况下最多相差 $1$，所以我们每次都向外将可扩展的边增...

AT_abc439_c [ABC439C] 2026 思路 exactly one pair 注意到是“恰好一对”。 枚举 $x,y$，将所有合法的 $x^2+y^2$ 加入一个数组内。 这样的数最多有 $n$ 个。 考虑对这个数组排序。 在排序后的数组内统计答案，若一个数既不与其前一个相等，也不与其后一个相等，因为数组是有序的，则它对应的 $x,y$ 一定只有一对。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#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--)#defin...

CF2175B XOR Array 思路 设前缀异或数组为 $pre$，其中 $pre_0=0$，$pre_i= a_1\oplus a_2\oplus\dots\oplus a_i$（$\oplus$ 表示异或）。 根据异或的性质，子数组 $a_x\dots a_y$ 的异或和可以表示为：$f(x,y)=pre_y\oplus pre_{x-1}$。 要求 $f(l,r)=0$，等价于 $pre_r=pre_{l-1}$。 要求其余子数组异或和非 $0$，等价于除 $(x,y)=(l,r)$ 外，任意 $i\neq j$ 都有 $pre_i\neq pre_j$。 初始化 $pre_0=0$，$pre_i=i$（$1\le i\le n$）。此时 $pre$ 数组元素互不相同，保证所有子数组异或和非 $0$。 调整 $pre_r=pre_{l-1}$，满足 $f(l,r)=0$。由于 $l \le r$，$pre_{l-1}$ 的值不会与 $pre_{1}\dots pre_{r-1}$ 重复，因此调整后仅存在一对相等的前缀值 $pre_{r}$ 和 $pre_{l-1}$。 ...