2019.10.23题解

A. Smooth

标签:

队列

题解:

直接口胡一下算法过程吧:

开B个队列,先在第一个队列里加入1,之后每次取出这B个队列里最小的数x,

x便为最小的光滑数,i从小到大枚举并用x*p[i]更新第i个队列,

为了不重复,要用每个数的最小质因子更新即当p[i]|x停止,

因为x一定比上次取出的y要大,所以可以保证每个队列都是单调的,

复杂度$ O(BK) $

B. Six

标签:

记忆化搜索

题解:

设f[i][j]代表已选的质因子集合为i,出现在两个不同的数里的质因子对集合为j的方案数,

记忆化搜索即可,状态数很少,手测的一些大点状态数大概3263个

C. Walker

标签:

随机化

题解:

题目中保证正确的数严格大于一半,所以考虑random两个数求出一组解之后回带check,

每次出错的概率是0.75,100次之后错的概率就是3e-13,足以通过本题

原文地址:https://www.cnblogs.com/AthosD/p/11730075.html