Codeforces Round #262 (Div. 2) D
|
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:
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 Input
8 30 7 Output
0 Note
Operation |
题意：给出l,r,k，要从[l,r]中的数选出最多k个组成集合，使这些元素异或起来得到的结果最小，输出最小值和这些元素，若多解输出任意满足条件的解。
题解：分析，找到规律然后搞。
题目要求异或得的值尽量小，所以我们研究如何能异或得到小值。
可以发现如下规律：
1. 一个偶数和 它本身加一 异或，得1。（xxxxxx0 xor xxxxxx1 = 0000001）
2. 4的倍数和它背身加1 加2 加3 一共4个数异或，得0。（...00 xor ...01 xor ...10 xor ...11=0）
由上面两个规律，当k>=4的时候，我们找区间内有没有完整的4的倍数x, x+1, x+2, x+3，若有，则直接得0。若没有，则区间内元素个数肯定小于6，直接2^6暴力得到最优解。
若k==1，则直接返回l。
如k==2，则区间元素个数只要大于等于3，肯定能得1。两个不同的元素不可能异或得0，只有相同的两个才能异或得0，所以k==2最少也就是1了。如果区间只有l和r两个元素，l还是奇数，那就得不了1，最小异或结果就是min( l , l^r)，也就是单独L一个不异或和l异或r中比较小的。
然后就是比较难想的，k==3的情况了。
k==3是可以异或得到0的，这个情况也比较特殊，因为三个1异或是会得1的，所以不可能像上面连续找好几个数异或得0，因为连续的数高位是一样的，都是1的话就会异或得1。
所以我们要找的三个数，每位上需要有2个1或者0个1。像上面一样，我们尽量找接近的数，这样比较容易在区间中找到。
110000000
101111111
011111111
看这三个异或结果为0的二进制数，很接近了。如果区间内有3个数能异或成0，区间内肯定能找到形式为这样的3个数异或为0。具体证明比较复杂，我脑内反证了很久……我就不详细写了。
然后我们根据这个，知道l和r的二进制位数必须不一样才能组成这样的3个数（位数一样的话最高位都是1，肯定不能得0），我们可以用l的二进制位数来试一试，不行的话用l的位数加一试一试，就是看看这样构造出来的三个数是不是都在区间内。如果这两种位数都不行的话就不行了，行的话肯定在这两种位数里有答案。
k==3这部分的代码：
if(k==) {
int lwei,rwei;
lwei=;
rwei=;
ll t=l;
while(t)t>>=,lwei++;
t=r;
while(t)t>>=,rwei++;
if(rwei>= && lwei<rwei) {
ll q[];
for(i=lwei+-; i<=lwei+-; i++){
q[]=(3LL<<i);
q[]=q[]-;
q[]=(1LL<<(i+))-;
bool dou=;
for(int j=;j<;j++)
if(q[j]<l || q[j]>r){dou=;break;}
if(dou)continue;
v.pb(q[]);
v.pb(q[]);
v.pb(q[]);
return ;
}
}
}
全代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) prllf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back ll l,r,k;
vector<ll>v; ll b[],bn;
ll c[],cn,miny;
void dfs(ll x,ll y,int cnt) {
if(cnt>k)return;
if(x>r) {
if(cnt!= && y<miny) {
cn=bn;
int i;
REP(i,bn)c[i]=b[i];
miny=y;
}
return;
}
b[bn++]=x;
dfs(x+,y^x,cnt+);
bn--;
dfs(x+,y,cnt);
} ll farm() {
ll i;
v.clear();
if(k==) {
v.pb(l);
return l;
} if(k>=) {
ll wa=(ll)(l/)*;
while(wa<l)wa+=;
if(wa+<=r) {
v.pb(wa);
v.pb(wa+);
v.pb(wa+);
v.pb(wa+);
return ;
}
bn=;
miny=1LL<<;
dfs(l,,);
REP(i,cn)v.pb(c[i]);
return miny;
} if(k==) {
int lwei,rwei;
lwei=;
rwei=;
ll t=l;
while(t)t>>=,lwei++;
t=r;
while(t)t>>=,rwei++;
if(rwei>= && lwei<rwei) {
ll q[];
for(i=lwei+-; i<=lwei+-; i++){
q[]=(3LL<<i);
q[]=q[]-;
q[]=(1LL<<(i+))-;
bool dou=;
for(int j=;j<;j++)
if(q[j]<l || q[j]>r){dou=;break;}
if(dou)continue;
v.pb(q[]);
v.pb(q[]);
v.pb(q[]);
return ;
}
}
} if(l==) {
v.pb();
return ;
} ll wa=((ll)((l+)/))*;
if(wa>=l && wa+<=r){
v.pb(wa);
v.pb(wa+);
return ;
}///区间内元素大于3的话肯定行，不然区间内只有l和r两个元素 if(l< (l^r)){
v.pb(l);
return l;
}else{
v.pb(l);
v.pb(r);
return l^r;
}
} int main() {
ll i;
scanf("%I64d%I64d%I64d",&l,&r,&k);
ll ans=farm();
printf("%I64d\n",ans);
ll maxi=v.size();
printf("%I64d\n",maxi);
if(maxi>)printf("%I64d",v[]);
for(i=; i<maxi; i++)printf(" %I64d",v[i]);
return ;
}
这道题我觉得是有点复杂，我比赛后还WA了好多次，细节没处理好。真没法在比赛中搞出来，真难玩，日后一定要碉。