【P5657 [CSP-S2019] 格雷码】

P5657 [CSP-S2019] 格雷码

暴力50分

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
int n,k;
signed main()
{IOS;cin>>n>>k;vector<string> v;v.pb("0");v.pb("1");for(int j=1;j<=n-1;j++) {vector<string> vt;for(int i=0;i<(int)v.size();i++){vt.pb("0"+v[i]);}for(int i=(int)v.size()-1;i>=0;i--){vt.pb("1"+v[i]);}v = vt;}cout<<v[k];
}

正解

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) 
#define int long long
#define PII pair<int,int> 
#define pb push_back
using namespace std;
const int N = 1e6+5;
unsigned long long n,k;
signed main()
{IOS;cin>>n>>k;__int128 sum = (__int128)pow(2,n);int pre = -1;while(1){if(pre==-1){if(k<=sum/2-1){cout<<0;pre = -1;}else{cout<<1;pre = 1;k -= sum/2;}	}else{if(k<=sum/2-1)//k下标从1开始 {cout<<1;pre = -1;}else{cout<<0;pre = 1;k -= sum/2;}}sum /= 2;if(sum==1) break;}
}