zcmimi's blog

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

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

点击跳转

先预处理出所有幸运数字

当前要求的是[l,r]中的幸运数字

我们可以使用容斥,用[1,r]-[1,l-1]

假设当前幸运数字为x,[l,r]中是x的倍数的有\left \lfloor \frac rx \right \rfloor - \left \lfloor \frac lx \right \rfloor +1

[1,r],[1,l-1]中的幸运数字的倍数可能有交集

继续容斥:

选1个-选2个的lcm+选3个的lcm-...

剪枝:

  1. 可以发现,一个数是另一个合法倍数的倍数,那么这个数字相当于没用(因为被前面的统计过了),可以删掉

  2. 如果将幸运数字从大到小排序,搜索时可以更快突破边界

  3. 现在因为所有数都不满足是另外一个数的倍数,所以合并任意两个数的时候,lcm的最小情况就是乘上一个3

    所以对于所有>r/3的合法数字,显然不能够和任何一个数合并了,所以这一部分可以拿出来直接提前算好

剩下的直接暴搜

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

点击跳转

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

点击跳转

f[i][j]表示第i天有j只股票最多赚多少钱 \\

  1. 直接买 f[i][j] = -ap[i] \times j
  2. 不买不卖

    f[i][j] =f[i-1][j]

  3. 买股

    f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

  4. 卖股

    f[i][j] = f[i-w-1][k] + bp[i] \times (k-j) (j \le k \le j + bs[i])

但是这样还是O(n^3)的复杂度,得想办法降到O(n^2)

看一下f[i][j] = f[i-w-1][k] - ap[i] \times (j-k) (j-as[i] \le k \le j)

可以化为f[i][j] = (f[i-w-1][k] + ap[i] \times k) - ap[i] \times j (j-as[i] \le k \le j)

于是就可以单调队列了 OωO

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

点击跳转

我们可以把每一行的SG异或

每一行只有20个,所以可以用状态压缩

可以通过动态规划或记忆化搜索的方式处理出每种状态的SG

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
查看原题

点击跳转

44/66
Search
search