50求条
查看原帖
50求条
431095
Druid楼主2024/11/28 14:28

如题,longlong之前RE和T,改longlong以后莫名WA

//思路:尽量让高位为0。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[514191],max1;
bool vis[514191];
int pow2(int k)
{
	if(k==0)
		return 1;
	if(k==1)
		return 2;
	//int ans0=1;
	//if(k>=32) {ans0*=4294967296;k-=32;}
	//if(k>=16) {ans0*=65536;k-=16;}
	//if(k>=8) {ans0*=256;k-=8;}
	int ans1=pow2(k/2);
	return ans1*ans1*pow2(k%2);
}
signed main()
{
	int ans=0;
	cin>>n>>m;
	m--;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		max1=max(max1,a[i]);
	}
	int i=0;
	while(pow2(i)<=max1) i++;
	i--;
	int x;
	bool flag=0;
	for(; i>=0; i--) {
		x=0;
		flag=!((a[1]/pow2(i))%2);//表示能不能塞一个or
		for(int j=2; j<=n; j++) {
			x+=flag and !vis[j];//x统计塞or的数量
			if((a[j]/pow2(i))%2==1)
				flag=!flag;
		}
		if(x<m or !flag) {//如果能塞的or比m小或最终无论如何都有1
			ans+=1<<i;//当前位改为1
			continue;
		}
		flag=(a[1]/pow2(i)%2);//表示能不能塞一个or
		for(int j=2; j<=n; j++) {
			if(vis[j]==0)
				vis[j]=flag;
			if((a[j]/pow2(i))%2==1)
				flag=!flag;
		}
	}
	cout<<ans;
	return 0;
}
2024/11/28 14:28
加载中...