题解 | 牛客周赛 Round 104 DEF Java题解

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

D 小红的矩阵不动点

对于本来位置数值正确的，一定不要修改，只需要修改两个位置数值不对的，不让记录一下所有位置不对的格子本来需要的数字和实际的数字的情况，看是否可以通过交换两个点实现答案加2，否则，对于某个位置的已有数字，看是否有格子需要，此时增加为1，剩下情况增加为0，时间复杂度O(nm+250000)

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,inc=0;
        boolean has[][]=new boolean[505][505],need[]=new boolean[505];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                int a=sc.nextInt();
                if(a==Math.min(i,j)){
                    ans++;
                }
                else{
                   has[Math.min(i,j)][a]=need[Math.min(i,j)]=true;
                }
            }
        }
        for(int i=1;i<=500;i++){
            for(int j=1;j<=500;j++){
                inc=Math.max(inc,has[i][j]?(has[j][i]?2:need[j]?1:0):0);
            }
        }
        System.out.println(ans+inc);
    }
}

E 小红的不动点权值

考虑每个数字的贡献，一个数字k有贡献，一定是在子数组中包括[1,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(),a[]=new int[n+5];
        for(int i=0;i<n;i++){
            a[sc.nextInt()]=i;
        }
        long ans=0;
        for(int i=1,min=n+5,max=-1;i<=n;i++){
            min=Math.min(min,a[i]);
            max=Math.max(max,a[i]);
            ans+=(long)(min+1)*(n-max);
        }
        System.out.println(ans);
    }
}

F 小红的树不动点

根据E的思路，一个数字k产生贡献，需要在序列中存在[1,k]所有的整数，这样的子树需要时这些数字的共同祖先，因袭需要求lca，时间复杂度O(18n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),p[][]=new int[18][n+5],level[]=new int[n+5];
        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);
        }
        find(n,0,p,level,path);
        for(int i=1;i<18;i++){
            for(int j=1;j<=n;j++){
                p[i][j]=p[i-1][p[i-1][j]];
            }
        }
        long ans=0;
        for(int i=1,j=1;i<=n;i++,ans+=level[j]+1,j=lca(i,j,p,level)){}
        System.out.println(ans);
    }
    static int lca(int a,int b,int p[][],int level[]){
        if(level[a]<level[b]){
            return lca(b,a,p,level);
        }
        for(int i=17;i>=0;i--){
            if(level[a]-level[b]>=(1<<i)){
                a=p[i][a];
            }
        }
        for(int i=17;i>=0;i--){
            if(p[i][a]!=p[i][b]){
                a=p[i][a];
                b=p[i][b];
            }
        }
        return a==b?a:p[0][a];
    }
    static void find(int k,int pre,int p[][],int level[],List<Integer> path[]){
        for(int a:path[k]){
            if(a!=pre){
                level[a]=level[k]+1;
                p[0][a]=k;
                find(a,k,p,level,path);
            }
        }
    }
}