首页 > 代码库 > codeforces 460D Little Victor and Set（构造、枚举）
codeforces 460D Little Victor and Set（构造、枚举）
最近的CF几乎都没打，感觉挺水的一个题，不过自己仿佛状态不在，看题解才知道做法。
输入l, r, k (1 ≤ l ≤ r ≤ 1012; 1 ≤ k ≤ min(106, r - l + 1)).
从[l,r]选至多k个数使得选出的数的异或值最小，输出最小异或值和方案。
分类讨论，首先如果r-l+1<=4，枚举集合解决之。
先面讨论r-l+1>=5的情况：
此时有至少5个数可以选择，故至少有连续的4个数满足2x,2x+1,2x+2,2x+3。
k==1时显然方案为{l}。k==2时，显然方案为{2x,2x+1}。k>=4时，显然方案为{2x,2x+1,2x+2,2x+3}。
k==3时再另外考虑：
首先，异或值至多为1（参考k==2）
我们现在来找异或值可否为0。先假设可以，则显然是选3个数。不妨设x>y>z。
111...1111
111...1110
000...0001
显然x,y,z前半部分必定是如上这样的，但由于我们要使得x,y,z尽量靠近，所以x,y,z前半部分必然是如下
11
10
01
之后，每添加一位，有可能是yi=zi=1,xi=0或xi=zi=1,yi=0或xi=yi=1,zi=0。
由于要x,y,z尽量靠近，所以显然采取yi=zi=1,zi=0。
所以x,y,z的二进制形式如下
110...0
101...1
011...1
至此，问题大致解决，剩下的就是些细节问题，问题不大。
#include <cstdio>#include <cstring>#include <iostream>#include <vector>using namespace std;#define ll long longint cnt(int i){ int ret=0; while(i) i-=i&(-i), ++ret; return ret;}int main(){ ll l,r; int k; while(~scanf("%I64d%I64d%d",&l,&r,&k)){ if(r-l+1<5){ int n=r-l+1; ll ansxor=1ll<<60; vector<ll>val; for(int i=1;i<(1<<n);++i){ ll xx=0; for(int j=0;j<n;++j) if(i&(1<<j)) xx^=l+j; if(xx<ansxor && cnt(i)<=k){ ansxor=xx; val.clear(); for(int j=0;j<n;++j) if(i&(1<<j)) val.push_back(l+j); } } printf("%I64d\n",ansxor); printf("%d\n",val.size()); for(int i=0;i<val.size();++i) printf("%I64d%c",val[i],i==val.size()-1?‘\n‘:‘ ‘); } else if(r-l+1>=5){ if(k==1){printf("%I64d\n1\n%I64d\n",l,l);continue;} if(k==2){ if(l&1) l++; puts("1"); puts("2"); printf("%I64d %I64d\n",l,l+1); } else if(k>=4){ if(l&1) l++; puts("0"); puts("4"); printf("%I64d %I64d %I64d %I64d\n",l,l+1,l+2,l+3); } else if(k==3){ ll x=-1,y,z; for(ll i=3;i<=r;i=i<<1){ if((i^(i-1))>=l){ x=i; y=i - 1; z=i^(i-1); break; } } if(x!=-1){ puts("0"); puts("3"); printf("%I64d %I64d %I64d\n",x,y,z); } else { if(l&1) l++; puts("1"); puts("2"); printf("%I64d %I64d\n",l,l+1); } } } } return 0;}
codeforces 460D Little Victor and Set（构造、枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。