参考资料

• 一份通过google search找到的资料
• OI-wiki

定义们

my submission on loj.ac

一个排列 $P$ 的冒泡排序交换次数达到下界当且仅当：对于某个位置 $i$ ，在它左边的、比 $P_i$ 大的数的个数不能超过 $\max\{0, i-P_i\}$ 个。

这个条件也等价于：

以下为我在校内讲课的课件。主要的参考资料为 James Stewart Calculus, 7th edition ，课件中的大部分的图片为这本书（6th or 7th edition）的截图，少部分图片来自维基百科（来自维基百科的图片均已在文中注明）。

错误可能比较多，欢迎指出。

链接：在google drive中查看

• link to the problem
• my submission

对于一个序列和一个询问集合，设 $S_i$ 为包含了 $i$ 这个位置的询问的集合。一个询问集合合法当且仅当 $S_i$ 互不相同。

性质 1 ：如果 $a<b<c<d, S_a=S_c, S_b=S_d$，那么 $S_a=S_b=S_c=S_d$ 。

A - 数一数

总感觉是做过的题，甚至清晰的记得给赵爷讲过，但是想不起来做法了…… :sob:

ZJK 告诉我题意是有问题的，每一列只能有恰好一个 $1$ ，否则样例 1 的答案就应该是 $\frac{3}{4}$ 。

参考资料

1. OI-wiki
2. wikipedia
3. 一份有详细图解的课件

KD-Tree 是什么

A - string

经典题目。

B - tree

定义-三角函数

其中

Sol

假设 $A$ 按照从小到大排好序之后得到的数组是 $B$ 。对于相邻的两个位置，假设其中一个是 $B_i$ ，另一个是 $B_j$ ，其中 $i<j$ ，那么这两个位置对 $\sum |f_i - f_{i+1}|$ 的贡就是 $B_j - B_i = \sum_{k=i}^{j-1} (B_{i+1}-B_i)$ 。这个式子启发我们，对每个 $B_{i+1} - B_i$ 算有多少对相邻的位置满足其中一个数 $\le B_i$ 另一个 $\ge B_{i+1}$ ，就能得到 $\sum |f_{i+1}-f_i|$ 。这也等价于我们把所有 $\le B_i$ 的数插入之后得到的序列中，极大连续段的端点数。

设 $f_{i,j,k,d}$ 表示已经插入了 $i$ 个数，插入了的数在序列中形成了 $j$ 个极长的连续段，已经统计过的 $\sum |f_i-f_{i+1}|$ 的贡献和是 $k$ ，两个端点是否被占用过，对应的方案数。转移 $O(1)$ ，最后的答案是 $\sum_{j\le m} f_{n,1,j,2}$ ，总复杂度 $O(n^2m)$ 。

Sol

考虑给一个第一行确定的矩形涂色的方案数：

• 第一行是红蓝交错的（RBRBRBR…或者BRBRBRB…）
  • 那么，接下来的每一行都有恰好两种选择，RBRBR…或者BRBRBR…，方案数是 $2^{n-1}$
• 第一行存在两个相邻的位置颜色相同
  • 显然在第二行中，那两个位置的颜色也是相同的；以此类推，这个矩形中的每一行都会有两个相邻的位置颜色相同
  • 对于第二行来说，由于上一行和这一行的至少两个格子的颜色是确定的，所以第二行每个格子的颜色都是确定的；后面的行也是同理
  • 所以涂色的方案数是 $1$