zcmimi's blog

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

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
查看原题

点击跳转

直接做可能想不出

我们可以逆着想

我们倒着删边,然后连锁反应

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

点击跳转

我们假设现在要合并的两个数是x,y,那么合并后是x\cdot10^{\ln y+1}+y

我们可以预处理出 a_i \cdot 10^t \mod k(t\le 10)

每个a_i统计有多少个数接到它前面符合要求

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

点击跳转

m \le 5000

数据这么小,直接把边排序一下,然后暴力枚举,用kruskal就可以了

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

点击跳转

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

点击跳转

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

点击跳转

说实话,我觉得我是太傻吊了,一道动动脑筋就可以写的题我能写成麻烦的dp

dalao的代码:(直接扫描一遍就可以过了)

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

点击跳转

LG 4824 [USACO15FEB]Censoring"的做法hash,kmp什么的因为数据水所以跑不满可以水过去

还是练一下AC自动机吧

解释见代码

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

点击跳转

cnt数组记录每种数字出现的次数

我们只需要考虑add(x),del(x),其他的交给莫队

我们考虑当前数原本的答案是a_x \times cnt_x^2

现在变成a_x \times (cnt_x+1)^2

cnt_x =y

(y+1)^2 = y^2 + 2y +1

所以更新的时候ans += a_x \times (cnt_x \times 2 + 1)

37/66
Search
search