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

DEF Java题解，代码已去除冗余~~~ 好菜，都得看答案才会😐🙄😣，只有代码没有分析

D 小苯的排列计数

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            boolean ok=true;
            List<int[]> list=new ArrayList<>();
            for(int j=1,pre=n+5;j<=n;j++){
                int p=sc.nextInt();
                if(p>pre){
                    ok=false;
                }
                else if(pre!=p){
                    list.add(new int[]{j,p});
                    pre=p;
                }
            }
            list.add(new int[]{n+1,0});
            if(!ok){
                System.out.println(0);
            }
            else{
                long ans=1;
                for(int j=1,count=n-list.get(0)[1];j<list.size();j++){
                    ans=ans*A(count,list.get(j)[0]-list.get(j-1)[0]-1)%mod;
                    count+=list.get(j-1)[1]-list.get(j)[1]-(list.get(j)[0]-list.get(j-1)[0]);
                }
                System.out.println(ans);
            }
        }
    }
    static long pow(long a,long b){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%mod){
            if(b%2==1){
                ans=ans*a%mod;
            }
        }
        return ans;
    }
    static long A(int a,int b){
        return b>a||b<0?0:fac(a)*pow(fac(a-b),mod-2)%mod;
    }
    static long fac(int a){
        return a==0?1:fac(a-1)*a%mod;
    }
}

E 和+和

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(),a[]=new int[n+5],b[]=new int[n+5];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=1;i<=n;i++){
            b[i]=sc.nextInt();
        }
        long min1[]=new long[n+5],min2[]=new long[n+5],sum=0,ans=(long)1e18;
        Queue<Integer> q=new PriorityQueue<>((p1,p2)->p2-p1);
        for(int i=1;i<=m;i++){
            q.add(a[i]);
            sum+=a[i];
        }
        min1[m]=sum;
        for(int i=m+1;i<=n;i++){
            q.add(a[i]);
            min1[i]=(sum+=a[i]-q.poll());
        }
        q.clear();
        sum=0;
        for(int i=n;i>n-m;i--){
            q.add(b[i]);
            sum+=b[i];
        }
        min2[n-m+1]=sum;
        for(int i=n-m;i>0;i--){
            q.add(b[i]);
            min2[i]=(sum+=b[i]-q.poll());
        }
        for(int i=m;i+m<=n;i++){
            ans=Math.min(ans,min1[i]+min2[i+1]);
        }
        System.out.println(ans);
    }
}

F 怎么写线性SPJ

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> list=new ArrayList<>();
        list.add(1);
        while(list.size()<n){
            List<Integer> temp=new ArrayList<>();
            for(int i=0;i<2;i++){
                for(int a:list){
                    temp.add(a);
                }
            }
            list=temp;
            list.set(list.size()-1,list.get(list.size()-1)+1);
        }
        System.out.println(new HashSet<>(list.subList(0,n)).size());
        for(int i=0;i<n;i++){
            System.out.print(list.get(i)+" ");
        }
    }
}