zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

离线处理,倒着添加

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f[i][j]表示翻转i次,还有j个与目标状态不同位置的方案数

每次翻转可以使与目标状态不同位置数量改变

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

预处理出二维前缀和

预处理出每个以(i,j)为右下角的A*B矩阵的和

预处理出每个以(i,j)为右下角的C*D矩阵的和

先用单调队列出列的C*D的最小值

再用另一个单调队列处理出行的

然后枚举比较即可

照着代码意会

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_{t,i,j} = MAX(f_{t-1,x',y'})+1

复杂度:O(Tnm),只能过50%

看到k \le 200那么我们是不是可以直接用?

f_{k,i,j}为在区间k中在位置(i,j)能最多滑行多远

f_{k,i,j} = MAX(f_{k-1,i,j},f_{k-1,i',j'}+dis_{(i,j),(i',j'))})

那么复杂度就是O(kn^3),可以用单调队列优化掉其中一个n

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

LG 1415 拆分数列加强版

复杂度要求减少

我们先来考虑dp方式

f_i = max(j)|(num(f[j],j) < num(j+1,i))

我们把填表式换成刷表式

现在不考虑0:

如果num(f[i],i)<num(i+1,i+1+i-f[i])

那么f(x) = max(f(x),i+1) (x\in[i+1+i-f[i],n])

否则f(x) = max(f(x),i+1) (x\in[i+1+i-f[i]+1,n])

(因为长度+1肯定满足)

于是我们可以令开一个数组来记录或者用线段树优化dp

现在考虑那个毒瘤的0:

要从i推到j

到达i时最小的数字应该是num(f[i],i)

这时候num(f[i],i)可能有前导0

num(i+1,i+1+i-f[i])也可能有前导0

我们用R0[i]表示从i开始有连续几个0

比较的时候就可以排除0的干扰

枚举的时候可以用hash+二分求出最大公共前缀优化到log n

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

n\le12

f[sta][x]表示状态为sta,当前位置为x的情况下最短的(字典序最小)

f[sta][y]=\min(f[sta'][x]+cost)

看到这个可以联想到AC自动机最短路(貌似是最短哈密顿路径?)

每个字符串长度都小于50,如果用AC自动机可能就核弹打蚊子

49/74
Search
search