F-同位序列_牛客周赛 Round 76

Round76比较简单，最后一题不涉及到什么算法，就是道模拟题，wa了几发最后还是让我混过去了🤭。其实就是一个规律：将整数二进制中第一次出现零的位置pos0且在这个位置之前出现了1(位置为pos1，同时这个1要是离这个0最近的1)，那么在pos1之前的所有1都要放到低位去。例如88=(1011000)2 ——> g(88)=97=1100001。所以我们只需要求pos0,pos1,和pos1之前出现了几个1，并将他们转换为十进制来计算。

Code:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<unordered_map>
#define int long long
using namespace std;const int N = 1e5+5;
//1 0 1 0  
int a[N],n,cnt,maxd,ans;
unordered_map<int,int> mp,st;
vector<int> v[N];
void js(int x)
{int sum=0;// cout<<"------"<<x<<endl;while(1){sum++;int one=0,sum1=0,sum2=0;st[x]=1;v[cnt].push_back(x);if(sum>maxd) ans=cnt,maxd=sum;int t1=0,t2=0;for(int i=0;i<=32;i++){if(((x>>i)&1)){if(one)sum2+=(1<<(one-1));one++;sum1+=(1ll<<i);t1=(1ll<<i);}if(!((x>>i)&1)&&t1){t2=(1ll<<i);break;}}int tt=x-sum1+t2+sum2;//cout<<tt<<endl;if(mp[tt]){x=tt;}else break;}  
}
//1011000
int32_t main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=1;}sort(a+1,a+n+1);for(int i=1;i<=n;i++){if(!st[a[i]]){cnt++;js(a[i]);}}cout<<maxd<<endl;for(auto t:v[ans]) cout<<t<<' ';
}