zcmimi's blog
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)时,合并即可

avatar
zc
2020-04-25 16:51:00
查看原题

点击跳转

枚举右端点r,当前颜色x

lst_x为颜色x上一次出现的位置

假设我们已经得知了f(l,r-1),l\in [1,r-1]

那么f(l,r),l\in [lst_x+1,r]=f(l,r-1)+1

也就是说我们把[lst_x+1,r]区间+1就可以了

于是这题就变成了线段树(或树状数组)维护区间平方和

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

点击跳转

avatar
zc
2020-04-23 14:02:00
查看原题

点击跳转

线段树分治+LCT

一个非常暴力的思路

FBI WARNING: 极有可能因为常数巨大而超时

把询问(修改)时间看成序列,每条边在这个序列上的一段区间出现

20/73
Search
search