普及+/提高

CF2190B1 Sub-RBS (Easy Version) 思路 有一个很简单的思路。 先说结论：如果前 $n\div2-1$ 个中存在右括号，答案是 $n-2$，否则答案是 $-1$。 证明 以下三个命题相互等价： 存在长度为 $l-2$ 的更好子序列； 存在任意长度的更好子序列； $s$ 的第一个右括号后至少有 $2$ 个左括号。 等价性简化证明 $1$ 到 $2$（显然成立） 若存在长度为 $l-2$ 的更好子序列，该子序列本身就是“任意长度的更好子序列”，直接得证。 $2$ 到 $3$ 设 $t$ 是更好的子序列，第一个差异位为 $i$，满足 s[i]==')' 和 t[i]=='('； 差异导致 $t$ 前缀 $0$ 到 $i$ 的平衡度（左括号数 - 右括号数）比 $s$ 多 $2$； $t$ 是合法 RBS，需后续右括号抵消该额外平衡度，且这些右括号均来自 $s$； $s$ 是合法 RBS（最终平衡度为 $0$），故 $s_i$（第一个右括号）后必须有至少 $2$ 个左括号，抵消多余平衡度，得证。 $3$ 到 $1$ 定位关键位置：$pos...

AT_arc212_a [ARC212A] Four TSP 思路 考虑如何构造出一个经过 $4$ 个点的环。 定义不存在任何端点为同一个点的两条边是一组对边。 画图后，我们发现，只有任意两组对边才可以组成一个符合题目要求的环。 考虑枚举这三组对边分别的长度和。 发现第三组对边的长度和可以由前两组求得，并且必定存在合法的六条边的长度分配。 则枚举两组对边长度和 $a,b$，第三组对边长度和为 $c$。 而具体到每一条边时，已知和为 $p$，则长度分配方法有 $p-1$ 种。 最后将题目转化为这个式子（设 $c=k-a-b$）： $$\sum_{a=1}^{k-2}\sum_{b=1}^{k-1-a}(k-\max(a,b,c))\times(a-1)\times(b-1)\times(c-1)$$ 直接按照这个式子实现即可。 要注意 $a,b,c$ 都是正整数，注意判边界条件。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++....

AT_arc212_b [ARC212B] Stones on Grid 思路 要使得所有第 $i$ 行和第 $i$ 列的棋子数均相等，则需要使选的所有 $x_j=i$ 和 $y_j=i$ 的数量相等。 那这不就是找环吗？ 形式化题面：如何找到含有给定边 $(x_1,y_1)$ 的最小环。 这就很简单了，跑出 $y_1$ 到所有点的最短路 $dis$，再枚举所有边，若对应的 $y_i=x_1$ ，则答案和 $c_1+dis_{x_i}+c_i$ 取最小值。 对上面的式子的解释：从 $x_1$ 出发先到 $y_1$，然后从 $y_1$ 出发到某个点 $x_i$，最后从 $x_i$ 出发回到 $y_i$，也就是 $x_1$。 没有负边权，可以用 Dijkstra 跑。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include<bits/s...

AT_abc439_f AT_abc439_f [ABC439F] Beautiful Kadomatsu 思路 省流：线段树。 首先我们发现，若按照 $(i,a_i)$ 的坐标在平面直角坐标系中建图，并且将每个点与它前面和后面（如果存在的话）的点相连，那么趋势一定呈一个波浪状。 又发现题目中要求的两种点就是波浪的波峰和波谷。 显然这两种点的数量最多相差 $1$，且差值取决于开头和结尾的趋势。 若要使得波峰数量比波谷数量多，则开头必定为增加，而结尾必定为减少。 考虑对正序对及逆序对计数。 显然可以用线段树求出正、逆序对的数量，表示为 $smr$ 和 $bgr$。 然后由于 $l,r,l<r$ 中间怎么选点不影响，则每个正、逆序对之间的点可任意选或不选，方案数为 $2^{r-l-1}$ 次。 而当 $l=r$ 时，中间无点可选。 那所有贡献则为 $\sum_{i=1}^n smr_i\cdot bgr_i$ 加上 $\sum_{i=1}^n\sum_{j=i+1}^n smr_i\cdot bgr_j\cdot 2^{j-i-1}$。 第一部分可以 $O(n)$ 地求出，直接...

CF2182E New Year’s Gifts 思路 题目中提到必须给 $i$ 号朋友买价值为 $y_i$ 的礼物，则这部分开销是不可避免的，直接从初始资金中减去。 此时对于朋友 $i$，他的贡献可以被形式化地表达为： 消耗 $\Delta=z_i-y_i$ 的剩余金钱产生 $1$ 的贡献。 消耗一个至少为 $x_i$ 美观度的礼盒产生 $1$ 的贡献。 且这两种操作不可重复计算。 我们可以贪心的将所有 $\Delta$ 按照大小排序，从小到大遍历所有礼盒，对于每个礼盒，找到它可以产生贡献的最大 $\Delta$，再使用这个礼盒，删除掉对应的 $\Delta$。 看到这里，我们需要一个可以支持插入、排序和删除的数据结构。 set 就非常合适。 但注意到这里面可能会出现相同元素，所以使用类似的 multiset。 还有一些细节，见代码中注释。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162...

CF2182D Christmas Tree Decoration 思路 手玩样例后发现这个拿装饰品的机制和班上轮换做清洁有点像啊。 不难发现在合法情况下，最少的拿取次数最多比最多的拿取次数少 $1$ 次。 那我们先判断是否合法，方法如下： 找到对应装饰品最多的一个人，设他的对应盒子中有 $mx$ 个装饰品。 将其他人的对应装饰品补足至 $mx-1$，不够的部分从 $p_0$ 中减掉。若在某一步 $p_0$ 不够了，则方案数为 $0$。 然后此时一定存在合法情况，我们考虑如何计算合法排列数。 首先这个排列中每个人的挂装饰品次数应当形如 $mx,\cdots,mx,mx-1,\cdots,mx-1$。 先扫描一遍整个数组，找到 $mx$ 有多少个，设它有 $a$ 个，则 $mx-1$ 有 $n-a$ 个。 此时分类讨论： 若 $p_0\le n-a$，则 $p_0$ 无法将所有 $mx-1$ 补到 $mx$，那么在补足后将会有 $a+p_0$ 个 $mx$，$n-a-p_0$ 个 $mx-1$，则答案为 $C_{n-a}^{p_0}\cdot A_{a+p_0}^{a+p_0...

CF2170D Almost Roman 思路 首先我们对每个数字进行分析： $I$ 权值最大为 $1$，最小为 $-1$， $V$ 权值为 $5$， $X$ 权值为 $10$。 注意到无论在何种情况下，$X$ 的权值和造成的影响一定比 $V$ 多 $5$。 可以把原字符串中的所有 $X$ 替换成 $V$，每替换一次就给总权值加 $5$。 又发现对于任意位置，填 $I$ 一定比填另外两个更优。 所以我们先将所有问号的位置都填上 $I$，如果不够就再替换成另外两个。 对于每一次替换，有以下三种情况： 增加了权值为 $-1$ 的 $I$ 的个数， 权值为 $-1$ 的 $I$ 的个数不变， 减少了权值为 $-1$ 的 $I$ 的个数。 显然我们应先替换第一种，再替换第二种，最后选第三种。 那代码就很好实现了。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707...