zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

点击跳转

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

点击跳转

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

点击跳转

直接做可能想不出

我们可以逆着想

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

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

点击跳转

44/73
Search
search