1001

一个有序序列
输出[l1,r1] [l2,r2] 组成新序列的中位数
注意区间有可能重叠

水题

直接计数,找出中间位置
注意计算过程可能爆int

1002

求阴影面积

平面几何

1004

1005

1006

求平面上若干条与坐标轴平行的线段的交点

线段树

我是直接按线段树维护矩形面积并(把线段视为1*L的矩形)来做的
题解的方法更简单

1007

求两个长度为n最长公共子串长度为m的串的个数
字符集大小为k

矩阵快速幂

$d_{i,j,0..1}$ 表示长度为i的串,当前连续最长公共子串为j
长度为m的公共子串是否出现过

$d_{i,j,0..1} = kd_{i-1,j-1,0..1}$
$d_{i,0,0..1} = k(k-1)d_{i-1,j,0..1} \;\; j $
$d_{i,m,1} = kd_{i,m-1,1}$

用一个(2m)^2的矩阵表示转移

不过卿爷的做法更简单,最后一维可以去掉
这样$d_{i,j}$表示的是最长公共子串大于j+1的个数

$d_{i,0} = k(k-1)d_{i-1,j}$
$d_{i,j+1} = kd_{i-1,j}$

答案就是$ans_m - ans_{m-1}$

1011

输出数字转化成英文书写格式
输出字符数

模拟

考察细节较多,可以把所有出现过的单词都列举出来