题目

输入n,构造长度为$2^n-1$的序列,使得下面在这个式子的值最小

方法:每组相邻元素最好二进制中只有一位不一样

打表结果:

1
2
3
4
n=1  0 1
n=2  0 1 3 2
n=3  0 1 3 2 6 7 5 4
     1 0 2 3 7 6 4 5

所以暴力或者按结论使用格雷码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int m = 1 << n;
    for (int i = 0; i < m; ++i) {
        cout << (i ^ (i >> 1));
        if (i < m - 1) cout << ' ';
    }
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ll n; cin>>n;
  set<ll> s;
  s.insert(0);
  cout<<"0 ";
  ll last=0;
  for(int i=1;i<=(1ll<<n)-1;i++){
    for(int j=0;j<=18;j++){
      ll next;
      if((last>>j)%2==0){
        next=last+(1ll<<j);
      }
      else{
        next=last-(1ll<<j);
      }
      if(s.find(next)==s.end()){
        cout<<next<<" ";
        s.insert(next);
        last=next;
        break;
      }
    }
  }
  cout<<endl;