题解 | 牛客小白月赛101 CEDF Java题解

C~F Java题解，代码已去除冗余

C tb的路径问题

暴力模拟一下n<100时的结果即可找到规律，时间复杂度O(1)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(Math.min(n*2-2,n%2==1?6:4));
    }
}

D tb的平方问题

对于任何一个下标，包含它的好数组，就是总的好数组数，减去左边不包含它的好数组数，再减去右边不包含它的好数组数，时间复杂度nC+q，其中C==1e4

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));
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]),a[]=new int[n+5],pre[]=new int[n+5],sum=0,count=0,ans[]=new int[n+5];
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        arr=bf.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(arr[i-1]);
            sum+=a[i];
            pre[i]=pre[i-1];
            for(int j=1;j*j<=sum;j++){
                pre[i]+=map.getOrDefault(sum-j*j,0);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        map.clear();
        map.put(0,1);
        sum=0;
        for(int i=n;i>0;i--){
            ans[i]=pre[n]-pre[i-1]-count;
            sum+=a[i];
            for(int j=1;j*j<=sum;j++){
                count+=map.getOrDefault(sum-j*j,0);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        for(int i=0;i<q;i++){
            bw.write(ans[Integer.parseInt(bf.readLine())]+"\n");
        }
        bw.flush();
    }
}

E tb的数数问题

用类似质数筛的方法求得1e6内所有数字是否为好的，时间复杂度O(ClogC+nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[(int)1e6+5],a[]=new int[n],ans=0;
        for(int i=1;i<=1e6;i++){
            for(int j=i;j<=1e6;j+=i){
                count[j]++;
            }
        }
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);
        for(int i=0;i<n;i++){
            if(i==0||a[i]!=a[i-1]){
                for(int j=a[i];j<=1e6;j+=a[i]){
                    count[j]--;
                }
            }
        }
        for(int i=1;i<=1e6;i++){
            if(count[i]==0){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

F tb的排列问题

参考资料，时间复杂度O(Tn)

import java.util.*;
public class Main{
    static int mod=998244353;
    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(),w=sc.nextInt(),idx[]=new int[n+5],pre[]=new int[n+1],notInA=0;
            for(int j=1;j<=n;j++){
                pre[j]=pre[j-1];
                int a=sc.nextInt();
                if(a==-1){
                    pre[j]++;
                }
                else{
                    idx[a]=j;
                }
            }
            long ans=1;
            for(int j=1;j<=n;j++){
                int b=sc.nextInt();
                if(idx[b]==0){
                    ans=ans*(pre[Math.min(n,j+w)]-notInA)%mod;
                    notInA++;
                }
                else if(idx[b]>j+w){
                    ans=0;
                }
            }
            System.out.println(ans);
        }
    }
}