CF問題集PART3 #262 div 2 D_html/css_WEB-ITnose

【#262 div 2 D. リトルビクターとセット】

【原题】

D. リトルビクターとセット

テストごとの制限時間

1 秒

メモリ制限テストあたり

256 メガバイト

入力

標準入力

出力

標準出力

小さなビクターは集合理論が大好きです。集合とは、すべての数字がペアごとに異なる数字のグループであることを思い出してください。今日、Victor は次の特性を持つ整数 S のセットを見つけたいと考えています:

すべての x に対して次の不等式が成り立ちます l?≤?x?≤?r;

1?≤?|S|?≤?k;

集合 S の i 番目の要素を si と表します。値はできるだけ小さくする必要があります。

Victor が説明されているセットを見つけるのを手伝ってください。

入力

最初の行には、スペースで区切られた 3 つの整数 l,?r,?k(1?≤?l?≤?r) が含まれています。 ?≤?1012; 1?≤?k?≤?min(106,?r?-?l?+?1)).

出力

f(S) の最小値を出力します。次に、set |S| の濃度を出力します。次に、セットの要素を任意の順序で出力します。

最適なセットが複数ある場合は、それらのいずれかを出力できます。

サンプル テスト

入力

8 15 3

出力

1210 11

input

8 30 7

Output

0514 9 28 11 16

注

演算は、ビット単位の排他的 OR の演算を表します。言い換えれば、それは XOR 演算です。

【分析】 K^(K+1)=1、K>3 の場合、連続する 4 つの自然数を選択できます。 (もちろん、R-L+1 の大きさに注意してください)。 K=1 の場合、L です。K=2 の場合、構築できるのは 1 または 1 の場合のみです。すべての推計は、ある問題に向けられています: K = 3 の一般的な状況でどのように実行されますか?

2 つの形式では、 または が 0 の場合は 1,1,0 または 0,0,0 になります。ただし、Z の最初の桁は 1 で、その後 X と Y は 0 になります。 Z の位置を 0 に設定し、X と Y を 1 に設定します。つまり、次の形式です:

110000000

101111111

011111111

可能性会議...

【代コード】

#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;}