Code Chef JUNE Challenge 2019题解

\(SUMAGCD\)

先去重，易知答案一定是一个数单独一组剩下的一组，前缀后缀\(gcd\)一下就行了

//quming
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=1e5+5;
int a[N],suf[N],Pre[N],n,T,mx;
int main(){
    for(scanf("%d",&T);T;--T){
        scanf("%d",&n),mx=0;
        fp(i,1,n)scanf("%d",&a[i]);
        sort(a+1,a+1+n),n=unique(a+1,a+1+n)-a-1;
        if(n==1){printf("%d\n",a[1]<<1);continue;}
        Pre[0]=0;fp(i,1,n)Pre[i]=__gcd(a[i],Pre[i-1]);
        suf[n+1]=0;fd(i,n,1)suf[i]=__gcd(suf[i+1],a[i]);
        fp(i,1,n)cmax(mx,a[i]+__gcd(Pre[i-1],suf[i+1]));
        printf("%d\n",mx);
    }
    return 0;
}

\(CHFING\)

\(1\)到\(k-1\)肯定\(gg\)，剩下的放到模\(k\)意义下，共有\(k\)个点，然后\(n-1\)条边，第\(i\)条边可以从\(c\)到\((c+k+i)\%k\)，设\(dis_c\)表示到\(c\)点的最短路，那么\(dis_c+p\times k\)都是能被标识的，剩下的不行。然后再仔细讨论一下就行了

//quming
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
int T,res,p;ll n,k;
const int P=1e9+7;
inline int calc(R int x){return (1ll*x*(x+1)>>1)%P;}
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
    R int res=1;
    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
    return res;
}
int main(){
    for(scanf("%d",&T);T;--T){
        scanf("%lld%lld",&n,&k),p=(k-1)/(n-1)%P,n%=P,k%=P;
        res=add(mul(calc(p),n-1),mul(p+1,dec(k-1,mul(p,n-1))));
        res=add(res,P);
        printf("%d\n",res);
    }
    return 0;
}

\(LENTMO\)

分情况讨论，如果\(k=n\)只有操作或不操作，如果\(k\)为奇数等价于\(k=1\)，为偶数等价于\(k=2\)

//quming
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],k,n,x,T;ll res,mx,sum[N];
int main(){
    for(scanf("%d",&T);T;--T){
        scanf("%d",&n),mx=res=0;
        fp(i,1,n)scanf("%d",&a[i]);
        scanf("%d%d",&k,&x);
        fp(i,1,n)res+=a[i],a[i]=(a[i]^x)-a[i];
        sort(a+1,a+1+n);sum[n+1]=0;
        fd(i,n,1)sum[i]=sum[i+1]+a[i];
        if(k==n)cmax(mx,sum[1]);
        else if(k&1)fp(i,1,n)cmax(mx,sum[i]);
        else for(R int i=n-1;i>0;i-=2)cmax(mx,sum[i]);
        printf("%lld\n",res+mx);
    }
    return 0;
}

Code Chef JUNE Challenge 2019题解

原文：https://www.cnblogs.com/yuanquming/p/11116926.html