最近的状态非常爆炸,几乎所有题都不能想出第一步QwQ.

只能尽可能调整一下状态了.

bzoj3489

如果允许离线显然是水题.

强制在线的话我们用主席树维护就行啦.

bzoj1019

令$f[i][j]$表示一开始在柱子$i$上有$j$个盘子,要移动到另外一个的最少步数.

令$g[i][j]$表示一开始在柱子$i$上有$j$个盘子,在最小字典序意义下会移动到哪一个柱子.

转移就非常显然了.

bzoj1021

我又不会做的水题...

不同的钞票之间显然是独立的.

令$f[i][j][k]$表示前$i$种钞票,第一个人有$j$元,第二个人有$k$元的最小钞票数,简单dp即可.

bzoj1935

将询问转化为前缀相减并离线,离散化后利用树状数组维护即可.

bzoj2024

把所有男生女生都按照身高从小到大排序,令$g[i][j]$表示排名前$i$小的女生参与匹配,且至少存在$j$对女大于男的方案数.

令$num[i]$表示比排名第$i$的女生身高矮的男生数目.

那么有转移:$g[i][j]=g[i-1][j]+g[i-1][j-1]\times{(num[i]-(j-1))}$.

然后这样会有重复的方案,所以要容斥一下,然后就行了.