CF 题目集锦 PART 3 #262 div 2 D_html/css_WEB-ITnose

【#262 div 2 d. little victor and set】

【原题】

D. Little Victor and Set

time limit per test

memory limit per test

input

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

1210 11

input

8 30 7

output

0514 9 28 11 16

Note

Operation  represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

【题意】给定范围L和R，在这之间选P个不同的自然数，其中1

【分析】很显然的结论，K^(K+1)=1，其中K是偶数。当K>3时，我们可以选连续的4个自然数使异或和为0。（当然注意要特判R-L+1的大小）。当K=1时，就是L。当K=2时，显然只能构造异或为1的情况。

所有的推论都指向一个问题：当K=3的一般情况怎么做?

猫眼课题宝

5分钟定创新选题，3步生成高质量标书！

85

查看详情

【题解】对于那个情况，我一直觉得能贪心构造，但是怎么也想不出简单易行且效率高的算法。

其实很简单。我们设L

在二进制中，异或和为0的情况是1,1,0或0,0,0。显然Z的第一位是1，然后X和Y是0。

因为是贪心，我们要尽量使Y靠近Z（因为如果Z符合范围，Y显然越大越好）。

那么第二位我们就让Y靠近Z。我们把Z那位设成0，X和Y都设成1，即如下形式：

110000000

101111111

011111111

为了少特判，我在R-L+1小的时候直接暴力寻找。

【代码】

#include<cstdio>#include<algorithm>#include<iostream>#define E endl#define INF 999999999999999ll#define RE return 0using namespace std;typedef long long LL;LL len,sum,ans,C,wri[15],temp[15],i,S,L,R,k,x,z;inline void DFS(LL now,LL C,LL sum){  if (now==R+1)   {    if (sum>=ans||!C) return;len=C;ans=sum;    for (int i=1;i<=C;i++) wri[i]=temp[i];    return;  }  if (now>R) return;  DFS(now+1,C,sum);if (C+1>k) return;  temp[C+1]=now;DFS(now+1,C+1,sum^now);}int main(){  cin>>L>>R>>k;  if (L==R) {cout<<L<<E<<1<<E<<R;RE;}  if (R-L<=8)   {    ans=INF;DFS(L,0,0);cout<<ans<<E<<len<<E;    for (i=1;i<=len;i++) cout<<wri[i]<<' ';RE;  }  if (k>3)  {    S=(L&1)?L+1:L;    cout<<0<<E<<4<<E<<S<<' '<<S+1<<' '<<S+2<<' '<<S+3;RE;  }  z=3;x=1;  while (z<=R&&k==3)  {    if (x>=L) {cout<<0<<E<<3<<E<<x<<' '<<z-1<<' '<<z;RE;}    x=x<<1|1;z<<=1;  }  if (k==2||k==3)   {    S=(L&1)?L+1:L;    cout<<1<<E<<2<<E<<S<<' '<<S+1;RE;  }  if (k==1||k==3) {cout<<L<<E<<1<<E<<L;RE;}  return 0;}