题解 | 牛客小白月赛89 BCDEF

伊甸之花

https://ac.nowcoder.com/acm/contest/76795/A

思路：首先为了使得最后一个数字最小，需要尽量先取出小的数字加到其他数字（一个或者多个）数字上，很明显，如果累加的值为非正数，那么为了使得剩下的数字在一次累加操作后尽可能小，最贪心的方式为给目前所有没有加到的数字都累加这个值，反之如果累加的数为正数，那么应该贪心地尽可能让少的数字变大，选取剩下的最小值去变大即可，其他数字不要动

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int j=0;j<t;j++){
            int n=sc.nextInt();
            Queue<Long> q=new PriorityQueue<>();
            for(int i=0;i<n;i++){
                q.add(sc.nextLong());
            }
            long add=0;
            for(int i=0;i<n-1;i++){
                long a=q.poll();
                if(add+a<=0){
                    add+=add+a;
                }
                else{
                    q.add(q.poll()+a+add);
                }
            }
            System.out.println(add+q.poll());
        }
    }
}

C太阳之华

思路：因为红为先手，那么需要特判没有红的情况返回blue，，其次先手如果可以使得蓝色全部消失，则返回red，否则先手红扩之后，一个蓝色（这个蓝色一定之前与一圈蓝色为邻，即使先手后，周围的蓝色蓝被换成红色，后手可以选择这个蓝色扩展出至少两个不相邻的蓝色块）总可以至少扩展出两个其他的蓝块

import java.util.*;
public class Main{
    static int move[][]={{1,0},{-1,0},{0,1},{0,-1}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),m=sc.nextInt();
            char c[][]=new char[n][];
            for(int j=0;j<n;j++){
                c[j]=sc.next().toCharArray();
            }
            System.out.println(find(c,n,m));
        }
    }
    static String find(char c[][],int n,int m){
        int hasBlue=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(c[i][j]=='.'){
                    hasBlue++;
                }
            }
        }
        if(hasBlue==m*n){
            return "Blue";
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(c[i][j]=='#'){
                    List<int[]> list=new ArrayList<>();
                    list.add(new int[]{i,j});
                    c[i][j]='p';
                    for(int k=0;k<list.size();k++){
                        int a[]=list.get(k);
                        for(int mo[]:move){
                            int x=a[0]+mo[0],y=a[1]+mo[1];
                            if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]=='#'){
                                list.add(new int[]{x,y});
                                c[x][y]='p';
                            }
                        }
                    }
                    Set<Integer> set=new HashSet<>();
                    for(int a[]:list){
                        for(int mo[]:move){
                            int x=a[0]+mo[0],y=a[1]+mo[1];
                            if(x>=0&&x<n&&y>=0&&y<m&&c[x][y]=='.'){
                                set.add(x*3000+y);
                            }
                        }
                    }
                    if(set.size()==hasBlue){
                        return "Red";
                    }
                }
            }
        }
        return "Draw";
    }
}

D冥古之潮

经典的问题：前i种距离可以得到多少种j种距离排列的方案，第i种选或者不选的问题，动态规划

import java.util.*;
public class Main{
    static int mod=(int)1e9+7;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),q=sc.nextInt(),x=sc.nextInt();
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<m;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        int dis[]=new int[n+5],count[]=new int[5005];
        Arrays.fill(dis,-1);
        dis[x]=0;
        Queue<Integer> queue=new LinkedList<>();
        queue.add(x);
        while(!queue.isEmpty()){
            int a=queue.poll();
            for(int b:path[a]){
                if(dis[b]==-1){
                    dis[b]=1+dis[a];
                    count[dis[b]]++;
                    queue.add(b);
                }
            }
        }
        long ans[]=new long[5005];
        ans[0]=1;
        for(int i=0;i<5005;i++){
            long temp[]=new long[5005];
            temp[0]=1;
            for(int j=1;j<=i;j++){
                temp[j]=(ans[j]+ans[j-1]*count[i])%mod;
            }
            ans=temp;
        }
        for(int i=0;i<q;i++){
            int k=sc.nextInt();
            System.out.println(ans[k]);
        }
    }
}

E神性之陨

思路：对每一列，记录放置的最后一个位置的所有可能的高度，由前一列转移的时候，需要考虑上一列或者只一列只允许放置一个方块的情况，否则只考虑上一列的底部接这一列的顶部，以及考虑这一列的底部接上一列的顶部两种状况，同时需要保证不出界

题解 | 牛客小白月赛89 BCDEF

全站热榜