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

点击跳转

动态规划

逆向思维

用所有的减去不合法的

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

点击跳转

一看就是树剖

先设所有情报员开始搜索情报的时间(我们假设给这个情报员赋值)是q,即询问个数

对于第i个询问如果是查询,则查找值比i-c小的情报员有多少个(树剖)

参与传递的人数显然是d_x+d_y-2 \times d_{LCA(x,y)} + 1

如果是让某个情报员开始搜集,则把这个情报员赋值为i

解法一:

套个主席树应该就可以了(请参见楼下)

解法二:

离线按照权值排序添加,然后用线段树或树状数组统计就可以了)

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

点击跳转

树形dp中的\text{up and down}

还有一点期望

设每个点能够通电的概率为P_i

那么ans = \sum_{i=1}^n P_i

我们先考虑up(只考虑子树))

分成两种情况:

  1. 直接通电 : q_i

  2. 被子节点通电 :

    (1-q_i) \times P_{to}(\text{子节点}) \times e_i.w(\text{连接的边导电的概率})

我们再考虑down(考虑子树外))

我们可以通过父节点的答案来更新子节点

父节点的答案是包括当前子节点的

可以把这部分除去然后按照up的方法更新

P_x= P_x' (1-P_x')*(P_{to}*e_i.w)(P_x'指根节点除去当前子节点的贡献的答案)

整理得: P_x'=\frac{P_x-(P_{to} \times e_i.w)}{1-(P_{to} \times e_i.w)}

(这里有个坑点:当1-(P_{to} \times e_i.w) = 0时这个式子就没有意义了)

\therefore P_{to} = P_{to} + (1-P_{to}) \times P_x' \times e_i.w

所以在下推的时候要特判一下

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

点击跳转

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

点击跳转

区间dp

显然设f[i][j]表示[i,j]最小的表示方法

普通情况:

f[i][j] = \min(f[i][k]+f[k+1][j])

当我们找到循环节:

f[i][j] = \min(f[i][j],f[i][k] + 2 + \text{<循环节个数>})

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

点击跳转

此题与网络流24题中的骑士共存问题一致

最大流=最小割

用点数-去可以攻击的最大匹配

可以使用网络流或二分图

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

点击跳转

先根据原来的边建树

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

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

60/74
Search
search