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

点击跳转

二分最大差值

然后bfs判断

我怎么又刷水了QwQ

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

点击跳转

一个数有三种情况:

  1. 放左边
  2. 放右边
  3. 不选

折半搜索

还是一样的套路

分前部分和后部分搜索

但是有可能出现前后选的数出现重叠状况

我们可以用状压并开一个桶来记录是否重复出现过

最后答案记得-1,因为空集不算

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

点击跳转

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

点击跳转

先根据原来的边建树

一条新边(x,y)能影响的边有树上x \rightarrow y路径上的边

那么这道题就转化成了树剖+线段树维护最值

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

点击跳转

二分最大值,然后树型dp

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

点击跳转

树形dp up and down

考虑 up:

s_x为点x子树中所有点到x的距离之和

S_x = \sum (s_{to}+siz_{to})

考虑 down:

s_{to} = s_{to} + (s_x-s_{to}-siz_{to}) + n - siz_{to}

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

点击跳转

link\ cut\ tree维护最小生成树

直接在线很难,我们可以离线加边

先把所有边(后来断掉的不算)跑一遍最小生成树

接着每次加边,设加xy,边长为w

先求出xy路径上最长的边

如果比要加的边长,则删掉这条边,加上新边

这样就可以lct维护最小生成树

因为lct不能直接维护点,所以我们可以把边看成点

x\rightarrow边\rightarrow y

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

点击跳转

f(i,j)表示前i个划分成j段最少的费用

我们设calc(l,r)表示[l,r]划分成一段的费用

f(i,j)=\min_{x=1}^i(f(x-1,j-1)+calc(x,i))

可以发现这个dp方程具有决策单调性

i<i',那么k_i\le k_{i'}(决策点)

把连续一段拆成两边更优x^2+y^2\le (x+y)^2(x,y\ge 0)

更巧的是w(l,r)可以用类似莫队的方法线性转移

这里采用分治的方法实现

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

点击跳转

52/73
Search
search