【Xor】

注:本题需要Special Judge

 

【问题描述】

请从区间[l,r]中取出不超过k个正整数,使得他们的异或和最小。

【输入格式】

输入文件的第一行有一个正整数T,代表数据组数。

接下来T行,每行三个正整数li,ri,ki。

【输出格式】

对每一组数据,你需要向输出文件中输出两行。

第一行包含两个整数x,n(1<=n<=k),分别表示你选的数的异或和以及个数。

第二行包含n个正整数,即你选的数。你不可以选相同的数。

【输入样例】

2

5 9 3

1 1000000000000000000 100000

【输出样例】

1 2

6 7

0 8

108 334 512 169 474 338 493 750

【数据范围】

T≤10000 l≤10的18次方 r≤10的18次方 k≤min(r-l+1,10的6次方)

不要被数据范围吓到了,其实这道题只要搞清楚k的影响就行了。

k=1 答案显然就是l

k=2 注意到如果x是一个偶数,那么x^(x+1)=0此时又分三种情况

I r=l+1 此时答案为min(l,l^r)判断输出即可。

II r>l+1 此时答案一定为1,如果l是偶数输出l l+1即可;如果l是奇数,那么输出l+1 l+2即可。

k=3最蛋疼的一种情况。答案不会超过1,因为从[l,r]中能选2个数使得答案为1,我们关心异或和为0的情况。

首先,这三个数的最高位不可能相同(否则异或起来的最高位为1,比如101^111^100,第三位变成1显然不是最优解)设这三个数分别为x,y,z(x<y<z)且y=2^k+b,z=2^k+c,b<c,那么x^b^c=0(x把剩下位异或掉了,然后y和z都是由2^k组成一异或就变成0了)为了让l<=x<y<z<=r我们需要使得x尽量大而c尽量小,设x≥2^(k-1)可以推得z≥2^(k-1)+2^k,为了满足x尽量大而c尽量小,令x=2^k-1(刚好比b=0时取得的y小)z=2^k+2^(k-1)可得y=z-1满足条件。

如果x<2^(k-1),我们可以发现,此时z没必要≥2^k,因为取上述y=2^(k-1)+b,z=2^(k-1)+c依然满足条件。

所以枚举k并检查x y z是否符合条件即可。

如果x都≥r了还没有,那么就输出1 即转到k=2的情况。

k=4相对3来说比较简单,还是分两种情况

I r-l=3 此时枚举[l,r]的子集比较大小即可(我比较笨懒得写dfs直接手写了12种情况……选一个的情况肯定是选l最优,所以不用把l+1之类的纳入考虑)

II r-l>=4此时如果l是偶数,那么l^(l+1)^(l+2)^(l+3)=0,输出即可。如果l是奇数,那么(l+1)^(l+2)^(l+3)^(l+4)=0,输出即可。

k>4的情况显然可以归入k=4时的r-l>=4来讨论。

本题难点就在k=3的情况,好好想清楚异或的性质这道题难度也不是太高(虽然还是不简单!)

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*