题解 | 牛客周赛 Round 65 DEFG Java题解

D~G Java题解，代码已去除冗余

D 医生

用二进制数位来表示每种药可以值得病，以及每个病人的得病情况，对于每个病人，百里暴力检查每种组合是否可以治病，同时更新答案，时间复杂度O((n+k)m+n*2^k)

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(),patient[]=new int[n];
        for(int i=0;i<n;i++){
            patient[i]=find(sc.next());
        }
        int k=sc.nextInt(),drug[]=new int[k],mask[]=new int[1<<k];
        for(int i=0;i<k;i++){
            drug[i]=find(sc.next());
        }
        for(int i=0;i<(1<<k);i++){
            for(int j=0;j<k;j++){
                mask[i]|=drug[j]*(i>>j&1);
            }
        }
        for(int a:patient){
            int ans=(int)1e9;
            for(int i=0;i<(1<<k);i++){
                if((mask[i]&a)==a){
                    ans=Math.min(ans,Integer.bitCount(i));
                }
            }
            System.out.println(ans==1e9?-1:ans);
        }
    }
    static int find(String s){
        int ans=0;
        for(int i=s.length()-1;i>=0;i--){
            ans|=(s.charAt(i)-'0')<<i;
        }
        return ans;
    }
}

E 降温（easy） && F 降温（hard）

这俩题其实思路一样，算最小值的时候，需要让每一步进坑能降温x-1，否则寒潮日数加一天；而算最大值的时候，需要尽可能降温x，假如降不了x，就把当前温度设为最大，使得后续降温的空间尽可能大，时间复杂度O(n)

import java.util.*;
public class Main{
    static int low=-50,high=50;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),x=sc.nextInt(),max=0,min=0,last1=low,last2=low;
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            if(a>=low){
                if(last1-a>=x){
                    max++;
                }
                if(last2-a>=x){
                    min++;
                }
                last1=last2=a;
            }
            else{
                if(last1-x<low){
                    last1=high;
                }
                else{
                    last1-=x;
                    max++;
                }
                last2=Math.max(last2-x+1,low);
            }
        }
        System.out.println(max+" "+min);
    }
}

import java.util.*;
public class Main{
    static int low=-(int)5e8,high=(int)5e8;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),x=sc.nextInt(),max=0,min=0,last1=low,last2=low;
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            if(a>=low){
                if(last1-a>=x){
                    max++;
                }
                if(last2-a>=x){
                    min++;
                }
                last1=last2=a;
            }
            else{
                if(last1-x<low){
                    last1=high;
                }
                else{
                    last1-=x;
                    max++;
                }
                last2=Math.max(last2-x+1,low);
            }
        }
        System.out.println(max+" "+min);
    }
}

G 乌鸦

由题可知，相邻位置乌鸦数量奇偶性不同，因此可以先把某些位置设为1，像尽可能平衡分布，之后凑出偶数个剩余在插空，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long m=sc.nextLong(),ans[]=find(n,m,1);;
        if(ans==null){
            ans=find(n,m,0);
        }
        if(ans==null){
            System.out.println("-1");
        }
        else{
            for(long a:ans){
                System.out.print(a+" ");
            }
        }
    }
    static long[] find(int n,long m,int start){
        long ans[]=new long[n];
        for(int i=start;i<n;i+=2){
            if(m==0){
                return null;
            }
            ans[i]=1;
            m--;
        }
        long d=m/n;
        for(int i=0;i<n;i++){
            ans[i]+=d;
        }
        m%=n;
        if(m%2==1){
            if(d==0||n%2==0){
                return null;
            }
            m+=n;
            for(int i=0;i<n;i++){
                ans[i]--;
            }
        }
        for(int i=start^1;i<n&&m!=0;i+=2,m-=2){
            ans[i]+=2;
        }
        for(int i=start;i<n&&m!=0;i+=2,m-=2){
            ans[i]+=2;
        }
        return ans;
    }
}