Ai.Freedom

本文在署名-非商业性使用-相同方式共享 3.0版权协议下发布, 转载请注明出自aifreedom.com

Google PageRank终于更新了, 而半年的努力, 让我的Blog的PR上升到了3.

在这次更新中, 很多老牌的PR预测工具都失效了. 但aw推荐的一个新的预测PR的工具网站也还是很好用的:

http://www.dlls.info/

还有我找到的这个工具也不错:

http://www.knowsky.com/tools/pr/

最后, 给看到这里但不知到我在说什么的同学介绍一下Google PageRank:

PageRank是Google的两位创始人 拉里·佩奇 和 谢尔盖·布林 于1998年在斯坦福大学发明的一项用来统计互联网上页面重要程度的技术. 它的基本思想就是让网页利用链接给其他的网页投票, 被投得多的网页就会得到一个比较高的"PageRank值"(简称"PR值"). PR值越高的网页在互联网上的重要性也越大, 而Google在排列搜索结果里网页的顺序时也会参考这个页面的PR值. PR值被Google分为11个等级, 从0到10, 我的Blog首页目前的PR值是3.

本文在署名-非商业性使用-相同方式共享 3.0版权协议下发布, 转载请注明出自aifreedom.com

这题做了很久才最终AC, NOIP前就写过, 但当时没能通过自己写的样例. 后来很久没有做题, 直到最近才把这题做掉. 但做的过程中很郁闷, 所以来写个简单的解题报告.(不知道Ural是什么的请参见这里)

题目意思很好理解, 没有什么歧义, 思路也很容易想到. 首先, 用N(i)表示1..i的01序列中, 1的个数, 那么"a b even"表示N(a-1)和N(b)同奇偶, "a b odd"表示N(a-1)和N(b)不同奇偶. 那么很自然的会想到用并查集, 但怎么用就有学问了. 而且题中序列的长度太长, 且远大于询问次数, 要用到hash或者离散化(我一开始居然用离散化.. 硬是把O(n)的算法弄到了O(nlogn).. 晕..).

最初朴素的想法是将同奇偶的归到一个集合中, 并且在每个集合的根处记录下与这个集合奇偶性相反的集合标号. yuhch大牛也是这样做的, 但我在编程实现的过程中遇到了不少麻烦. 想找yuhch要来他的程序看看, 但他说他N年前AC的, 程序早就不在了..

改换思路, 在使用并查集的时候记录每个节点和它的父亲的奇偶性是否相同. 并且用到了xor运算的一些性质: xor的逆运算还是xor, 而xor运算的真值表有正好和整数奇偶性相同. 于是可以很好地降低编程复杂度.

你可以点击这里下载我已AC的源程序.