欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Kattis bitwise-思维

程序员文章站 2022-04-01 20:39:30
...

题目链接

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);
}```

相关标签: 训练