zcmimi's blog

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

avatar
zc
2020-04-28 17:21:00
查看原题

点击跳转

可以发现答案是递减的

每个q_i相当于破坏掉[1,q_i]的最大值

那么我们把[1,q_i]区间-1

将最大值变为p_k的时候,相当于[1,k]的最大值都变成了p_k

那么把[1,k]区间+1

每次询问的时候,一直将当前最大值-1,应用变化,直到区间最大值大于0,输出答案

具体看代码

avatar
zc
2020-04-28 00:27:00
查看原题

点击跳转

首先把连接所有i\rightarrow p_i,可以得到若干个环

kp_i=p_{p_i}后会让i指向环上从i数起的k+1个点

只需要让一个环满足条件既可以,我们可以对每个环分别处理,然后答案取\min

可以发现假设一个环长度为l,若k可行,那么\gcd(k,l)也是可行的

我们判断是否存在0\le t < \gcd(k,l),使环上所有模\gcd(k,l)等于t的点的颜色都相同就可以了

avatar
zc
2020-04-27 17:49:00
查看原题

点击跳转

可以发现,这条链必然经过每个给定点的父亲

把每个给定点都变成它的父亲

按深度排序

依次判断接下来的节点是否在上一个的子树中即可

avatar
zc
2020-04-27 12:37:00
查看原题

点击跳转

很妙的构造题

首先,可以发现异或和明显不大于总和

第二,如果异或和与总和的奇偶不同,那么无解(二进制下最低位不同,没法用进位来填充)

剩下的就都可以构造了

u=v的时候,输出u就可以了,当u=0的时候记得特判

x=\frac{u+v}2

那么\left\{x,x,u\right\}就一定可以满足

如果x \And u=0的时候\left\{x,u\right\}等价于\left\{x+u\right\}

那么\left\{x,x+u\right\}可以满足

avatar
zc
2020-04-26 21:16:00
查看原题

点击跳转

首先我们可以只保留每个数奇数次幂的因子

第二,根据约数个数定理,因为每个数的约数不超过7,所以最多只有两个质因子

可以把选择一个数看成在这两个质因子之间的连边

如果只有一个,那么把1作为另一个质因子

于是我们得到一张图

乘积为完全平方,也就是每个质因子都是偶数次幂,那么再最终的图中它的入度为偶数

那就是说我们要找这个无向图中的最小环

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

f_{i,j}表示前i个点,第i个点的覆盖状态为j(j8位二进制数)

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

两次dfs即可

第一次dfs:

计算出每个点的子树,包含这个点,答案最大是多少

显然S_x=v_x+\sum\limits_{y\in son_x} [S_y>0]S_y

(若x为黑点v_x=-1,否则v_x=1)

第二次dfs:

通过x的父亲的答案来计算出x的答案

如果x目前的答案>0,则从x的答案减去x目前的答案

如果这个结果>0,那么x的答案加上这个结果

感觉直接看代码可能更直观

avatar
zc
2020-04-26 14:01:00
查看原题

点击跳转

建立新数c,使c_i=a_i-b_i

那么就是要找多少对i<jc_i>c_j

c排序,然后双指针统计一下就可以了

avatar
zc
2020-04-26 01:05:00
查看原题

点击跳转

首先,确定最大值和唯一一对的相同的元素

这对元素分别放在最大值的左边和右边

剩下的n-3个元素,有两种选择:

  1. 放在最大值左边
  2. 放在最大值右边

那么就有2^{n-3}种方案

[1,m]中选取n-1个不相同的元素,有m \choose {n-1}种方案

接着在这n-1个元素中选取一个非最大值的元素作为唯一相同那一对,有n-2种方案

那么最终答案就是2^{n-3} \times {m \choose{n-1}} \times (n-2)

avatar
zc
2020-04-25 19:52:00
查看原题

点击跳转

看到n\le 500容易想到是区间dp

f(i,j)[i,j]合并后的最小长度,w(i,j)为合并后的和

f(i,j)=\min\left\{ f(i,k)+f(k+1,j)\right\}

f(i,k)=f(k+1,j)=1w(i,k)=w(k+1,j)时,合并即可

13/66
Search
search