CF1988C#

题意简述#

给定一个正整数 $n$ ，要构造出一个长度为 $k$ 的严格递增序列 $a$ ，且每一项 $a_i\le n$ 。要满足 $a_i|a_{i-1}=n$ 。

题目分析#

要使得 $a_i|a_{i-1}=n$ ，我们不妨先找找规律：

当 $n=14$ 时，可以构造出以下数据：

$a_1=6$

$a_2=10$

$a_3=12$

$a_4=14$

将其转化为 二进制：

$0110$
$1010$
$1100$
$1110$

通过观察此数据，可以发现，构造出的数字的二进制存在规律，即将 $n$ 从末位开始将每个 $1$ 都去除一次，这样可以使得相邻两个数的异或值都为 $n$ 。

Code#

1
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
 #define MULTI_CASES
8
const int MaxN = 2e5+100;
9
const int INF = 1e9;
10
int T=1, N, M;
11
int a[MaxN];
12
int Atoi(string s,int radix)    //s是给定的radix进制字符串
13
{
14
  int ans=0;
15
  for(int i=0;i<s.size();i++)
16
  {
17
    char t=s[i];
18
    if(t>='0'&&t<='9') ans=ans*radix+t-'0';
19
    else ans=ans*radix+t-'a'+10;
20
  }
21
  return ans;
22
}
23
//n是待转换的十进制数，m是待转换成的进制数
24
string intToA(int n,int m){
25
  string ans="";
26
  do{     //使用do{}while()循环类型以防止输入为0的情况
27
    int t=n%m;
28
    if(t>=0&&t<=9)
29
      ans+=(t+'0');
30
    else
31
      ans+=(t+'a'-10);
32
    n/=m;
33
  }while(n);
34
  reverse(ans.begin(),ans.end());
35
  return ans;
36
}
37

38
inline void Solve()
39
{
40
  cin>>N;
41
//  char s1[MaxN];
42
  string s;
43
  s=intToA(N,2);
44

45
  M=1;
46
//  cout<<s<<endl;
47
  for(int i=0;i<s.size();i++){
48
    if(s[i]=='1'){
49
      M++;
50
    }
51
  }
52
  if(M==2){
53
    cout<<1<<endl<<N<<endl;
54
    return;
55
  }
56
  cout<<M<<endl;
57
  for(int i=0;i<s.size();i++){
58
    if(s[i]=='1'){
59
      string str=s;
60
      str[i]='0';
61
      cout<<Atoi(str,2)<<" ";
62
    }
63
  }
64
  cout<<N<<endl;
65
//  cout<<endl;
66
//  cout<<s<<endl;
67
}
68
signed main()
69
{
70
#ifndef ONLINE_JUDGE
71
  freopen(".in", "r", stdin);
72
  freopen(".out", "w", stdout);
73
#endif
74
  ios::sync_with_stdio(0);
75
  cin.tie(0),cout.tie(0);
76

77
#ifdef MULTI_CASES
78
  cin >> T;
79
  while (T--)
80
#endif
81
    Solve();
82
  //fclose(stdin);
83
  //fclose(stdout);
84
  return 0;
85
}