题解 | 牛客小白月赛114 DEFG Java题解

D~G Java题解，代码已去除冗余，并保留必要注释~~~

D 神孙权

由题意可知，进行最大慎行操作的次数是一定的，设为max，那么每一次慎行操作后，进行帝力操作之和即为前后缀之和（其中前后缀的长度之和最大为max），因此可以分别求出前缀的前缀最大和，以及后缀的后缀最大和，线性遍历起即可，时间复杂度O(n+sqrt(n+k))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),max=find(n,k);
        long maxPre[]=new long[n+5],pre[]=new long[n+5],maxSuf=0,ans=-(long)1e18;
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+sc.nextInt();
            maxPre[i]=Math.max(pre[i],maxPre[i-1]);
        }
        for(int i=n;i>n-max;i--){
            ans=Math.max(ans,maxSuf+maxPre[max-(n-i)]);
            maxSuf=Math.max(maxSuf,pre[n]-pre[i-1]);
        }
        System.out.println(ans);
    }
    static int find(int n,int k){
        int ans=0;
        for(;k>=ans&&n>0;k-=ans-1,n--,ans++){

        }
        return ans;
    }
}

E 友诸葛亮

线性循环问题，直接把所有的位置的数，按照频次最小的n-1个数字之和循环下标即可，其中的下标指的是经过频次升序排序的下标，时间复杂度O((x+y+z)log(x+y+z))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt(),y=sc.nextInt(),z=sc.nextInt(),a[]=new int[x+y+z],ans[]=new int[x+y+z],count[]=new int[5];
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<x+y+z;i++){
            a[i]=sc.nextInt();
            count[a[i]]++;
            list.add(i);
        }
        int inc=count[1]+count[2]+count[3]-Math.max(count[1],Math.max(count[2],count[3]));
        Collections.sort(list,(a1,a2)->Integer.compare(a[a1],a[a2]));
        for(int i=x+y+z-1;i>=0;i--){
            ans[list.get(i)]=a[list.get((i+inc)%(x+y+z))];
        }
        for(int b:ans){
            System.out.print(b+" ");
        }
    }
}

F 王粲

分组背包问题，可以把桃看做两个牌，再进行更新的时候需要记录当前增加体力的次数以及最大站位总数，时间复杂度O(cn^2)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt(),max[][]=new int[n+5][n+5],ans=0;
        for(int i=0;i<=n;i++){
            Arrays.fill(max[i],-(int)1e9);
        }
        max[0][0]=0;
        for(int i=0;i<n;i++){
            int c=sc.nextInt(),ab[][]=new int[c+2][3];
            for(int k=0;k<2;k++){
                for(int j=2;j<=c+1;j++){
                    ab[j][k]=sc.nextInt();
                }
            }
            ab[0]=new int[]{x,y,0};//获得价值
            ab[1][2]=1;//增加体力
            for(int j=n;j>=0;j--){
                for(int k=n;k>=0;k--){
                    //max[j][k]表示的是选择占位j，且用了k次桃的最大价值
                    for(int p[]:ab){
                        if(j>=p[1]&&k>=p[2]){
                            max[j][k]=Math.max(max[j][k],max[j-p[1]][k-p[2]]+p[0]);
                        }
                    }
                    if(k>=j){
                        ans=Math.max(ans,max[j][k]);
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

G 蒋干

不分思路参考了参考资料，实现细节略有不同，时间复杂度O(能过)

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(),k=sc.nextInt(),size=0;
        //map1是牌库里面每种牌名对应的颜色集合，map2是手中的牌，set是要求的颜色集合
        Map<String,Set<String>> map1=new HashMap<>(),map2=new HashMap<>();
        Set<String> set=new HashSet<>();
        for(int i=0;i<n;i++){
            String color=sc.next(),s=sc.next();
            map1.putIfAbsent(s,new HashSet<>());
            map1.get(s).add(color);
        }
        for(int i=0;i<m;i++){
            String color=sc.next(),s=sc.next();
            map2.putIfAbsent(s,new HashSet<>());
            if(map2.get(s).add(color)){
                size++;
            }
        }
        for(int i=0;i<k;i++){
            set.add(sc.next());
        }
        if(size>=2){
            //此时需要判断手中牌的花色是否有给出的替换花色，若有就直接替换成自己即可
            for(String s:map2.keySet()){
                for(String color:map2.get(s)){
                    if(set.contains(color)){
                        System.out.println(String.format("Yes\n%s %s\n%s %s",color,s,color,s));
                        return;
                    }
                }
            }
        }
        //造出新牌，此时收中至少两张牌，替换掉一张即可，由于花色没有出现在花色集合中，因此任何造出的牌都是新牌
        //注意此时还有(手中之牌).size()==1的情况
        for(String s:map2.keySet()){
            Set<String> cur=map2.get(s);
            String curColor=null;
            for(String c:cur){
                curColor=c;
                break;
            }
            for(String color:map1.get(s)){
                if(set.contains(color)&&(size==1&&!color.equals(curColor)||!cur.contains(color))){
                    System.out.println(String.format("Yes\n%s %s\n%s %s",curColor,s,color,s));
                    return;
                }
            }
        }
        System.out.println("No");
    }
}