zcmimi's blog

arrow_back思维共14篇文章

avatar
zc
2020-10-27 12:19:30

查看原题

点击跳转

既然对考虑每条边断开后产生的重心比较麻烦,那么换个方式:

考虑每个点成为重心的次数

首先找出重心作为树根

设当前节点为x,子树大小为siz_x,孩子的最大子树大小为g_x,割掉一条边后,另一棵树大小为S

考虑x不是重心的情况:

2(n-S-siz_x)\le n-S2g_x\le n-S

也就是

S\in [n-2siz_x,n-2g_x]

我们可以用树状数组维护并统计每个点割掉与父亲之间的边后形成的S

显然这条边不能在x的子树内,那么减去 进入x子树前后求和的差

考虑x为重心的情况:

ux重儿子,vx次重儿子

若割掉的边在u的子树中: 2siz_v\le n-S,即S\le n-2siz_v

否则: 2siz_u\le n-S,即S\le n-2siz_u

avatar
zc
2020-10-23 12:34:55

查看原题

点击跳转

在dfs的过程中维护一个栈st

假设当前遍历节点为x,栈顶st[tp]

x与栈顶形成一个括号对,那么弹出栈顶,将新的栈顶权值+1

栈顶权值表示:

如果有新的右括号入栈,以这个右括号结尾,能形成多少合法括号串

avatar
zc
2020-06-13 11:22:00
查看原题

点击跳转

逆推

若当前区间[l,r]和为x,考虑如何得到和为x-2的区间:

  1. a_l=2 \rightarrow [l+1,r]
  2. a_r=2 \rightarrow [l,r-1]
  3. a_l=a_r=1 \rightarrow [l+1,r-1]

这样我们求出区间 最大奇数和 与 最大偶数和,就可以预处理出所有x的答案了

avatar
zc
2020-06-11 16:49:00
查看原题

点击跳转

f_i表示所有数\gcdi还要加入的数的期望数量

ans=1+\frac{\sum_{i=1}^mf_i}m

可以知道f_1=0

f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)

继续推式子:

\begin{aligned} f_i &=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\ &=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m \end{aligned}

把分子拿出来

\begin{aligned} &\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\ \end{aligned}\\

T=dx

=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor

带入原来的式子

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m

F_T=\sum_{d|T} f_d \mu(\frac Td)

d\not = i时可以每算出一个f_i就更新所有F_x(i|x)

d=i时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m \\ f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}

这样就可以先算f_i,再算F_i

[d\not=i]这个条件只在T=i的时候才有限制

枚举到T=i,计算f_i时,F_x(x<i)都已经计算好了

F_i还少了f[i] \times \mu(1)

这正好是要剪掉的部分

avatar
zc
2020-06-04 07:29:00
查看原题

点击跳转

做这题之前可以看看[WC201]最大XOR和路径

可以考虑换个思路:

对于每一对点的每一位,有多少种方案能使该位的xor和为1

dfs求出1到各点x的任意一条简单路径xord_x,那么求xy的简单路径长度就是d_x ~ xor ~ d_y

dfs的过程中也可以顺便求出所有环的xor和,这些可以用来增广简单路径,我们将这些环的xor和插入到线性基中

若线性基中有cnt个非零位,则一共会产生2^{cnt}个不同的xor

到了这一步,通过枚举两个点来统计路径的复杂度仍然是O(n^2 \cdot 60)的,我们要采用更高效的方法

直接讨论d_x对答案的贡献

先统计出第k位为0的数的个数,我们将其记为x,再统计出第k位为1的数的个数,记为y,总共有point个点

  1. d_x的第k位为1,线性基中有第k位为1的数: 此时我们有两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总体对于答案的贡献为:2^k\cdot 2^{cnt-1}\cdot (point-1),减1就是为了把自己给去掉。
  2. d_i的第k位为1,线性基中没有第k位为1的数: 这个时候另一个点只能取第k位为0的,, 所以总贡献为: 2^k\cdot 2^{cnt}\cdot x

  3. d_i的第k位为0,线性基中有第k位为1的数: 一样的,, 两种选择:

    • 选线性基中的,另一个点选择第k位为0的。
    • 不选线性基中的,另一个点选择第k位为1的。总贡献为: 2^k\cdot2^{cnt-1}\cdot(point-1)
  4. d_i的第k位为0,线性基中没有第k位为1的数: 另一个点只能取第k位为1的,总贡献: 2^k\cdot 2^{cnt}\cdot y

avatar
zc
2020-03-23 16:44:00
查看原题

点击跳转

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,now为位置i的方案数

H_i\ge x,now=pre+\sum_{j=1}^i [S_j=S_i],这些位置是位置i-1不能满足而位置i可以满足的

H_i\le x,now=pre-\sum_{j=1}^i [S_j=S_{i-1}],这些位置是位置i不能满足而位置i-1可以满足的

这样就可以\Theta(n)解决了呢

记得开long long,S_0先赋值为n,防止负数re

avatar
zc
2020-01-21 10:36:00
查看原题

点击跳转

设当前区间为[l,r]

res=\sum_{i=l}^r p_i\times[\prod_{j=l,j!=i}^r(1-p_j)]

s_{[l,r]}表示\prod_{i=l}^r(1-p_i)

res=s_{[l,r]}\sum_{i=l}^r \frac{p_i}{1-p_i}

a_i=1-p_i,b_i=\frac{p_i}{1-p_i}

res=\prod_{i=l}^ra_i\sum_{i=l}^rb_i

假设现在区间变成了[l,r+1]

A=\prod_{i=l}^ra_i,B=\sum_{i=l}^rb_i

res'=A\times a_{r+1}(B+b_{r+1})

=A(a_{r+1}B+a_{r+1}b_{r+1})

=A(a_{r+1}B+p_{r+1})

res'>res,那么a_{r+1}B+p_{r+1}>B

1-p_{r+1}+\frac{p_{r+1}}B>1

\therefore B<1

那么对于每个l,只需要找到最远的r使\sum_{i=l}^rb_i<1

而这又具有单调性,那么\mathcal{O(n)}就可以解决了

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们可以第一次修改的时候就用第一个黑点建树,可以预处理出a_i表示i到根节点路径上点编号的最小值

我们考虑接下来将一个点x变为黑点对其他点的影响:

显然x变成黑点对它的子树内的点的答案没有影响

对子树外的影响:

子树外的点可以通过根到达x,可以记录一个值t表示根能到黑点的所有路径上值的点的最小编号

查询时答案就是\min(a_x,t)

自己画个图就懂了

avatar
zc
2020-01-04 10:21:00
查看原题

点击跳转

我们先预处理出L_i,R_i分别表示与a_i相同的数出现在i左边和右边的位置

我们可以使用分治来判断一个区间是否合法

我们设当前区间为[l,r]

从两边一起找

假设枚举到位置iL_i<lR_i>r,那么左端点在[l,i],右端点在[i,r]的区间都是"non-boring"

这时我们只需要判断区间[l,i-1][i+1,r]是否合法就可以了

复杂度可以降至\Theta(n \log n)

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

点击跳转

原本打算写dp的,但是仔细观察一下,只要第一个点确定了,后面的点也确定了

答案只有可能是0,1,2中的一种

(可能是我扫雷玩太少了)

1/2
Search
search