0103abc 的网站

有两个端点比较难受，所以考虑转化问题，找到最小的 $m$ 使得存在一个起点 $t\in [0,m]$ 使得每一步 $+ai$ 或 $p-ai$ 后值都在 $[0,m]$ 范围内。 显然 $m$ 是有单调性的，所以考虑二分 $m$ 的值，判定是否合法容易简单想到 $O(nm)$ 暴力背包...

好困难/ll 套路的把左括号看作是 $1$，右括号看作是 $-1$。则显然 $i$ 位置的前缀是 RBS 的充要条件是： 不存在 $1\le j\le i$ 满足 $j$ 位置的前缀和 $<0$。 $i$ 位置的前缀和为 $0$。 考虑直接状压 dp，设 $f_{i,j}$ 表示当前处理了 $i$...

先考虑 D1 怎么做。容易想到记 $buci$ 表示 $a$ 序列中有多少个数是 $i$ 的倍数（可以写一个埃筛 $O(n\log n)$ 求出），然后记 $fi$ 表示当前序列的 $\gcd$ 为 $i$，所有前缀的 $\gcd$ 的和最...

感觉比较像 sale（？但是要简单一些 可以证明对于任意一个排列都最多只需要三次操作使得排列变得满足条件。因此考虑分别计数需要 $0,1,2,3$ 次操作可以排序的排列数量： 需要 $0$ 次操作的排列数量：显然答案就是 $1$。 需要 $1$ 次操作的排列数量：显然这次操作只能把前 $2n$...

容易想到设 $f_{k,i,j}$ 表示当前处理了前 $k$ 行的染色情况，第 $k$ 行恰好染色了 $[i,j]$ 区间内的所有格子，方案数是多少。然后注意到这个东西的转移可以用矩阵乘法优化，做到 $O(m^6\log n)$ 时间复杂度求解。...

未看题解完成，用时 34min 7s。 对一个位置而言赋值操作肯定最多进行一次，因此考虑直接贪心。注意到一定存在一个最优策略满足对每个位置，其执行的操作的顺序都是（赋值）-（加法）-（乘法），括号代表一个操作可有可无。证明可以简单 Exchange-Argument Trick 处理。...

未看题解完成，用时 26min 18s。 有一个简单的贪心策略是直接把每个位置都拆开得到 $|s|$ 个长度为 $1$ 的数字然后直接加起来，但是这个贪心显然是错的。 考虑直接错上加错，以一定概率把两个长度为 $1$ 的数字合并起来（实测概率取 $\frac1{15}$...

注意到对于 $\gcd$ 而言，有这样的性质：若 $a>b$，则 $\gcd(a,b)\le a-b$。因此可以证明存在最优策略使得有一组内只有一个值相同的数。 还可以发现护结论：这个数在所有数字中要么是值最大的元素，要么是值第二大的元素。证明考虑反证，记选的数是 $x$，严格前两大的数分别为...

比较套路的题，考虑先给每个颜色随机赋一个权值，然后对每次询问二分出 $k$ 判定当前的 $k$ 是否合法，此时考虑直接 SUM-HASH，建立树上主席树然后差分判定 $[1,k]$ 区间上主席树差分出的和是否相同即可。 总时间复杂度为 $O(n\log^2n)$ 可以通过该题，有单 $\log$...

注意到 $k\in\lbrace 1,2\rbrace$（现在你已经做完了这个题最难的地方），因此猜测是直接分两类讨论。 $k=1$ 可以把问题转化为：找到最小的 $x$ 使得 $\sum\limits{i=1}^n|ai-x|+\sum\limits{i=1}^n|bi-x|$...