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

C 智乃的数字

注意到末尾是5的奇数，对10取模余数是5，3的倍数的奇数，对6取模都余3，而符合上述两个的奇数，对30取模余15，因此可以二分结合容斥原理求出第k个这样的数字，时间复杂度O(Tlogk)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            long k=sc.nextLong(),l=0,r=k*10;
            while(l<r){
                long mid=(l+r)>>1;
                if(find(mid)>=k){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
                if(l==r-1){
                    if(find(l)>=k){
                        r=l;
                    }
                    break;
                }
            }
            System.out.println(r);
        }
    }
    static long find(long p){
        return (p+3)/6+(p+5)/10-(p+15)/30;
    }
}

D 智乃与长短期主义者博弈

对于某个回合面对的局面，可视为短期主义者先取，长期主义者在剩下的局面再取“当前最优的选择”，注意此处只需要让自己的当前局面最优解即可，这样的思想可以考虑区间动态规划，而这种规划又是自底向上的，因此可以记忆化搜，时间复杂度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];
        long sum=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
        }
        System.out.println(sum-find(new long[n][n],a,0,n-1)+" "+find(new long[n][n],a,0,n-1));
    }
    static long find(long max[][],int a[],int l,int r){
        if(l>=r){
            return 0;
        }
        if(a[l]>=a[r]){
            if(max[l+1][r]==0){
                max[l+1][r]=Math.max(a[l+1]+find(max,a,l+2,r),a[r]+find(max,a,l+1,r-1));
            }
            return max[l+1][r];
        }
        else{
            if(max[l][r-1]==0){
                max[l][r-1]=Math.max(a[l]+find(max,a,l+1,r-1),a[r-1]+find(max,a,l,r-2));
            }
            return max[l][r-1];
        }
    }
}

E 智乃的跳跃排序 数据弱，代码有误

下标相隔为k的数字可以任意交换，因此可以按照下标对k的取模数分组排序，再按照实际数值进行再起交换排序，后者用并查集实现，时间复杂度(α(n)+nlogn))

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(),a[]=new int[n],group[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            group[i]=i;
        }
        for(int i=0;i<n&&i<k;i++){
            Queue<Integer> q=new PriorityQueue<>();
            for(int j=i;j<n;j+=k){
                q.add(a[j]);
            }
            for(int j=i;j<n;j+=k){
                a[j]=q.poll();
            }
        }
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<n;i++){
            map.put(a[i],i);
            if(map.containsKey(a[i]+k)){
                union(i,map.get(a[i]+k),group);
            }
            if(map.containsKey(a[i]-k)){
                union(i,map.get(a[i]-k),group);
            }
        }
        List<Queue<Integer>> list[]=new List[n+5];
        for(int i=0;i<n;i++){
            int p=find(i,group);
            if(list[p]==null){
                list[p]=new ArrayList<>();
                list[p].add(new PriorityQueue<>());
                list[p].add(new PriorityQueue<>());
            }
            list[p].get(0).add(i);
            list[p].get(1).add(a[i]);
        }
        for(int i=0;i<n;i++){
            if(i==find(i,group)){
                Queue<Integer> idx=list[i].get(0),val=list[i].get(1);
                while(!idx.isEmpty()){
                    a[idx.poll()]=val.poll();
                }
            }
        }
        for(int i=1;i<n;i++){
            if(a[i]<a[i-1]){
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
    static void union(int a,int b,int group[]){
        group[find(b,group)]=find(a,group);
    }
    static int find(int a,int group[]){
        return a==group[a]?a:(group[a]=find(group[a],group));
    }
}

F 智乃的数组乘积

当x为0的时候，只需要将数组中的0改为非0数字即可；否则，需要利用前缀积思想，在遇到不符合的后缀的时候，将不符合的位置改为0即可，时间内复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),p=sc.nextInt(),x=sc.nextInt(),a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        if(x==0){
            for(int i=0;i<n;i++){
                a[i]=Math.max(a[i],1);
            }
        }
        else{
            x=(int)pow(x,p-2,p);
            Set<Long> set=new HashSet<>();
            set.add(1L);
            long pre=1;
            for(int i=0;i<n;i++){
                pre=pre*a[i]%p;
                if(a[i]==0||set.contains(pre*x%p)){
                    a[i]=0;
                    set.clear();
                    pre=1;
                }
                set.add(pre);
            }
        }
        for(int b:a){
            System.out.print(b+" ");
        }
    }
    static long pow(long a,long b,long p){
        long ans=1;
        for(;b!=0;b>>=1,a=a*a%p){
            if(b%2==1){
                ans=ans*a%p;
            }
        }
        return ans;
    }
}