zcmimi's blog

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

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

点击跳转

还是用并查集统计连通块大小

离线处理,按相关性从大到小加边

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

点击跳转

f_x表示在x放置且x的子树都被覆盖最少多少

g_x表示不在x放置且x的子树都被覆盖最少多少(x可以不被覆盖)

s_x表示在x放置且x的子树都被覆盖最少多少(x一定被覆盖)

f_u = \sum min(f_v,s_v,g_v)

g_u = \sum min(f_v,s_v)

s_u = (\sum \min(f_v,s_v)) - max(0,min(f_v-s_v))

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

点击跳转

S_i[1,i]\ge w的数的个数

如果一个区间要满足中位数\ge w,那么\frac {S_r-S_{l-1}}{\frac {r-l+1}2} \ge w

化简一下:2S_r-r > 2S_{l-1}-(l-1)

那么二分w然后用树状数组统计之后判断排名是否\ge k就可以了

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

点击跳转

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

点击跳转

求出LCA

如果

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

点击跳转

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

点击跳转

删除完这个字符串后面的就接到前面

我们可以想到用栈解决

然后判断剩下的串当前位置是否和目标字符串匹配我们可以用hash来解决

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

点击跳转

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

点击跳转

其实下面给出的a数组没什么鸟用

列出方程:

E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E)

解方程: E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E) \\\\ E = \sum_{i=0}^{n-1} \frac in + (1 - \frac mn)E \\\\ \frac mnE = \frac {\frac 12n(n-1)}n \\\\ E = \frac {n(n-1)}{2m}

65/66
Search
search