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

点击跳转

排序 贪心

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

点击跳转

首先二分出最大一段的最小值,然后dp找出方案数

f[i][j]表示前j个分成i组的方案数,求出的最小值为x

f[i][j] = \sum(f[i-1][k])(S_j-S_k \le x,k \le j-1)

\Theta(n^3m)当然会TLE

我们发现只要找到最小的k之后[k,j-1]都是合法的

这时我们就可以前缀和优化dp

sum[i][j] = \sum_{k=0}^j f[i][k]

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

可是\Theta(n^2m)还是TLE

我们可以先预处理出第一个S_j-S_k \le xk

因为S_i具有单调性,所以k不需要每次都重新枚举

还没结束

因为f[i][j]每次更新的时候只需要用到f[i-1][...]这一维,我们可以用滚动数组滚掉数组的一维

但是\Theta(nm+n \log \sum L_i)的复杂度还是觉得很悬

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

点击跳转

tarjan找出强连通分量之后树形dp

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

点击跳转

考虑排序后的序列

i个人说有a_i个人分数比他高,有b_i个分数比他低

从大到小排序后分数和i相同的人的区间为[a_i+1,n-b_i]

我们设L_i = a_i + 1, R_i = n - b_i

那么如果L_i > R_i显然是假话

如果R_i-L_i+1小于这个区间的人数(L_{i'}=L_iR_{i'}=R_i),那么这也是假话

去掉所有一定是假的话后,问题变成:给若干个区间[l_i,r_i],价值为v_i,从中选出若干个没有交集的区间,价值和最大为多少?

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

点击跳转

离散化 建图 最短路

烦死了

51/74
Search
search