1001

将a中的子串b替换成*(也可以不替换),问可以构成多少种不同的串

DP

用KMP处理出子串的位置,考虑不能重叠

d[i] = d[i] + d[i-1]
d[i] = d[i] + d[i-|b|]

1005

1006

1010

有一些位置为0的序列,0可以替换为任意整数
问最后可以构成的最长的LIS长度

LIS

我们要利用全部的0,因为这样不会使原来的LIS长度减小

每个非0的位置减去它之前到上一个不为0的位置间的0的个数,构成新的序列
这样就保证了序列是严格递增的…

然后对当前序列做LIS,最后答案就是 LIS+0的个数

1011

1012

求一个排列冒泡排序中每个元素的最右和最左位置的差

树状数组

最右位置就是当前位置加上它右边比它小的元素个数
这个倒着用树状数组统计就行了
最左位置就是当前位置和最终位置的最小值