0103abc 的网站

考虑用第一类斯特林数的生成函数来解这个问题。设 $fx(n)$ 是第 $n$ 行第一类斯特林数组成的生成函数，则有：$fx(n)=\sum\limits{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i=\prod\limits{i=0}^{n-1}(x+i)$。...

~~积分我哪会啊，已严肃背过结论~~ 答案是 $\large\frac1n\sum\limits_{i=n-k+1}^i\frac1i$，线性递推出逆元然后用前缀和就可以做到 $O(n)-O(1)$。

正解很困难，但是注意到这是一个最优化问题，所以先考虑一个显然的贪心：按顺序插入每个物品然后分别计算其插入到两个集合内的代价，若插入到 A 集合里更优那么就插入到 A，否则就插入到 B。 这一看就很没有道理，但是这个时候直接随机一个顺序贪心然后多随机几次就能过了，应该是卡不了的。

挺好玩的这题其实 首先容易观察到答案是一段连续的区间。因此对于答案区间 $[l,r]$，考虑二分求解。这样的问题有两种策略： 先找到一个合法位置，然后以这个位置为分界线向左向右分别二分。 直接分别二分出区间左右端点。 这里采取第二种做法。 判断当前二分到的总长度 $x$...

考虑沿用 CBC022E 的套路，把题面中给的操作扔到 $a$ 的差分数组里，容易发现其实就是交换两个相邻的数的差分值。 套路的把方差乘以 $n^2$ 拆成 $n\sum\limits{i=1}^nai^2-(\sum\limits{i=1}^nai)^2$ 的形式，然后考虑 dp 处理。设...

先把期望成求和问题。 考虑一个非常厉害的转化：把两个序列 $a,b$ 拼接到一起得到序列 $c$，这样问题就变为了在序列 $c$ 上两两配对求所有最小价值的和。容易发现此时 $c$ 序列上顺序是无所谓的，因此对 $c$ 序列所有元素的值从大...

性质的必然存在性.jpg 注意到题目给出了十分特殊的性质 $\boldsymbol{k\le n}$，因此考虑从这个地方入手。 注意到当 $k<n$ 时，根据抽屉原理可知必然存在一个全 $0$ 行，因此考虑枚举该行，然后对于该行内每个 $1...

题解区里怎么没有写二进制分组 KDT 的（） 先考虑其弱化版 [P3769 [CH弱省胡策R2] TATT](https://www.luogu.com.cn/problem/P3769)。该问题求解的是四维意义下的 LIS，容易想到先按第一维排序，然后转化为三维的偏序关系。 比较常规的解法是...

K-D Tree 是一种可以维护高维空间信息的数据结构，其结构和平衡树比较相似。 维护高维子空间信息 以一道板子题为例： 在 $k$ 维空间中，有一个由整点构成的可重集 $S$（初始为空），$S$ 中每个点都有一个权值。记整点 $A$ 的第 $d$ 维坐标为 $x_d(A)$。 你需要维护三种操作：...

唐题。 先考虑一个十分暴力的做法：对数组进行分治。对于一个分治区间 $[l,r]$： 求出该区间内元素最大值 $mx$。 找到数组 $X$ 表示该分治区间内所有值为 $mx$ 的位置。 考虑计算 $mx$ 为最大值时，对答案的贡献。此时若一个区间 $[l',r']$ 满足...