D~F Java

D 小黑的区间

利用双指针，左指针固定为子数组起点，右指针试图加入数字，当加入的右指针处数字上一个在i前边或者距离小于k的时候可以加入，时间复杂度O(n)

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(),col[]=new int[n],last[]=new int[100005];
        Arrays.fill(last,-1);
        long ans=0;
        for(int i=0;i<n;i++){
            col[i]=sc.nextInt();
        }
        for(int i=0,j=0;i<n;i++){
            while(j<n&&(j-last[col[j]]<=k||last[col[j]]<i)){
                last[col[j]]=j;
                j++;
            }
            ans+=j-i;
        }
        System.out.println(ans);
    }
}

E 小绿的房子

首先利用递归由下向上处理每个点，保存子节点中每一支的最长距离，二次递归由上向下，一次依次处理向下的最长距离，向父节点方向的最长距离。本代码在处理最值的过程利用了有序映射，因此时间复杂度为O(nlogn)，其实也可以只记录最大值和次大值那么时间可以O(n)

import java.util.*;
public class Main{
    static int ans=0;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> path[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt(),v=sc.nextInt();
            path[u].add(v);
            path[v].add(u);
        }
        TreeMap<Integer,Integer> map[]=new TreeMap[n+5];
        findDis(1,path,map,new boolean[n+5]);
        findMaxDis(1,-1,-1,path,map,new boolean[n+5]);
        System.out.println(ans);
    }
    static void findMaxDis(int k,int par,int pre,List<Integer> path[],TreeMap<Integer,Integer> map[],boolean has[]){
        has[k]=true;
        int max=map[k].lastKey();
        if(k!=1){
            int a=map[k].lastKey();
            modify(map[par],1+a,-1);
            max=Math.max(max,1+Math.max(pre,map[par].lastKey()));
            pre=Math.max(pre,map[par].lastKey());
            modify(map[par],1+a,1);
        }
        if(max<=2){
            ans++;
        }
        for(int a:path[k]){
            if(!has[a]){
                findMaxDis(a,k,1+pre,path,map,has);
            }
        }
    }
    static void findDis(int k,List<Integer> path[],TreeMap<Integer,Integer> map[],boolean has[]){
        //深搜并整理每个节点向下的每个子节点的最长路径长度
        has[k]=true;
        map[k]=new TreeMap();
        modify(map[k],0,1);
        for(int a:path[k]){
            if(!has[a]){
                findDis(a,path,map,has);
                modify(map[k],1+map[a].lastKey(),1);
            }
        }
    }
    static void modify(TreeMap<Integer,Integer> map,int a,int inc){
        map.put(a,map.getOrDefault(a,0)+inc);
        if(map.get(a)==0){
            map.remove(a);
        }
    }
}

F 小橙的圈圈

观察三元环，可以发现假如不看方向，那么任意三个点可以组成环，那么其中不符合要求的环，必定有两个边同时指向一个点，那么就是三元组数量减去所有的入度任选2的数量，时间复杂度O(n^2)

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,seed;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[n+5];
        seed=sc.nextInt();
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(rnd()==0){
                    count[i]++;
                }
                else{
                    count[j]++;
                }
            }
        }
        long ans=(long)n*(n-1)*(n-2)/6;
        for(int i=1;i<=n;i++){
            ans-=(long)count[i]*(count[i]-1)/2;
        }
        System.out.println(ans);
    }
    static long rnd(){
        long ans=seed;
        seed=(seed*7+13)%mod;
        return ans&1;
    }
}

但是，有一个复杂度不正确的方法，利用二进制优化，压缩为long的比特，时间复杂度为O(n^3/C)，其中C==63，当取得极限数据时，复杂度高达2e9，但是依然可以ac，仅供参考吧，不提倡

import java.util.*;
public class Main{
    static long mod=(int)1e9+7,seed;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[n+5];
        long edgeOut[][]=new long[n+5][n/63+1],edgeIn[][]=new long[n+5][n/63+1],ans=0;
        seed=sc.nextInt();
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(rnd()==0){
                    for(int k=0;k<=n/63;k++){
                        ans+=Long.bitCount(edgeIn[i][k]&edgeOut[j][k]);
                    }
                    edgeOut[i][j/63]|=1L<<(j%63);
                    edgeIn[j][i/63]|=1L<<(i%63);
                }
                else{
                    for(int k=0;k<=n/63;k++){
                        ans+=Long.bitCount(edgeIn[j][k]&edgeOut[i][k]);
                    }
                    edgeOut[j][i/63]|=1L<<(i%63);
                    edgeIn[i][j/63]|=1L<<(j%63);
                }
            }
        }
        System.out.println(ans);
    }
    static long rnd(){
        long ans=seed;
        seed=(seed*7+13)%mod;
        return ans&1;
    }
}