D. Little Victor and Set
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:
- for all x
the following inequality holds l ≤ x ≤ r;
- 1 ≤ |S| ≤ k;
- lets denote the i-th element of the set S as si; value
must be as small as possible.
Help Victor find the described set.
Input
The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).
Output
Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.
If there are multiple optimal sets, you can print any of them.
Sample test(s)
input
8 15 3
output
1 2 10 11
input
8 30 7
output
0 5 14 9 28 11 16
题意：给出l,r，选出一个集合元素<=k的集合，且不能有重复的数，使得集合所有数的异或值最小
思路：这应该算是一道规律题
1. k=1，则答案为l
2. k=2，如果可以选择一奇一偶，这里偶数比奇数小1，则答案为0，否则选择l和l^r中较小的一个
3. k=4，如果可以选择四个连续的数，使得最小的一个数为偶数，则答案为0，否则转k=3或k=2或k=1处理
4. k=3，找出形如 11xxxx，10zzzz，01yyyy，这里10zzzz=11xxxx^01yyyy，基于贪心的思想可以将01yyyy取为l，算出11xxxx<=r，则答案为0，否则转k=2或k=1处理
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll l,r,k;
ll a[1000010];
int d1;
struct node{
ll w;
ll b[5];
int cnt;
};
node b[20];
ll c[5];
bool cmp(node a,node b)
{
return a.wr){
if(!cent)return;
b[d1].cnt=cent;
for(int i=0;i>l>>r>>k)
{
ll ans,x;
int d=0,i,j;
if(k==1){
ans=l;
a[d++]=l;
}
else{
if(r-l<4){
d1=0;
dfs(l,r,0,0);
sort(b,b+d1,cmp);
for(i=0;i=4){
for(x=l;x<=r;x++)if(x%2==0)break;
ans=0;
a[d++]=x;
a[d++]=x+1;
a[d++]=x+2;
a[d++]=x+3;
}
else {
ll now=l;
int bi=0;
while(now){
now>>=1;
bi++;
}
now=3;
while(--bi)now<<=1;
if(now<=r){
ans=0;
a[d++]=now;
a[d++]=now^l;
a[d++]=l;
}
else {
for(x=l;x<=r;x++)if(x%2==0)break;
ans=1;
a[d++]=x;
a[d++]=x+1;
}
}
}
}
cout<