zcmimi's blog

categories/刷题记录/共646篇文章

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

点击跳转

数位dp模板题

我们先不考虑前导0,那么满i位所有数字出现的次数是相同的

f_i为满i位数字出现的个数(因为相同就不需要再加一维了)

那么f_i = f_{i-1} \times 10 + 10^{i-1}

((0-9)+(0-9.....))

(0-9:10^{i-1},(0-9.....):f_{i-1} \times 10)

我们来想想ABCD的答案

先考虑A000中的000,每种数据出现的次数是A \times f_3(因为A后面有3位)

那么0~A-1出现的次数还要加上10^{i-1}(X xxx(xxx:0-999))

接着考虑ABCD中的BCD,A出现的次数加上BCD+1(000-BCD)

最后减去前导0,也就是0001,0002,...0101,0102,...,0999这些,那么0出现的次数减去10^{i-1}

答案就是solve(r)-solve(l-1)

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

点击跳转

离散化 建图 最短路

烦死了

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

点击跳转

单调队列优化dp

f[i]表示从1-i最多能选出的效率

枚举断点j,

f[i] = \max(f[j-1]+ \sum_{t=j+1}^i a[t])

但是直接这样的复杂度不可行

我们可以考虑用单调队列优化

f[i] = \max(f[j-1] - S_j) + S_i

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

点击跳转

二分最大差值

然后bfs判断

我怎么又刷水了QwQ

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

点击跳转

f_{i,j,k,(1/0)}a_i(选或不选),b_j,k

f_{i,j,k,0} = f_{i-1,j,k,0} + f_{i-1,j,k,1}

a_i = b_j:

f_{i,j,k,1}=f_{i-1,j-1,k,1}+f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k-1,1}

a_i = b_j:

f_{i,j,k,1} = 0

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

点击跳转

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

点击跳转

二分

判断的时候枚举区间,用rmq或单调队列来求最值,还可以用堆(看题解的)

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

点击跳转

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

点击跳转

n个小根堆,然后启发式合并即可

可以用并茶几判断一个人所在的团

唉唉,过了,stl开o2

等等,居然是左偏树

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

点击跳转

经典的最小路径覆盖问题

可以看出一开始有 1~n条路径(1~n)

每次可以挑选一个点,合并两条路径

但是一个点只能用一次

所以我们把点拆成两个

从源点向每个点的入点连一条边权为1的边

从每个点的出点与汇点连一条边权为1的边

每个点的入点向能到达的点的出点连一条边权为1的边

用 n-最大流 就是答案

至于输出:

突然有点尴尬

随便乱搞吧

用过的边就是合并过的

把这些边合并起来就可以得出路径

(搞个并茶几???)

43/65
Search
search