普及+/提高

P12675 「LAOI-8」Boundary 思路 首先考虑如何使得整个区间变为 $-10^9$，显然一定有一次修改左端点为 $1$，有一次修改右端点为 $n$，因为无法通过增加 $1$ 使得某个数变为一个极小值（当然不考虑上溢出）。 那么就得到了一种比较普通的方法，取 $1<l<r<n$，那么答案即为 $|a_1-a_l|+l+|a_n-a_r|+(n-r+1)+(r-l+1)$。 化简式子可得 $|a_1-a_l|+|a_n-a_r|+n+2$，可以发现与 $l,r$ 的位置无关，只与 $a_1,a_l$ 与 $a_n,a_r$ 的大小有关。 考虑两个 DP 数组 $f,g$，$f_i$ 表示 $x\in(1,i],\min |a_1-a_x|$，$g_i$ 表示 $x\in[i,n),\min |a_n-a_x|$，这两个数组也是好做的，代码大概是： 123f[1]=inf;g[n]=inf;rep(i,2,n)f[i]=min(f[i-1],abs(a[1]-a[i]));per(i,n-1,1)g[i]=min(g[i+1],abs(a[n]-a[i...

P16308 [ICPC 2023 Jinan R] 很多很多头 思路 首先题目中提到两种括号的朝向可以任意，所以实际上同种类型的括号等价。 然后考虑合法（唯一）且仅存在 [A] 这种结构的括号序列（将其称为“简单括号序列”）长啥样。 发现一定是 [([(A)])] 状物或是 ([(A)]) 状物。 也就是两种括号必须交替出现。 若有一段出现了 [[A]]，则可以被替换为 []A[]，圆角括号也是一样，此时不是唯一构造。 然后考虑 AB 结构。 若 A 与 B 的最外层是同一种，如 [A][B]，则可以替换为 [A[]B]，此时也不是唯一构造。 而如果存在三段及以上的“简单括号序列”，则根据抽屉原理一定存在两段的最外层相同，不是唯一构造。 所以得出结论：只能存在形如 [A] 的子结构，且最多有两个字结构，最外层还必须不同。 那么一个合法的序列就是 [A](B) 这样，转化一下变成 [A[(B(，然后 A 内部两种交替出现，B 内部两种交替出现，只有 A 和 B 最内层会出现连续且类型相同的括号，所以只需统计有多少组连续相同的括号，判断是否少于两种即可。 代码 1234567891...

P15406 [NOISG 2026 Prelim] 摩天大楼 思路 首先我们发现若 $k\le 2$，则一定有解。 我们现将所有高度的大楼数量按照高度为关键字排序。 考虑从上到下，从左到右填数字。 这时所有位置的上面和左边一定不存在比它高的大楼。 然后若 $k=4$，显然当且仅当所有大楼都一样高时成立。 这时便只剩下 $k=3$ 的情况需要讨论。 我们考虑从小到大填，从外往内覆盖整个矩形。 发现当且仅当用同样高度填充整行或整列才能合法地填入最小高度的大楼。 用完了一种高度的大楼就用大于它的最小高度的大楼。 若当前剩余的最小大楼数量不足填充任何一条整边，这种填充方法不合法。 考虑进行 DFS，传参还需要填充的行数和列数，现在用到了哪个高度以及用了多少。 但这样还无法通过，考虑进行记忆化，用一个 map 存下哪些行列数量已经遍历过了（因为从小到大填，所以填的顺序没有影响）。 所有的行数和列数都只会被考虑到一次，总时间复杂度为 $O(n^2\cdot \log n)$，$n$ 最大仅有 $1000$，足以通过。 代码 123456789101112131415161718192021...

CF2194D Table Cut 思路 假设一共有 $tot$ 个 $1$ 块。 第一部分很简单： 注意到任何分配均可以成立，故最大值一定为 $\lfloor\frac{tot}{2}\rfloor\times\lceil\frac{tot}{2}\rceil$ 这样的构造。 考虑第二部分如何构造： 我们假设上半部分分 $tar=\lfloor\frac{tot}{2}\rfloor$ 个 $1$，考虑如何构造。 预处理第 $i$ 行的总和为 $cnt_i$，现在已经加入了 $now$ 个，若 $cnt_i+now<tar$，则直接加这一行。 若 $cnt_i+now\ge tar$，则从后往前枚举，若能加则加，不能加就说明现在已经够了。 这样的构造要如何转化为题目要求的输出呢？ 首先若要加一整行，则直接输出 D，若要加上行末的 $k$ 格，则输出 $m-k$ 个 R，然后输出一个 D，再补上该行剩余的 R 即可。 最后输出剩下的 D。 代码 12345678910111213141516171819202122232425262728293031323334353637...

CF2194C Secret message 思路 先找所有可能的长度（总长的因子），从小到大排序。 枚举长度，枚举总字符串的每一位对应到子字符串的哪一位。 用状压的思想枚举子字符串的每一位所有可能值，从全集开始，每次都或上当前位所有存在的字母并集，若最后状态还不等于 $0$，则此位可以成立，若为 $0$ 直接 break。 若全部遍历完后则输出每一个状态最低位的对应字母（题目要求任意子字符串皆可）。 笑点解析：没初始化调了 $10$ 发都 TLE，结果用第一发代码加个初始化就过了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii ...

AT_abc444_e [ABC444E] Sparse Range 思路 题目要求求出满足对于所有的 $1\le l\le r\le n$ 所构成的区间，能使得区间中所有数之间的差值都大于 $D$ 的 $(l,r)$ 对数总和。 注意到对于每个区间，这个要求都比它的子区间更难达到。 所以对于每一个 $r$，若 $l_1<l_2\le r$，则若 $(l_1,r)$ 满足要求，它的子区间 $(l_2,r)$ 显然一定也满足要求。 而若要从 $l_2$ 推到 $l_1$，则需要所有 $l_1$ 和 $l_2$ 中间的数之间满足要求，且这些数都与 $l_2$ 到 $r$ 中间的数满足要求。 考虑使用双指针。 从大到小枚举 $l$，全局变量 $r$，每当有一个新的 $l$，就二分找现在小于等于它的最大的数和大于等于它的最小的数，如果差值小于 $D$，就将 $r$ 减一，然后再判断，直到满足为止，然后从 $l$ 到现在的新 $r$ 之间的所有区间全都满足，不从 $l$ 出发的前面统计过了，所以直接加上 $r-l+1$ 就行了。 由于每个 $r$ 都只会被枚举一次，所以可以通过。 代...

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)$ 地求出，直接...