普及-

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}$。 ...

CF2173B Niko’s Tactical Cards 思路 简单 DP，只需要记录到每一步操作的最小值和最大值，再进行更新就行了。 最大值只会由最大值减 $a_i$ 或 $b_i$ 减最小值得到，最小值只会由最小值减 $a_i$ 或 $b_i$ 减最大值得到。 再分别对这两对值取对应的最值即可。 最后输出最后一位的最大值。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243#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...

CF2170B Addition on a Segment 思路 正难则反，考虑从给出序列每次把一段区间减 $1$ 直到回到全 $0$。 首先从大到小排序。因为若乱序操作很可能会造成中间无法操作而两头还有剩余值的情况，非常浪费。 我们只在第一次操作时考虑最长，后面每次都使 $l=r$，若操作次数多出，则将某几次合并成一次即可。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344#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++)#defin...

CF2157B Expansion Plan 2 题意 从原点 $(0,0)$ 这个正方形开始，有两种扩展，分为 $4,8$，分别代表向四个方向和八个方向扩展一个正方形。 求点 $(x,y)$ 是否被包含在扩展图形内部。 思路 观察样例发现，不论如何扩展，最后的区域均为一个大正方形的四角分别往内凹进一个等腰直角三角形。 又发现四个象限的本质相同，可通过旋转使它们重合。 简单推理可得等腰直角三角形的边长为字符串中 $4$ 的出现次数。 综上，我们可以对每个点的 $x$ 和 $y$ 取一次绝对值，使这个点变成第一象限点，再根据它的坐标模拟即可。 具体的： 若 $x>n$ 或 $y>n$，则单个坐标轴已经超出上限，显然不在扩展图形内部。 若 $x,y$ 之和比 $8$ 的出现次数加上总括展次数还大，则不在扩展图形内部。 其余情况均在扩展图形内部。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<...

P2651 添加括号III 思路 思路较为简单。因为要使得结果为整数，则最优方案是只将 $a_2$ 设为分母，其它均为分子。这里不做过多赘述，详见其他题解。 具体实现 $a_i$ 的范围非常大，显然不能直接累乘（除非你写高精度）。 注意到其它所有题解在约分时均使用了 $\gcd(a,b)$ 来约分，而它的最坏时间复杂度为 $O(\log \min(a,b))$。 这并不优秀，它使得整体的时间复杂度最坏为 $O(T\cdot n \cdot \log\min(a,b))$ 而我们有一种更优的做法，时间复杂度为 $O(T\cdot n)$。 原理很简单，在每一次累乘后直接将乘积对 $a_2$ 取模即可。 证明 这题的结果由 $(\prod_{i=3}^{n} a_i)\cdot a_1$ 能否整除 $a_2$ 决定。 若我们在每一步后对乘积取模： 设当前乘积为 $m$，要乘 $a_t$，则分配率易证 $m\cdot a_t\equiv m\cdot (a_t\bmod a_2) \pmod {a_2}$。 同理对 $m$ 取模同样不影响结果。 所以我们在过程中可以任意取模，比每次约分...

思路 因为从 $x$ 到 $y$ 的时间与从 $x$ 到 $z$ 再到 $y$ 的时间相同 $(x \le z \le y)$ ; 而如果直接从 $x$ 到 $y$ 的话，有一段时间还在比 $z$ 低的 $x$ ，显然劣于从 $x$ 到 $z$ 再到 $y$ ; 所以直接从当前塔一路向更高的塔走，直到某一刻水升上来所需时间小于传送所需时间，就会被水淹没。 实现 将塔的高度排序，把比初始点还低的塔排除掉，再遍历一遍即可。 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>#define int long long#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) for(int i=s;i&g...