Posts match “ 好题 ” tag:

http://codeforces.com/contest/460

D题 Little Victor and Set

构造。
关键在于两个相邻元素的异或可能会很小。
当集合中有两个元素时,答案可能是l^(l+1),但l=1011时就不太合适,这种情况下(l+1)^(l+2)就更好,此时异或为1。
当集合中有四个元素时,可能出现异或为0的情况,也要考虑,方法与有两个元素时类似。
当集合中有三个元素时,唯一可以使异或为0的构造是找到一个大于l的2^k数,令其为x。
此时异或的结果已经达到最小,更大的集合大小就不用考虑了。
比如x=10000,那么
x-1=1111,
x+x/2=11000,
x+x/2-1=10111。
此时三者异或恰好为0,并且这组数恰好是所有三元组中最大数(这里为x+x/2)最小的。

附代码:

继续阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4630

比较能体现离线威力的一道题。
为了方便使用树状数组维护区间最值,我们从右往左遍历 a 数组,这样查询也要根据 l 从大往小排序。
对于 a[i] 这个数,对它的每个因子 m,我们找一个在 a[i] 右边的,离 a[i] 最近的,且同样有因子 m 的数,其下标为 j,则更新树状数组 j 位置的最值为 m。
为什么找最近的?因为离线查询按照 l 排序后有个天然的包含关系
然后用树状数组查询区间最值就行。

继续阅读