模拟赛
T1
对每个ai开个桶分别算答案即可
注意long long
T2
维护m个指针
倒着枚举l
p1~pm维护第i个字符已匹配的下标
每次匹配修改一个前缀
复杂度O(n)
另外可考虑：
T3
设dpi,j表示i子树内钦定返祖j次的方案数
将相邻向北的点对连边，形成若干条链
合并子树时方案数
然后新加一个点，这个点相当于加入到任意一条链中，或者新增一条链
最后把钦定变成恰好，容斥一下
T4
牛逼的题
先考虑k=2
挖掘性质
DP
CF392B
fi,x,y表示前i个盘，从x到y的代价
容易转移
P2331
dpi,j,0~4表示第i行，选了j个矩阵
这一行的两个数{
-
没有元素被选择
-
第一列的元素在子矩阵中
-
第二列的元素在子矩阵中
-
两列元素在同一个子矩阵中
-
两列元素在不同子矩阵中
}
分别转移即可
CF607B
fi,j表示消除[i,j]的最小代价
经典区间DP
CF571B
相当于要求选择k条链
求出k条链最大值减最小值最小能是多少
容易看出每条链不交
CF703E
b为k的倍数当且仅当gcd(b,k)=k
fi,j表示前i个数gcd=j的最小元素和
而gcd(Bb,k)=gcd(b,k)gcd(b,k/gcd(B,k))
P1169
对(i+j)奇数的点取反
变成颜色全相同的最大子矩阵/正方形
子矩阵就对每个点求出往上最大延伸长度
据此算出往左往右第一个比他小的位置
计算答案
正方形就设fi,j表示以i,j左上角最大边长
若si,j=i-1,j=i,j-1=i-1,j-1
则fi,j=max(f+1)
QOJ8933
fi,j表示i个事件，剩j个1分，最多0分的数量
此时2分数量=si-j
简单转移
QOJ9312
期望DP
QOJ8528
环上的线相交相当于区间相交
数据随机
答案不会太大（<900）
gi,j表示i,j最大匹配
满足单调性
fi,j表示满足gi,k=j的最小的k
转移考虑i是否匹配
若匹配，那么更新就是从 ri 继承过来加上 gi,ri 的答案
否则就是从 i + 1 继承
计数
GYM105336
容易发现如果一个 ai 和 bj 匹配了，那么 ai 后的元素与 bj 前的元素匹配对答案就不会产生改变了
考虑 答案 k 被确定时，方案可以简单算出
令 fi,j 表示前 i 个 a 匹配了 j 个 b 的方案数
每次枚举选不选即可转移
不难发现对于一个权值为 w 的方案，恰好在 k = 1~w 都被计算了一次
直接对所有 k 的答案求和即可得到所有匹配的权值和。
P2592
转化成网格计数
要求y-x极差<=k
（对称计算答案就是用类似卡特兰数的方法
卡特兰数公式：C(2n,n)-C(2n,n-2)
这个公式就是通过对称得来的）
复杂度O(n+m+k)