在讨论《这不是 P14458 严格弱化版吗 /baiy》回复：

@[_ATRI](luogu://user/2029033) 这是极其严重的学术不端。和难度、第几题没有关系。

在讨论《还有救吗》回复：

喜欢故意装弱说批话以获取关注的缺爱小朋友你好呀

在讨论《这不是 P14458 严格弱化版吗 /baiy》回复：

原来是搬的。这下这下了

在讨论《这不是 P14458 严格弱化版吗 /baiy》回复：

不是故意搬题的话，是不是就是查重不力的问题呢？还是说根本没有查重呢？

[P14458 [ICPC 2025 Xi'an R] Let's Make a Convex!](https://www.luogu.com.cn/problem/P14458) /baiy/baiy/baiy

显然，序列 $a$ 是否能通过操作排好序只和每个元素的相对大小有关，因此我们可以先求出将其离散化后的序列 $b$。对于序列 $b$，设其值域为 $[1,w]$，我们考虑序列 $b$ 拆成 $w+1$ 个 $01$ 串 $c_0,c_1,\dots,c_w$，其中 $c_{i,j}=[b_j \ge i]$，那么序列 $…

合法的方案数并不好求，因此考虑正难则反，计算不合法的方案数。 首先尝试刻画一下不合法的条件。显然，如果小 R 购买的糖果是按照性价比排序后的一段前缀，则他买到的糖果一定是最优的；因此，我们只需要考虑中间有一些糖果因为买不起而没有买的情况。设： - 小 R 在只剩下恰好一元钱前，购买的最后一颗满足 $w_i=1$ 的糖果…

设集合 $U=\{i \mid s_i=1\}$，考虑钦定一个集合 $S \subseteq U$，满足： - 对于所有 $i\in S$，第 $i$ 个位置的人会被录取，即要求 $c_i \gt \sum\limits_{j=1}^{i-1} [j \notin S]$； - 对于所有 $i\in U\setminu…

在文章《场上的我像个 sb》发表评论：

你牛大了

设第 $i$ 个人给下一个人传了 $c_i$ 个球，第 $i$ 个人的手中最终有 $x_i$ 个球，则有 $x_i=a_i-c_i+c_{i-1}$，其中我们认为 $c_0=c_n$。显然，若 $\min\limits_{i=1}^n c_i \gt 0$ 则可以通过使所有 $c_i$ 都减去 $1$ 的方式保持最终局…

在讨论《喧嚣二阶》回复：

怎么被发现了

直接做有点困难，因此考虑钦定一些尚未确定的障碍点在路径上。设被钦定的障碍点的集合为 $T$ 时，满足条件的路径数为 $c(T)$，则根据容斥原理可知答案可以表示为 $\sum_{T} (-1)^{|T|} c(T)$。 设 $f_{i,j,k,0/1,0/1}$ 表示，考虑到第 $i$ 行第 $j$ 列的格子，此时一共…

考虑把 $a_i$ 看作 $1$ 类数，$b_i$ 看作 $2$ 类数，将所有 $a_i$ 和所有 $b_i$ 扔进一个长度为 $2n$ 的数列 $c$ 中并从大到小排序，每次选出一个 $1$ 类数和 $2$ 类数进行匹配，贡献乘上较小的数的值，将问题转化为求所有匹配方案的贡献之和。 设 $f_{i,j}$ 表示考虑到…

设总成本为 $w$，第 $i$ 个灯是第 $p_i$ 个被点亮的。考虑每个灯节约了多少成本，则显然有： $$ \left(\sum_{i=1}^n a_i\right)-w=\sum_{i=1}^n \min(a_i,p_i-1) $$ 考虑把 $a_i$ 看作 $1$ 类数，$p_i-1$ 看作 $2$ 类数，将所有…

将所有球按照 $X_i$ 排序，那么第 $i$ 个球满足 $X_i=i$。显然选择的球的顺序并不重要，我们只需要明确哪些球被选了。为了方便，我们在 $(0,n+1)$ 和 $(n+1,0)$ 处各添加一个球，并强制选择这两个球。 设选择的球所组成的集合为 $S=\{a_1,a_2,\dots,a_m\}\ (0=a_1…

将对排列 $a$ 的计数转化为对其逆排列 $b$ 的计数，那么此时要求结点 $b_i$ 不在结点 $i$ 的子树内。 考虑容斥。设 $g_i$ 表示钦定 $i$ 个结点不合法，且只考虑这 $i$ 个结点的方案数，那么 $ans=\sum\limits_{i=0}^n (-1)^i\times g_i\times (n-…

考虑 dp。设 $F_{i,j,k}$ 表示，对于第 $i$ 种衣服，考虑到第 $j$ 个人，有恰好 $k$ 个人的尺寸合适的概率。容易得到转移方程： $$ F_{i,j,k}=F_{i,j-1,k-1} \times p_{j,i} + F_{i,j-1,k} \times (1-p_{j,i}) $$ 设 $E_{…

## [CF183D T-shirt](https://codeforces.com/problemset/problem/183/D) :::info[题解] 考虑 dp。设 $F_{i,j,k}$ 表示，对于第 $i$ 种衣服，考虑到第 $j$ 个人，有恰好 $k$ 个人的尺寸合适的概率。容易得到转移方程： $$…

设从 $i$ 指向 $p_i$ 所形成的图为 $G_1$，从 $i$ 指向 $a_i$ 所形成的图为 $G_2$，考虑考查 $G_1$ 和 $G_2$ 之间的关系。 显然 $G_1$ 由若干个环组成，于是考虑 $G_1$ 中的每一个环： - 若环上的每一个点都满足 $a_i=p_i$，则 $G_2$ 中有一个一模一样的…

注意到，如果我们把 $\texttt a$ 看作 $1$，$\texttt b$ 看作 $2$，设 $f(s)$ 表示字符串 $s$ 中所有字符所对应的数字之和对 $3$ 取模后的值，那么每次操作不会改变 $f(s)$。 首先考虑字符串 $s$ 能不能变成单个字符 $c$（$s \ne c$）。此时显然需要满足： -…

首先考虑对于一个确定的长度为 $n$ 的 $\texttt{01}$ 串 $S$，如何求 $S$ 的编码方式数。 设 $f_{l,r}$ 表示 $S_l\sim S_r$ 的编码方式数，$g_{l,r}$ 表示 $S_l\sim S_r$ 缩成一个括号或单个字符的编码方式数。 对于 $f_{l,r}$，枚举 $S_l\…

将所有线段从短到长排序，考虑断环为链，以第 $n$ 条线段即**最长的线段**的左端点作为起点，将问题转化为：最长的线段的左端点位于位置 $0$，其余线段的左端点在 $[0,c]$ 上随机，求 $[0,c]$ 都被覆盖的概率。其中，以最长的线段的左端点作为起点是为了防止存在另一条更长的线段 $[x,c+y]$ 覆盖了…

显然总期望操作次数等于每个点期望操作次数之和，于是考虑对于每个点 $u$，计算点 $u$ 被操作次数的期望。 设点 $u$ 的深度为 $d_u$，那么点 $u$ 是否还需要被操作只和点 $u$ 到根路径上的 $d_u$ 个点的状态有关，所以我们可以只考虑这 $d_u$ 个点。 于是现在问题转化为了，有 $d_u$ 个点…

由于每个点最多只会被删除一次，且每个连通块不会增大，所以可以将题意转化为：随机一个排列 $p$，从 $1$ 到 $n$ 依次考虑每个点 $p_i$，如果点 $p_i$ 所处的连通块大小大于 $k$ 则删除点 $p_i$，否则不进行操作，求期望删除次数。 设 $P(G)$ 表示原树的子图 $G$ 作为一个完整的连通块的出…

先考虑 $\min\limits_{1 \le i \le n}\left(\max\limits_{1 \le j \le m} a_{i,j}\right)\lt \max\limits_{1 \le j \le m}\left(\min\limits_{1 \le i \le n} a_{i,j}\right)$…

## [P1758 [NOI2009] 管道取珠](https://www.luogu.com.cn/problem/P1758) :::info[题解] 有一个经典的 trick 是，可以将每个东西出现次数的平方转化为选择两个相同东西的方案数。对于此题，即为将 $\sum {a_i}^2$ 转化为选择两个相同的输出序…

考虑把排列 $p$ 拆成 $n+1$ 个 $01$ 串 $c_0,c_2,\dots,c_n$，其中 $c_{i,j}=[p_j\ge i]$，那么排列 $p$ 能通过操作排好序当且仅当它拆成的 $n+1$ 个 $01$ 串都能通过操作排好序。 可以时刻维护每个 $01$ 串是否合法，把每个排列 $p$ 看成一个 $0…

考虑维护一棵值域线段树 $T$。对于每一个 $i$，将 $T$ 上 $[b_i+1,a_i]$ 的位置的值加 $1$，于是 $a$ 可以变成 $b$ 当且仅当 $T$ 上每一个位置都大于等于 $0$，此时需要的操作次数为 $\sum\limits_{i=1}^m a_i-\sum\limits_{i=1}^m b_i$…

首先把总和拆开，将 $\sum\limits_{i=1}^n a_i$ 转化为 $\sum\limits_{j=1}^m \sum\limits_{i=1}^n [a_i \ge j]$。 于是考虑枚举 $j$，计算 $\sum\limits_{i=1}^n [a_i \ge j]$ 的总和。 设初始时满足 $a_i…

首先考虑 $D_i=0$ 怎么做。 不妨令 $L_0=a_0$，$R_0=b_0$。设 $A_n=L_i \le L_0$，那么显然 $B_n$ 所能取到的最大值为： $$ \min(R_0,\min_{L_j \lt L_i} R_j) $$ 按照 $L_i$ 从小到大的顺序计算即可。 接下来考虑不保证 $D_i=0…