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

C Cidoai的植物

按照列存储每一列空白位置，操作1的时候种植并清空，操作的2的时候把位置加入，时间复杂度O(mn+k)

import java.util.*;
public class Main{
    static long seed;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
        seed=sc.nextLong();
        List<Integer> list[]=new List[m+5];
        for(int i=1;i<=m;i++){
            list[i]=new ArrayList<>();
            for(int j=1;j<=n;j++){
                list[i].add(j);
            }
        }
        long arr[][]=new long[n+5][m+5],ans=0;
        for(int i=0;i<k;i++){
            long op=rnd()%2+1;
            if(op==1){
                long idx=rnd()%m+1,x=rnd()%(n*m)+1;
                for(int a:list[(int)idx]){
                    arr[a][(int)idx]=x;
                }
                list[(int)idx].clear();
            }
            else{
                int a=(int)(rnd()%n+1),b=(int)(rnd()%m+1);
                if(arr[a][b]!=0){
                    list[b].add(a);
                    arr[a][b]=0;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                ans^=arr[i][j]*((i-1)*m+j);
            }
        }
        System.out.println(ans);
    }
    static long rnd(){
        long p=1L<<32,ret=seed;
        seed=(seed^((seed<<13)%p))%p;
        seed=(seed^((seed>>17)%p))%p;
        seed=(seed^((seed<<5)%p))%p;
        return ret;
    }
}

D Cidoai的猫猫

相邻的字符串p要么是取自同一个字串，要么是向右的平移一个单位的字串，而后者成立的条件只能是字串仅有一种字母构成，因此对任意k，操作即为将同种字母缩短为最多k连续，时间复杂度O(nlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),sum=n,count=0;
        long ans=0;
        String s=sc.next();
        Queue<Integer> q=new PriorityQueue<>((a,b)->b-a);
        for(int i=0,j=0;i<n;){
            while(j<n&&s.charAt(i)==s.charAt(j)){
                j++;
            }
            q.add(j-i);
            i=j;
        }
        for(int i=n;i>0;i--){
            while(!q.isEmpty()&&q.peek()>=i){
                sum-=q.poll();
                count++;
            }
            ans^=(long)i*(sum+i*count);
        }
        System.out.println(ans);
    }
}

E Cidoai的可乐

对于权值较小的点，尽量用更多的连接其他点，只需要找到前n-1可以的连的边就是理论上的最小边权和，时间复杂度O(nlogn)

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],d[]=new int[n];
        long ans=0;
        Queue<Integer> q=new PriorityQueue<>((p1,p2)->Integer.compare(a[p1],a[p2]));
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            q.add(i);
        }
        for(int i=0;i<n;i++){
            d[i]=sc.nextInt();
        }
        for(int i=0;i<n-1;i++){
            int b=q.poll();
            ans+=a[b];
            d[b]--;
            if(d[b]>0){
                q.add(b);
            }
        }
        System.out.println(ans);
    }
}

F Cidoai的自恋

参考资料。。。。待完善，时间复杂度O(n)

import java.util.*;
public class Main{
    static long seed;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt(),idx[]=new int[n+5],len[]=new int[n+5],ans=0;
        seed=sc.nextLong();
        for(int i=1;i<=k;i++){
            int a=(int)(rnd()%n+1);
            if(idx[a]==0){
                idx[a]=i;
            }
        }
        Stack<Integer> stack=new Stack<>();
        for(int i=1;i<=n;i++){
            if(idx[i]>0){
                while(!stack.isEmpty()&&stack.peek()>idx[i]){
                    stack.pop();
                }
                stack.push(idx[i]);
            }
            else{
                len[i]=stack.size();
            }
        }
        stack.clear();
        for(int i=n;i>0;i--){
            if(idx[i]>0){
                while(!stack.isEmpty()&&stack.peek()>idx[i]){
                    stack.pop();
                }
                stack.push(idx[i]);
            }
            else{
                len[i]+=stack.size();
            }
        }
        for(int i=1;i<=n;i++){
            if(idx[i]==0&&(ans==0||len[i]<len[ans])){
                ans=i;
            }
        }
        System.out.println(ans);
    }
    static long rnd(){
        long p=1L<<32,ret=seed;
        seed=(seed^((seed<<13)%p))%p;
        seed=(seed^((seed>>17)%p))%p;
        seed=(seed^((seed<<5)%p))%p;
        return ret;
    }
}