zcmimi's blog

arrow_backdfs共24篇文章

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

点击跳转

求仙人掌直径

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

点击跳转

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

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

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

对子树外的影响:

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

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

自己画个图就懂了

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

点击跳转

先两次dfs找树的直径

emmmm, n \le 300 !!!

随便写好了

原来bzoj还有一道加强版,双倍经验多好

一定要在直径上取,而且距离不可以大于s,那么单调队列的思想不是可以吗?

因为离直径中点越近“贡献越大”

意会一下QwQ

这样下来代码量也很短 = ̄ω ̄=

而且可以ac bzoj的加强版

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

点击跳转

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

点击跳转

我们设学生1的债务为x

可以根据连边来计算出其他学生债务的表达式(ax+b)

如果出现矛盾,立即输出impossible并输出

最后可以求出x,并推出所有学生的债务

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

点击跳转

同树网的核

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

点击跳转

先预处理出所有幸运数字

当前要求的是[l,r]中的幸运数字

我们可以使用容斥,用[1,r]-[1,l-1]

假设当前幸运数字为x,[l,r]中是x的倍数的有\left \lfloor \frac rx \right \rfloor - \left \lfloor \frac lx \right \rfloor +1

[1,r],[1,l-1]中的幸运数字的倍数可能有交集

继续容斥:

选1个-选2个的lcm+选3个的lcm-...

剪枝:

  1. 可以发现,一个数是另一个合法倍数的倍数,那么这个数字相当于没用(因为被前面的统计过了),可以删掉

  2. 如果将幸运数字从大到小排序,搜索时可以更快突破边界

  3. 现在因为所有数都不满足是另外一个数的倍数,所以合并任意两个数的时候,lcm的最小情况就是乘上一个3

    所以对于所有>r/3的合法数字,显然不能够和任何一个数合并了,所以这一部分可以拿出来直接提前算好

剩下的直接暴搜

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

点击跳转

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

点击跳转

把风铃看成一棵树

因为交换一根杆的两端不会影响它下面的子树的情况,所以可以采用分治+分类讨论

我们先预处理出最小深度和最大深度

如果差大于1,那么不满足要求

一个端点可以分成三种情况

  1. 都是最小深度

  2. 都是最大深度

  3. 两种都有

如果一根杆左右端点分别为0,10,22,1那么它就需要交换左右端点

如果左右端点都是2那么交换也没用,直接输出-1,结束程序

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

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

点击跳转

n\le 100,每个点都只能经过一次

当然直接dfs了

2/3
Search
search