Codeforces Global Round 1

shanxizeng
关注文章
TinyMind专栏频道

竟然又没掉？

A - Parity

先判断基数是奇数还是偶数，如果是偶数，其奇偶性显然只与个位的奇偶性相关，否则与所有数位的数的和的奇偶性相关。

#include<bits/stdc++.h>
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int b,k,a[Maxn];

int main() {
    read(b,k);
    for(int i=1;i<=k;i++) read(a[i]);
    if(b&1) {
        int zhy=0;
        for(int i=1;i<=k;i++) zhy+=a[i];
        if(zhy&1) puts("odd");
        else puts("even");
    }
    else
        if(a[k]&1) puts("odd");
        else puts("even");
    return 0;
}

B - Tape

贪心一下就好了，好像usaco上讲过的。

#include<bits/stdc++.h>
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,m,k,a[Maxn];
priority_queue<int,vector<int>,greater<int> > q;

int main() {
    read(n,m,k);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++) q.push(a[i+1]-a[i]-1);
    int ans=n;
    n-=k;
    while(n--) {
        ans+=q.top();
        q.pop();
    }
    printf("%d\n",ans);
    return 0;
}

C - Meaningless Operations

首先观察样例，可以发现0与另一个数字的gcd就是另一个数字，那么如果这个数的位不满，就一定可以选出来一个数与他的&为0，而^为所有位满的数。

如果满的话，可以发现异或就是减去这个数，而位与还是这个数，那么这个数如果就是那个数的约数，其gcd就是这个约数。那么就可以选择那个数的最大的约数即可。

#include<bits/stdc++.h>
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int q,x;

int main() {
    read(q);
    while(q--) {
        read(x);
        int sxz=1;
        while(sxz<=x) sxz<<=1;
        sxz--;
        if(x==sxz) {
            int flag=0;
            for(int i=2;i*i<=sxz;i++)
                if(sxz%i==0) {
                    flag=sxz/i;
                    break;
                }
            if(!flag) puts("1");
            else printf("%d\n",flag);
        }
        else printf("%d\n",sxz);
    }
    return 0;
}

D - Jongmah

很显然，如果是连着的三个超过了三个，那么一定就没有意义了，因为可以选三个相同的也能达到相同的效果，所以可以直接进行DP了。

#include<bits/stdc++.h>
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,m,x,a[Maxn],f[Maxn][3][3];

int main() {
    read(n,m);
    for(int i=1;i<=n;i++) {
        read(x);
        a[x]++;
    }
    for(int i=1;i<=m;i++) {
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++) {
                    if(j+k+l>a[i]) continue;
                    f[i][k][l]=max(f[i][k][l],f[i-1][j][k]+l+(a[i]-j-k-l)/3);
                }
    }
    printf("%d\n",f[m][0][0]);
    return 0;
}

E - Magic Stones

先差分，然后发现操作的本质就是交换两个数，具体可以参考题解。

#include<bits/stdc++.h>
#define qmin(x,y) (x=min(x,y))
#define qmax(x,y) (x=max(x,y))
using namespace std;

char gc() {
//  static char buf[100000],*p1,*p2;
//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;
    return getchar();
}

template<class T>
int read(T &ans) {
    T f=1;ans=0;
    char ch=gc();
    while(!isdigit(ch)) {
        if(ch==EOF) return EOF;
        if(ch=='-') f=-1;
        ch=gc();
    }
    while(isdigit(ch))
        ans=ans*10+ch-'0',ch=gc();
    ans*=f;return 1;
}

template<class T1,class T2>
int read(T1 &a,T2 &b) {
    return read(a)==EOF?EOF:read(b);
}

template<class T1,class T2,class T3>
int read(T1 &a,T2 &b,T3 &c) {
    return read(a,b)==EOF?EOF:read(c);
}

typedef long long ll;
const int Maxn=1100000;
const int inf=0x3f3f3f3f;
const ll mod=998244353;

int n,a[Maxn],b[Maxn];

int main() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) read(b[i]);
    if(a[1]!=b[1]||a[n]!=b[n]) {
        puts("No");
        return 0;
    }
    for(int i=1;i<n;i++) a[i]=a[i+1]-a[i],b[i]=b[i+1]-b[i];
    sort(a+1,a+n),sort(b+1,b+n);
    for(int i=1;i<n;i++) {
        if(a[i]!=b[i]) {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}
优质内容筛选与推荐>>
1、一款基于jquery固定于顶部的导航
2、关于SeleniumLibrary库导入PyCharm无法自动感知关键字的解决方法 （本人python版本3.6.4）
3、[LeetCode165] Compare Version Numbers
4、盗取你的帐户仅需一张图片
5、统计字母出现频率及其单词个数


长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消，“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字，当前共字 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字，当前共字

    发送中

    网络异常，请稍后重试

    微信扫一扫
    关注该公众号

    0 │ 收藏 │ 举报