【Codeforces】Round #488 (Div. 2) 总结

比较僵硬的一场，还是手速不够，但是作为正式成为竞赛生的第一场比赛还是比较圆满的，起码没有FST，A掉ABCD，总排82，怒涨rating两百

A：Fingerprints

A题，就在第一个串中查找第二个串中的数字，最气的是一开始没编译直接交CE了，噗

#include<iostream>

#include<cstdio>

using namespace std;

int read(){

    int ans=0,w=1;char c=getchar();

    while(!isdigit(c)&&c!='-')c=getchar();

    if(c=='-')c=getchar(),w=-1;

    while(isdigit(c))ans=ans*10+c-'0',c=getchar();

    return ans*w;

}

#define N 20

int a[N],b[N];

int main(){

    int n=read(),m=read();

    for(int i=1;i<=n;i++)a[i]=read();

    for(int j=1;j<=m;j++)b[j]=read();

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++)

            if(a[i]==b[j]){

                cout<<a[i]<<" ";

                break;

            }

    }

    return 0;

}

B：Knights of a Polygonal Table

B题，照样是手速题，按照能力值排一个序，然后可以用小根堆维护一下当前可以获得的最大价值，然后记录一下就好

#include<bits/stdc++.h>

using namespace std;

#define LL long long

LL read(){

    LL ans=0,w=1;char c=getchar();

    while(!isdigit(c)&&c!='-')c=getchar();

    if(c=='-')c=getchar(),w=-1;

    while(isdigit(c))ans=ans*10+c-'0',c=getchar();

    return ans*w;

}

#define N 100010

struct Node{

    LL p,c,id,ans;

}a[N];

LL n,k,ans[N];

priority_queue<LL,vector<LL>,greater<LL> > q;

bool cmp(Node a,Node b){

    return a.p<b.p;

}

bool cmp2(Node a,Node b){

    return a.id<b.id;

}

int main(){

    LL sum=0;

    n=read();k=read();

    for(LL i=1;i<=n;i++)a[i].p=read();

    for(LL i=1;i<=n;i++)a[i].c=read(),a[i].id=i;

    sort(a+1,a+n+1,cmp);

    for(LL i=1;i<=min(k+1,n);i++){

        a[i].ans=a[i-1].ans+a[i].c;

        q.push(a[i].c);

        sum+=a[i].c;

    }

    for(LL i=k+2;i<=n;i++){

        LL top=q.top();q.pop();

        sum-=top;

        q.push(a[i].c);

        sum+=a[i].c;

        a[i].ans=sum;

    }

    sort(a+1,a+n+1,cmp2);

    for(LL i=1;i<=n;i++)

        printf("%I64d ",a[i].ans);

    return 0;

}

C：Two Squares

就是给你两个正方形，判断有没有相交

我把这种题叫做不用脑子却死一片

final test的时候有一大堆人这题fst了。。诶

把握好代码的细节，然后写几个特判就好了

#include<bits/stdc++.h>

using namespace std;

struct Node{

    int x,y;

}a[5],b[5];

bool cmp(Node a,Node b){

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

int main(){

    for(int i=1;i<=4;i++)scanf("%d%d",&a[i].x,&a[i].y);

    for(int i=1;i<=4;i++)scanf("%d%d",&b[i].x,&b[i].y);

    sort(a+1,a+5,cmp);

    sort(b+1,b+5,cmp);

    int tmp=0;

    if(b[4].x<a[1].x)tmp=1;

    if(b[2].y>a[2].y)tmp=1;

    if(b[3].y<a[1].y)tmp=1;

    if(b[1].x>a[3].x)tmp=1;

    if(tmp){

        printf("NO");

        return 0;

    }

    //zuoshang

    if(b[1].x<a[2].x&&b[3].y>a[2].y){

        int t=b[2].y-b[2].x;

        if(t+a[2].x>a[2].y)tmp=1;

    }

    //zuoxia

    if(b[1].x<a[1].x&&b[2].y<a[1].y){

        int t=b[3].x+b[3].y;

        if(t-a[1].x<a[1].y)tmp=1;

    }

    //youshang

    if(b[3].y>a[4].y&&b[4].x>a[4].x){

        int t=b[1].x+b[1].y;

        if(t-a[4].x>a[4].y)tmp=1;

    }

    //youxia

    if(b[2].y<a[3].y&&b[4].x>a[3].x){

        int t=b[3].y-b[3].x;

        if(t+a[3].x<a[3].y)tmp=1;

    }

    if(tmp){

        printf("NO");

        return 0;

    }

    printf("YES");

    return 0;

}

D：Open Communication

身为一个蒟蒻这种题我还是少碰的好，题意很毒瘤，然后我就用非常不正常的做法A了，我都不知道我是怎么A的。

大概是有两个无聊的人，他们互相传递数字对，让你确定他们的秘密数字是什么，然后秘密数字是：对于两个元素不完全相等数对，其中一个相等的元素

然后可以确定输出那个数，你不能确定但那两个人可以确定输出0，你和其中一人都不能确定输出-1

然后我就记录一下在每个人的信息里可能匹配的和全局可能匹配的，加一堆特判就好了，反正是乱搞做法

#include<bits/stdc++.h>

using namespace std;

#define N 30

struct Pai{

    int a,b;

}x[N],y[N];

int n,m,pic[N];

int vis1[N][N],vis2[N][N];

int tmp1[N],tmp2[N];

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>x[i].a>>x[i].b;

    for(int i=1;i<=m;i++)cin>>y[i].a>>y[i].b;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++){

            if(x[i].a==y[j].a&&x[i].b==y[j].b)continue;

            if(x[i].a==y[j].b&&x[i].b==y[j].a)continue;

            if(x[i].a==y[j].a||x[i].a==y[j].b)pic[x[i].a]=1,vis1[i][x[i].a]=1,vis2[j][x[i].a]=1;

            if(x[i].b==y[j].a||x[i].b==y[j].b)pic[x[i].b]=1,vis1[i][x[i].b]=1,vis2[j][x[i].b]=1;

        }

    for(int i=1;i<=n;i++)

        for(int j=1;j<=9;j++)tmp1[i]+=vis1[i][j];

    for(int i=1;i<=m;i++)

        for(int j=1;j<=9;j++)tmp2[i]+=vis2[i][j];

    int siz=0,tip;

    for(int i=1;i<=9;i++){

        siz+=pic[i];

        if(pic[i])tip=i;

    }

    if(siz==1){

        cout<<tip;

        return 0;

    }

    if(!siz){

        cout<<"-1";

        return 0;

    }

    for(int i=1;i<=n;i++){

        if(tmp1[i]>1){

            cout<<"-1";

            return 0;

        }

    }

    for(int i=1;i<=m;i++){

        if(tmp2[i]>1){

            cout<<"-1";

            return 0;

        }

    }

    cout<<"0";

    return 0;

}

巴特西

【Codeforces】Round #488 (Div. 2) 总结

【Codeforces】Round #488 (Div. 2) 总结

A：Fingerprints

B：Knights of a Polygonal Table

C：Two Squares

D：Open Communication

E：Careful Maneuvering

F:Compute Power

最新文章

热门文章