AtCoder Beginner Contest 088 简要题解

题目链接https://abc088.contest.atcoder.jp/assignments

A

  • 暴力
int n,a;
int main(){
    read(n),read(a);
    if (a>=n) puts("Yes");
    else{
        for (int i=0;i<=a;i++){
            if ((n-i)%500==0) return puts("Yes"),0;
        }
        puts("No");
    }
    return 0;
}

B

  • 肯定都尽量拿大的,所以从大到小排序以后模拟即可。
int n,a[105];
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    int ans=0;
    for (int i=1;i<=n;i+=2){
        ans+=a[i]-a[i+1];
    }
    printf("%d\n",ans);
    return 0;
}

C

  • 首先可以知道每个a_ib_i都被计算了三次,所以最后总和一定是3的倍数,其次可以知道第二列对第一列的差值为b_2-b_1固定不变,其他同理,所以我们都试一下看差值是否恒定即可判断。
int c[4][4];
int main(){
    int ans=0;
    for (int i=1;i<=3;i++){
        for (int j=1;j<=3;j++){
            ans+=read(c[i][j]);
        }
    }
    if (ans%3!=0) puts("No");
    else{
        bool flag=true;
        int tmp;

        tmp=c[1][2]-c[1][1];
        for (int i=2;i<=3;i++){
            flag&=(tmp==c[i][2]-c[i][1]);
        }

        tmp=c[1][3]-c[1][2];
        for (int i=2;i<=3;i++){
            flag&=(tmp==c[i][3]-c[i][2]);
        }

        tmp=c[2][1]-c[1][1];
        for (int i=2;i<=3;i++){
            flag&=(tmp==c[2][i]-c[1][i]);
        }
        tmp=c[3][1]-c[2][1];
        for (int i=2;i<=3;i++){
            flag&=(tmp==c[3][i]-c[2][i]);
        }

        if (flag) puts("Yes");
        else puts("No");
    }
}

D

  • BFS出最短路以后,把最短路以外的格子都涂黑就是我们要得最大值了,因为显然可以知道最短路以外的格子都没有用,且保留下来的白格子是最少的。
struct Node{
    int x,y,step;
};
int n,m;
char maze[100][100];
bool vis[100][100];
int dir_x[]={0,1,0,-1};
int dir_y[]={1,0,-1,0};
int main(){
    read(n),read(m);
    int ans=n*m;
    for (int i=1;i<=n;i++){
        scanf("%s",maze[i]+1);
        for (int j=1;j<=m;j++){
            if (maze[i][j]=='#') ans--;
        }
    }
    if (maze[1][1]=='#'||maze[n][m]=='#') puts("-1");
    else{
        queue<Node>Q;
        Q.push((Node){1,1,1});
        while (!Q.empty()){
            Node cur=Q.front();Q.pop();
            if (cur.x==n&&cur.y==m){
                return printf("%d\n",ans-cur.step),0;
            }
            for (int i=0;i<4;i++){
                int tx=dir_x[i]+cur.x;
                int ty=dir_y[i]+cur.y;
                if (tx<1||tx>n||ty<1||ty>m||maze[tx][ty]=='#'||vis[tx][ty]) continue;
                vis[tx][ty]=1;
                Q.push((Node){tx,ty,cur.step+1});
            }
        }
        puts("-1");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注