题解 | 牛客周赛 Round 59 DEF Java题解

DEF Java题解，代码已去掉冗余

D 构造mex

特殊讨论k==0，以及必须至少有每一个[0,k-1]的数字，其他的数字需用不是k的数字填充，时间复杂度O(Tn)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int t=Integer.parseInt(bf.readLine());
        for(int i=0;i<t;i++){
            String arr[]=bf.readLine().split(" ");
            List<Integer> ans=find(Integer.parseInt(arr[0]),Integer.parseInt(arr[1]),Integer.parseInt(arr[2]));
            if(ans==null){
                bw.write("NO\n");
            }
            else{
                bw.write("YES\n");
                for(int a:ans){
                    bw.write(a+" ");
                }
                bw.write("\n");
            }
        }
        bw.flush();
    }
    static List<Integer> find(int s,int n,int k){
        if(n<k||k==1&&s==1){
            //至少需要k个数字占满[0,k-1]，和为1肯定分出一个1,
            return null;
        }
        List<Integer> ans=new ArrayList<>();
        if(k==0){
            //此时序列需要全是正数
            if(s<n){
                return null;
            }
            for(int i=0;i<n;i++){
                ans.add(i<s%n?s/n+1:s/n);
            }
        }
        else{
            long sum=(long)k*(k-1)/2;//至少需要的总和量
            //剩下的数字要么是一个大于k的数字，要么全是小于k的数字
            if(sum>s||n==k&&s>sum||n==k+1&&s==sum+k){
                //总和超过s，或者余下正数但是数量不余下，余下一个数但是剩下k
                return null;
            }
            s-=sum;
            n-=k;
            for(int i=0;i<k;i++){
                ans.add(i);
            }
            if(s>k){
                ans.add(s);
                n--;
                s=0;
            }
            while(n!=0){
                if(s>k-1){
                    ans.add(k-1);
                    s-=k-1;
                }
                else{
                    ans.add(s);
                    s=0;
                }
                n--;
            }
        }
        return ans;
    }
}

E 小红的X型矩阵

统计横纵坐标的和与差（模n下）1的数量，枚举每一个左上角的位置，尝试计算，时间复杂度O(n^2)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[][]=new int[n][n],count1[]=new int[n],count2[]=new int[n],sum=0,ans=(int)1e9;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                a[i][j]=sc.nextInt();
                count1[(i+j)%n]+=a[i][j];
                count2[(i-j+n)%n]+=a[i][j];
                sum+=a[i][j];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                //表示的是把a[i][j]的数字挪到左上角
                ans=Math.min(ans,n*2-n%2-(count2[(i-j+n)%n]+count1[(i+j+n-1)%n]-(n%2==1?a[(i+n/2)%n][(j+n/2)%n]:0))*2+sum);
            }
        }
        System.out.println(ans);
    }
}

F 小红的数组回文值

方法一：区间动态规划，计算贡献，时间复杂度O(n^2)

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(),a[]=new int[n];
        long ans[][]=new long[n][n],pow[]=new long[n+5];
        pow[0]=1;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            pow[i+1]=pow[i]*2%mod;
        }
        for(int d=1;d<n;d++){
            for(int i=0;i+d<n;i++){
                ans[i][i+d]=(ans[i][i+d-1]+ans[i+1][i+d]+(a[i]==a[i+d]?0:pow[d-1]))%mod;
            }
        }
        System.out.println(ans[0][n-1]);
    }
}

方法二：组合计算