普及+/提高

P16604 [SYSUCPC 2025] SYSU III 思路 神神原神原神 uu。 贪心找到的串一定合法，但不一定最优，所以答案不会大于正解。 考虑怎么使得贪心得到的值小于正解，只需构造 ssysysuu 这样的一个串，就可以使得贪心的第一个串的第一个 s 用掉了本该给第二个串的第二个 s 导致错误。 扩展一点，s...ys...u... 这样的结构每有两组就会使得贪心比正解少一。 那么我们只需要放 $(y-x)\times 2$ 组 s...ys...u...，再在最后加上 $x$ 组 sysu 就可以了。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>#define fir first#define sec second#define int long long#define pii pair<int,int>#d...

P16605 [SYSUCPC 2025] Sum 思路 数据范围一眼根号分治。 首先考虑暴力枚举进制，也就是进制转换，对于 $10$ 进制转 $k$ 进制，不断取 $n\bmod k$ 再除 $k$ 直到 $n=0$ 即可。 时间复杂度 $O(B\log n)$，其中 $B$ 是阈值。 然后考虑如何得到一个 $\frac{n}{B}$ 状物，分析上面的方法，发现若 $k>\sqrt n$，那么只能进行两次除法就归零，会取两个值： $n\bmod k,\lfloor\frac{n}{k}\rfloor$。 那么对于既定的 $k$，贡献则是 $n\bmod k+\lfloor\frac{n}{k}\rfloor$。 推一下式子： 原式 $=n-\lfloor\frac{n}{k}\rfloor\times k+\lfloor\frac{n}{k}\rfloor=n-(k-1)\times \lfloor\frac{n}{k}\rfloor$。 枚举 $\lfloor\frac{n}{k}\rfloor$，要使得原式子在既定的 $\lfloor\frac{n}{k}\rfloo...

CF2223A Zhily and Bracket Swapping 思路 首先一个不合法的括号序列有两种情况： 两种括号数量不相等。 存在某个前缀中的后括号数量大于前括号的数量。 又因为两个字符串的括号不可以跨位交换，所以我们枚举 $i\in [0,n)$，对于每个 $i$ 维护四个值 $sw_1,sw_2,v_1,v_2$ 分别代表序列 $1$ 可以往序列 $2$ 交换过去的前括号数量，序列 $2$ 可以往序列 $1$ 交换过去的前括号数量，此时序列 $1$ 中前括号比后括号多多少个，此时序列 $2$ 中前括号比后括号多多少个。 首先特判若两者中总的两种括号数量不相等，则不成立。 然后考虑如何维护上面的四个值以及它们分别有什么用。 首先维护 $sw1,sw2$，根据定义可得： 12if(a2[i]==1&&a1[i]==-1)sw1++;if(a1[i]==1&&a2[i]==-1)sw2++; 若在某个 $i$，$v1,v2$ 中有一个小于 $0$ 且无法“挽回”，则不存在合法构造。 “挽回”是什么意思呢，就是通过将前面某处可交换的交换使...

CF2223B Zhily and Barknights 思路 题目的意思是：把 $b$ 数组随机打乱，然后和 $a$ 对应位置相乘得到新数组 $c$，问 $c$ 里逆序对数量的期望值。 期望可以拆成每一对位置 $i,j(i<j)$ 的逆序概率之和。 对于固定的 $i$ 和 $j$，我们关心的是 $a_i\times b_i>a_j\times b_j$ 的概率，其中 $b_i$ 和 $b_j$ 是从 $b$ 里随机抽的两个不同数。 把 $b$ 里的数两两配对（有序），总共有 $n\times (n-1)$ 种可能。 条件 $a_i\times u>a_j\times v$ 等价于 $u\div v > a_j\div a_i$。 所以问题变成：给定一堆 $u,v$ 对，以及一堆比值 $a_j\div a_i$，统计有多少组满足 $u\div v$ 大于这个比值。 可以先把所有 $u\div v$ 排好序，然后对于每个比值二分查找，一次性累加结果。 最后除以总方案数 $n\times(n-1)$ 即可。 代码 12345678910111213141516...

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$ 都只会被枚举一次，所以可以通过。 代...