Kattis bitwise-思维

题目链接

Kattis bitwise

思路

这道题就是求循环序列的分成k部分的和的最大值，我们考虑从高位到低位，如果高位可行就加入答案，然后把答案带入下一个需要验证的位中进行一起验证即可，因为是循环2n的序列，只要能分成2k-1分即可，因为中间有一份可能会连接起来使得总的部分少一份。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 5e5+10;
int a[N*2];
int main(){
   int n,k;
   scanf("%d %d",&n,&k);
   for(int i=0;i<n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
   ll ans=0,now=0;
   for(int num=(1<<30);num>=1;num>>=1){
   	now = 0;
   	int cnt = 0;
   	for(int i=0;i<n*2;i++){
   	now|=a[i];
	if((now&(ans|num))==(ans|num))
	cnt++,now=0;
	}
	if(cnt>=k*2-1)ans|=num;
   }
   printf("%d\n",ans);
}```