前不久，看到了个大新闻，有人提出了个的整数乘法算法。不过据说是理论意义大于实际意义。看到这个我就很奇怪了，使用FFT的整数乘法算法的时间复杂度之前难道不就是吗？然后我看到了知乎上相关的讨论，说以前的复杂度是。难道我一直都搞错了吗？经过一番研究后发现，这是由于我们对和运算的定义不同导致的。说复杂度为的，指的是二进制位的个数，其基本运算是二进制位的运算。而具体到我们的常见实现，我们通常采用十进制数下的...

阅读全文 »

最近点对问题是一个经典问题，目标是在n个点中找到距离最近的一对点。做法可以有很多，直接上KD-Tree都是可以的。但最常用的还是分治法。其主要思想很简单，就是把问题分成两个子问题，再进行合并。不过在这之前，我们要先对点按x排序。求解时先把一堆点平均分成两堆点，分别递归求解两堆点的最近点对，记为和，然后取。之后我们把横坐标距离中间点在范围之内的点取出来，找它们之间的最近点对，与取即可。不过这里面有个...

阅读全文 »

注意：这是一篇从旧博客恢复的文章。 原地址：http://freemeepo.com/acm/1410.html 归并树：在$$n\log n$$的时间内离线处理一个序列，在$$\log^3 n$$的时间查询[l, r]区间内的第K大数。 其原理就是利用归并排序+线段树。 记录下归并排序的过程，可以得到$$\log n$$个长度为$$n$$的序列，把这$$\log n$$个序列纵向展开，按照...

阅读全文 »

注意：这是一篇从旧博客恢复的文章。 原地址：http://freemeepo.com/blog/archives/112 如果有人问我数学有什么用，我一定会拿RSA算法甩他一脸。 今天下午无意中点开了RSA算法的资料，我决定把它搞清楚。以前我一直以为理解它需要很长时间，所以一直没看。今天学习了下，发现搞懂RSA的原理、看一些RSA的历史，总共也就花了我1个多小时的时间。看完之后不得不感叹这个...

阅读全文 »

注意：这是一篇从旧博客恢复的文章。 原地址：http://freemeepo.com/acm/1369.html 注：有更新 http://acm.timus.ru/problem.aspx?space=1&num=2004 2004. Scientists from Spilkovo Time limit: 0.5 second Memory limit: 64 MB Misha ...

阅读全文 »