USACO/humble

来自NOCOW

< USACO

跳转到：导航, 搜索

[编辑] 方法一

官方题解 by Russ Cox 译 by 逆铭

我们在数组hum中计算出前n个丑数。为了实现起来更简单，我们把1也作为一个丑数，算法也要因此略微调整一下。

当我们已知前k个丑数，想得到第k+1个，我们可以这样做：

对于每个质数p 寻找最小的丑数h 使得 h * p 比上一个丑数大

取我们找到的 h * p 中最小的一个：它就是下一个丑数为了使搜索更快，我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数，每次都从那里开始，而不是再从头再来。 (官方源码参见参考代码-C)

[编辑] 方法二

这道题可以用BFS+Treap来做。但这里的BFS不使用队列来扩展，而是用Treap来扩展。

建一个Treap保存已经得到的数，从小到大每次从堆中取出一个数，用它和集合中的质数相乘，查找判断它是否重复.如果没有重复，那么将它插入到Treap中。直到产生了n个数，那么再往后扩展一位，得到的第n个数既为所求的结果。时间复杂度：BFS扩展为O(N),查第k大为O(logN)判重为O(logN),插入为O(logN),因此总的复杂度为O(NlogN)

有谁用宽搜的方法写的..我的思路是每次从堆中取一个...然后从质数集合里扫一遍.... 虽然不能保证新扩展出的数的顺序...但很类似Astar...第n个开始扩展的节点可以确定复杂度应该为 nklogn 可惜内存不够开.... ..小岛

[编辑] 方法三

这道题目可以直接应用STL中的priority_queue来做，复杂度为O(NKlogN),对于第i小的数，扩充它能得到的所有新元素并插入priority_queue中，然后pop第ｉ小的数。时间没问题，但是空间会爆，当然只对于最后一个数据，我最后一个数据在自己机子上RUN完后，骗过去的，USACO上分配内存太小!

以上内存不够的问题：可以用最大最小堆，当队列里元素个数大于n就可以把最大的数删掉了。（但是我写的很残，TLE，无语。）

[编辑] 假想中的方法

读入数据数组a，然后对二取对数，存为数组b，然后把问题转化成装箱问题（求第n种b能组出的和，找出第n种），貌似需要离散化、位运算，我刚学，不懂，哪位神牛能帮我探究一下可行性？囧了,刚才试了一下,发现(ln(maxlongint)-ln(maxlongint-1))*maxlongint<1,也就是说当数达到一定程度的时候就无法精确到一了,我是发展不了我的创意了,谁能帮忙? ps一句,我是为了说这个方法才注册的,我是个小人物,我没有什么好办法用程序实现,新手不要尝试.

方法3可以的吧，因为只有前N个才是有用的

       for (int i = 0; i < num; i++) 
           if (a[i] <= m / x) a[num++] = a[i] * x;
       sort(a, a + num);
       if (num > n + 1) {
           num = n + 1;
           m = a[n];
       }

我这种很戳，最后一个0.9多

[编辑] 非常离谱和菜鸟性质的方法5（但它的确有一些效果，起码AC了）

USACO难得地把数据给得弱了——除了最后一个点素数量很大，其余的点素数量量都不大，<=10。

素数量不大的点，其在一定范围内丑数分布会相对密布，之后非常稀疏，如果有7个素数，1万以内有近1000个丑数，15万以内有3000个，408万内有10000多个，超过5*10^6之后，每10万个数中有20~50个丑数；素数量大的反而相对过于密布。（其实这比较符合我们的主观预感）

先列出菜鸟们能想到的所有办法：

1、对每个数进行暴力检查

（以下的构造的具体实现方法（定义）为：

按从小到大的顺序，对每一个确认是丑数的数，乘上每一个质数，记录下来）

2、构造每一个有效的数，当做开boolean数组的背包题（The Longest Prefix）来记录。

3、

原始：构造每一个有效的数，直接放到数组中。（缺点：查重很慢）

优化：构造每一个有效的数，用类似hash的链地址法来记录（数组模拟，取div一个10^5数量级的数作为其特征码，取mod相同的大数得到的数作为存到数组里的数）。

对于素数量小，且丑数值小于一定值（我取的大约有5*10^6）的数，我们可以只使用第2种构造方法。

对于素数量小，但是待求丑数值超过一定值的数，需要把2、3两种方法结合起来。（如果只使用第3种，除非用指针，否则MLE不可避免；但是，指针实际情况下差错太难了）

对于素数量大的情况，我们很高兴的看到，待求丑数值不大（最后一个点待求值只有30万不到，因为素数量大了，丑数密布，第100000个也不够大），那就直接用第1种暴力检查方法。【警告：不要用第二种或第三种！因为素数过多，而且丑数密布，上面的构造法只能因生成太多过大数和重复数而被拽慢了】

然后时间对菜鸟来说还是很令人满意的：

  Test 5: TEST OK [0.108 secs, 15640 KB]
  Test 6: TEST OK [0.594 secs, 15640 KB]（小素数量的最大点）
  Test 7: TEST OK [0.189 secs, 15640 KB]
  Test 8: TEST OK [0.108 secs, 15640 KB]
  Test 12: TEST OK [0.351 secs, 15640 KB]（大素数量，100个的点）

其实这种方法回头看看总体说说容易，具体实现就有一定的挑战性了（最后写了120行左右，还有一些很难看的语句）。

[编辑] 方法六

这题楼上N层全都想复杂了根本不需要那么多步骤直接一个set搞定每个数乘一边set内全部humble number 如果 size 比n大删掉最后一个数据如果当前humble number 比set最后一个大那么break; 全写出来不过40行只有最后一个点0.2s 其他全都是 0.0*s 秒杀的代码见 ID: useset

这道题我想了很多，只认同O(nk log n)的解法，但是最后一组数据超时，同上面骗过去以后，发现usaco数据中一个有趣的现象，所有的质数都是从2开始连续递增！！，这样造成的结果就是那些每次添加不止一个数据的算法也能通过.