zcmimi's blog

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

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

点击跳转

左右都hash一遍

然后二分每个位置可以组成回文串的长度(判断奇数和偶数长度)

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

点击跳转

求树的直径

读入毒瘤

自己探索吧(不怀好意

(tips:getline,ssstream)

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

点击跳转

先把所有0合成1个,所有正数合成一个,把负数(除了最大的那个负数之外的(如果负数个数为奇数)))合成一个

1.如果全是0

2.没有0

3.没有负数

4.没有正数

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

点击跳转

这篇题解可能是对楼下的补充

我们考虑每个点能贡献多少次

无标题.png

设当前节点为x,路径有三种情况,上图分别对应情况1,情况2,情况3

  1. x子树内\rightarrow x \rightarrow x子树外(包括x)

  2. x子树内(包括x)\rightarrow x \rightarrow x子树内

  3. x子树外\rightarrow x \rightarrow x子树内

我们可以先处理出与x的距离为偶数和与x的距离为奇数的点的个数,分别记作f_x,g_x

那么f_x = 1 + \sum g_{to},g_x = 1 + \sum f_{to}(tox的孩子)

我们来考虑所有情况

  1. ans += V_x \times (f_x-g_x) \times (n-siz_x+1)(可以在x的子树中随机选一个往子树外面走(可以指走到x))

  2. ans += V_x \times (g_{to}-f_{to}) \times (siz_x-siz_{to}-1)

    ans+= V_x \times (siz_x-1)(可以从x直接向下走)

  3. 我们需要记录x子树外与x的距离为偶数和与x的距离为奇数的点的个数,分别记作uf_x,ug_x

    我们可以通过bfs从上到下来处理,那么

    uf_x=ug_{fa_x}+g_{fa_x}-f_x

    ug_x=uf_{fa_x}+f_{fa_x}-g_x

    ans += V_x \times (uf_x-ug_x) \times siz_x

接下来放代码:

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

点击跳转

记录区间内最先出现的左括号和右括号

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

点击跳转

树形dp 长链剖分

加强版

先来考虑1 \le n \le 5000

f[i][j]表示在i的子树中与i距离为j的点数

显然f[i][j] = \sum f[to][j-1](f[i][0] = 1)

g[i][j]表示以i为根的子树中,点对(x,y)满足x,ylca(x,y)距离都是d,并且lca(x,y)i的距离为d-j的点对数

g[i][j] = \sum g[to][j+1]

ans = \sum_{i=1}^n (g[i][0]+g[i][j] \times f[to][j-1])

我们来考虑加强版

n \le 100000

有点像静态链分治和树链剖分

我们计算长链的时候结果不需要清空,其他儿子节点重新计算

这样可以省下长链的时间

长链剖分真是个毒瘤(指针毒瘤)

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,结束程序

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

64/66
Search
search