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

C 翻之

对于两列，初始情况相同的，肯定是需要翻转的列的情况是一样的，因此只需要判断哪种列的排序最多即可，时间复杂度O(nm)

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(),ans=0;
        StringBuilder sb[]=new StringBuilder[m];
        for(int i=0;i<m;i++){
            sb[i]=new StringBuilder();
        }
        for(int i=0;i<n;i++){
            String s=sc.next();
            for(int j=0;j<m;j++){
                sb[j].append(s.charAt(j));
            }
        }
        Map<String,Integer> map=new HashMap<>();
        for(StringBuilder t:sb){
            String s=t.toString();
            map.put(s,map.getOrDefault(s,0)+1);
        }
        for(int a:map.values()){
            ans=Math.max(ans,a);
        }
        System.out.println(ans);
    }
}

D 乘之

首先俩人一定选择的区间是连续区间，因为假如不连续，之间的部分乘k之后要么使得和不增长，要么使得和不下降，因此可以又小龙或小蛇中的一个选取，，而作为博弈，小蛇是在小龙的基础上选取（使得在小龙的基础上选则后和最小），小龙应该预见到小蛇选完后的结果，那么最优就可以先把整个区间都选上，时间复杂度O(Tn)，，，其实这个题我不懂，上边的证明瞎说的

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--){
            int n=sc.nextInt(),k=sc.nextInt();
            long ans=0;
            for(int j=0;j<n;j++){
                ans+=k*sc.nextInt();
            }
            System.out.println(ans);
        }
    }
}

E 在树上游玩

图是个树，因此将所有标记的连通块点缩点后，可以看做是树中有些互不相邻的标记点，只需要把每个连通块的外接边涂红一个即可，用并查集处理，时间复杂度O(α(n))

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(),k=sc.nextInt(),count[]=new int[n+5],group[]=new int[n+5];
        for(int i=1;i<=n;i++){
            group[i]=i;
        }
        boolean has[]=new boolean[n+5];
        for(int i=0;i<k;i++){
            has[sc.nextInt()]=true;
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            if(has[u]&&has[v]){
                union(u,v,group,count);
            }
            else if(has[v]){
                count[find(v,group)]++;
            }
            else if(has[u]){
                count[find(u,group)]++;
            }
        }
        long ans1=0,ans2=1;
        for(int i=1;i<=n;i++){
            if(i==find(i,group)&&count[i]>0){
                ans1++;
                ans2=ans2*count[i]%mod;
            }
        }
        System.out.println(ans1+" "+ans2);
    }
    static void union(int a,int b,int group[],int count[]){
        int p1=find(a,group),p2=find(b,group);
        if(p1!=p2){
            group[p2]=p1;
            count[p1]+=count[p2];
        }
    }
    static int find(int a,int group[]){
        return a==group[a]?a:(group[a]=find(group[a],group));
    }
}

F 小红的01子序列计数（hard

先把字符串加长至两倍，需要计算后一半每个1对答案做出的贡献，假设单独考虑的是s[j]==1与s[i]==0对答案做出的贡献，显然我们有j-i<n是有意义的，那么这对儿数字，会对长度为长度j-1+1的字串做出大小为1的贡献，为长度j-1+2的字串做出大小2的贡献，，以此类推，为长度n的字串做出大小为n-(j-i)的贡献，因此s[j]做出的总贡献为sum(sum(1~n-(j-i) if s[i]==0) for i in(j-n,j])，分别维护下标的三种（0次，1次，2次）前缀和即可，时间时间复杂度O(n)

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,coef[][]={{0,1,1},{1,2,0},{1,0,0}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String s=sc.next();
        long pre[][]=new long[n*2+5][3],ans=0;
        for(int i=1;i<n*2;i++){
            pre[i]=pre[i-1].clone();
            if(s.charAt((i-1)%n)=='0'){
                for(int j=0;j<3;j++){
                    pre[i][j]=(pre[i][j]+pow(i,j))%mod;
                }
            }
            else if(i>=n){
                for(int j=0;j<3;j++){
                    long sum=0;;
                    for(int p=0;p<3;p++){
                        sum=(sum+pow(n-i,p)*coef[j][p])%mod;
                    }
                    ans=(ans+sum*(pre[i][j]-pre[i-n][j])%mod+mod)%mod;
                }
            }
        }
        System.out.println(ans*pow(2,mod-2)%mod);
    }
    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;
    }
}