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

点击跳转

  1. b_i = a_i + 1

    一条链

    直接二分最小值,然后判断即可

  2. m=1

    直接找树的直径

  3. a_i = 1

    记录所有边权,设边权为w,然后排序

    w_1 + w_{2m} , w_2 + w_{2m-1}, ...的最小值

  4. 分支不超过3(基本上就是正解了)

明摆着就是正解嘛

dfs(x,f,w)求出x的子树连接x长度不超过w的最长路径

路径分为两种

一种\ge w,那直接条数++

另一种a+b \ge w

那我们直接用multiset存,每次lowerbound找到最接近的,然后返回

stl,还是太弱了Q\omega Q

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

点击跳转

f[i][sta]表示以第i只奶牛结尾,状态为sta的情况下有多少种

f[i][sta] = \sum f[i-1][sta']

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

点击跳转

H:minH , V:minV

  A \times (h-H) + B \times (v-V) \le C

A \times h + B \times v -C \le A \times H + B \times V

s = Ah + Bv - C,按s排序,确保i可以取j就可以取(j<i)

枚举H,V,然后用双指针,具体看代码

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

点击跳转

把风铃看成一棵树

因为交换一根杆的两端不会影响它下面的子树的情况,所以可以采用分治+分类讨论

我们先预处理出最小深度和最大深度

如果差大于1,那么不满足要求

一个端点可以分成三种情况

  1. 都是最小深度

  2. 都是最大深度

  3. 两种都有

如果一根杆左右端点分别为0,10,22,1那么它就需要交换左右端点

如果左右端点都是2那么交换也没用,直接输出-1,结束程序

然后把状态向上传递就可以了

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

点击跳转

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

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

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

点击跳转

73/74
Search
search