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

点击跳转

假设我们已经知道区间[l,r]左右节点的答案

记录:

lv,rv:左右端点的值
s: 区间答案
l:以左端开始最长下降
r:以右端结束的最长上升
L:以左端开始最长先上升(再下降)
R:以右端结束最长先上升(再下降)

然后考虑最高点再左节点还是有节点

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

点击跳转

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

点击跳转

开一个桶f记录每个数出现次数,然后f[i]=\sum_{i|d}f[d]

求出所有i的倍数可能组成的四元组,这时\gcd一定是i,2i,3i,\cdots,然后减去\gcd2i,3i,\cdots的四元组个数。即f[i]={cnt\choose 4}-\sum_{i|d,i\neq d}f[d]

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

点击跳转

保证这个数不会超过500000

那么就是背包了

买卖股票有3种方法:

  1. 买,第二天卖了

  2. 不买(相当于买了然后卖了)

  3. 买了,过几天再卖(相当于买了了,接下来卖了再买了)

d-1次背包即可

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

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

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

这样可以省下长链的时间

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

71/73
Search
search