题目翻译

我们定义前缀或的意思是 $or_i=or_{i-1} \operatorname{or} a_i$。

重排数组 $a$，使得它的前缀或数组的字典序最大。

题目思路

通过观察和思考可得，第一位一定放 $\max\limits_{1\leq i\leq n}\{a_i\}$ 才能让第一位最大，接着保证字典序最大。

那么我们考虑，对于之后每一位的答案，我们都去和前面的进行比较，看看哪一个才是这一位该放的最大的答案。这一点是很容易想到的。

那么这只是 $\mathcal O(n^2)$，很显然是会超时的。

我们考虑到，一个 int 类型只有 $32$ 位，那么我们只要知道这 $32$ 位能不能放上 $1$ 即可。

也就是说，如果这 $32$ 位都决策完了，我们不用继续找，后面没用过的可以直接输出。

所以我们只要判断当前操作下来的答案，和上一步操作的答案是否相同，若相同即可结束。

完整代码

#include<bits/stdc++.h>
using namespace std;
void solve()
{	
	vector<int>ans;
	int n,maxx=-1,id;
	cin>>n;
	int a[n+1];
	int tmp[n+1];
	bool f[n+1]={};
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		tmp[i]=a[i];
		if(a[i]>maxx)
		{
			maxx=a[i];
			id=i;
		}
	}
	f[id]=1;
	ans.push_back(maxx);
	int last=maxx;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			tmp[j]|=maxx;
		}
		last=maxx;
		maxx=0;
		for(int j=1;j<=n;j++)
		{
			if(!f[j])
			{
				if(tmp[j]>maxx)
				{
					maxx=tmp[j];
					id=j;
				}
			}
		}
		f[id]=1;
		ans.push_back(a[id]);
		if(maxx==last)
		{
			for(int j=1;j<=n;j++)
			{
				if(!f[j])
				{
					ans.push_back(a[j]);
				}
			}
			break;
		}
	}
	for(int i:ans)
	{
		cout<<i<<" ";
	}
	cout<<endl;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
	return 0;
}

链接