B显生之宙

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

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神性之陨

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

import java.util.*;
public class Main{
    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(),a[]=new int[m+5];
            for(int j=1;j<=m;j++){
                a[j]=sc.nextInt();
            }
            //count表示的是,作为一列中最下边的方块可能出现的
            int count[]=new int[n+5];
            Arrays.fill(count,1);
            for(int j=2;j<=m;j++){
                int pre[]=new int[n+5];
                if(a[j-1]==1){
                    for(int k=1;k<=n;k++){
                        if(count[k]>0){
                            int min=Math.max(a[j],k),max=Math.min(n,k+a[j]-1);
                            pre[min]++;
                            pre[max+1]--;
                        }
                    }
                }
                else if(a[j]==1){
                    for(int k=1;k<=n;k++){
                        if(count[k]>0){
                            int min=Math.max(1,k-a[j-1]+1),max=k;
                            pre[min]++;
                            pre[max+1]--;
                        }
                    }
                }
                else{
                    for(int k=1;k<=n;k++){
                        if(count[k]>0){
                            //下对上:
                            if(k+a[j]-1<=n){
                                pre[k+a[j]-1]++;
                                pre[k+a[j]]--;
                            }
                            //上对下:
                            if(k-a[j-1]-a[j]+2>=1){
                                pre[k-a[j-1]+1]++;
                                pre[k-a[j-1]+2]--;
                            }
                        }
                    }
                }
                for(int k=1;k<=n;k++){
                    pre[k]+=pre[k-1];
                }
                count=pre;
            }
            int ans=0;
            for(int j=1;j<=n;j++){
                if(count[j]>0){
                    ans++;
                }
            }
            System.out.println(ans);
        }
    }
}

F无垢之土

思路:这个我不会,这个链接里的题解看明白了,按照写了代码

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        List<Integer> path[]=new List[n+5],born[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
            born[i]=new ArrayList<>();
        }
        for(int i=1;i<n;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        for(int i=0;i<m;i++){
            int a=sc.nextInt(),t=sc.nextInt();
            born[a].add(t);
        }
        int l=0,r=(int)5e6;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(mid,n,path,born)){
                r=mid;
            }
            else{
                l=mid+1;
            }
            if(l==r-1){
                if(check(l,n,path,born)){
                    r=l;
                }
                break;
            }
        }
        System.out.println(r);
    }
    static boolean check(int t,int n,List<Integer> path[],List<Integer> born[]){
        int ans[][]=new int[n*2][];
        find(1,t,path,born,ans);
        for(int i=1;i<=n;i++){
            if(ans[i][0]+ans[i][1]<=t){
                return true;
            }
        }
        return false;
    }
    static void find(int k,int t,List<Integer> path[],List<Integer> born[],int ans[][]){
        ans[k]=new int[]{(int)1e7,(int)1e7};
        for(int a:path[k]){
            if(ans[a]==null){
                find(a,t,path,born,ans);
                ans[k]=merge(ans[k],new int[]{ans[a][0]+1,ans[a][1]+1});
            }
        }
        for(int b:born[k]){
            if(b*2<=t){
                ans[k]=merge(ans[k],new int[]{b});
            }
        }
    }
    static int[] merge(int a[],int b[]){
        for(int c:b){
            if(c<a[0]){
                a[1]=a[0];
                a[0]=c;
            }
            else if(c<a[1]){
                a[1]=c;
            }
        }
        return a;
    }
}