普及-

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