题解 | 牛客周赛 Round 89 DEFG Java题解

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

D 小红开灯（三，hard）

首先特判n==k的情况，此时只有两种结果，也就是全开和全关；；否则，经过两次操作可以改变任意两盏距离不超过k-1的灯的状态，因此可以按照k的奇偶性分类讨论，时间复杂复杂度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();
        System.out.println(n==k?2:pow(n-1+k%2));
    }
    static int pow(int a){
        return a==0?1:pow(a-1)*2%mod;
    }
}

E 小红开灯（四)

暴力修改灯的开关状态，每盏灯只跟自己右边或者下边的配对，直到最后一盏灯，无法配对儿时，即返回无解，时间复杂度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(),a[][]=new int[n][m];
        for(int i=0;i<n;i++){
            String s=sc.next();
            for(int j=0;j<m;j++){
                a[i][j]=s.charAt(j)-'0';
            }
        }
        List<int[]> ans=new ArrayList<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]==0){
                    if(j<m-1){
                        a[i][j+1]^=1;
                        ans.add(new int[]{i+1,j+1,i+1,j+2});
                    }
                    else if(i<n-1){
                        a[i+1][j]^=1;
                        ans.add(new int[]{i+1,j+1,i+2,j+1});
                    }
                    else{
                        System.out.println("-1");
                        return;
                    }
                }
            }
        }
        System.out.println(ans.size());
        for(int b[]:ans){
            System.out.println(b[0]+" "+b[1]+" "+b[2]+" "+b[3]);
        }
    }
}

F 小红开灯（五，easy）

状态机类型的动态规划，首先一个节点在最优的情况后下一定不会被反转两次，定义0为一个点不被改变的子树最小次数，1是改变了状态了的最小次数，2是点没改变，但是准备跟父节点一起翻转的最小次数，考虑清楚转移即可，时间复杂度O(n)

import java.util.*;
public class Main{
    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);
        }
        long ans[]=find(1,0,path);
        System.out.println(Math.min(ans[0],ans[1]));
    }
    static long[] find(int k,int p,List<Integer> path[]){
        //0代表这个点没有翻转，1代表翻转了，2代表没翻转但是准备跟父节点翻转
        long ans[]=new long[]{0,(int)1e9,0};
        List<long[]> list=new ArrayList<>();
        long sum=0;
        for(int a:path[k]){
            if(a!=p){
                long cur[]=find(a,k,path);
                ans[0]+=cur[1];
                ans[2]+=Math.min(cur[0],cur[1]);
                sum+=Math.min(cur[0],cur[1]);
                list.add(new long[]{cur[2],Math.min(cur[0],cur[1])});
            }
        }
        for(long a[]:list){
            ans[1]=Math.min(ans[1],1+a[0]+sum-a[1]);
        }
        return ans;
    }
}

G 小红开灯（五，hard）

题意同上，需要记录每种状态的来时路径，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> path[]=new List[n+5];
        List<int[]> last[][]=new List[n+5][3];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
            for(int j=0;j<3;j++){
                last[i][j]=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);
        }
        long ans[]=find(1,0,path,last);
        System.out.println(Math.min(ans[0],ans[1]));
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{1,ans[0]<=ans[1]?0:1});
        while(!q.isEmpty()){
            int a[]=q.poll();
            for(int b[]:last[a[0]][a[1]]){
                q.add(b);
                if(a[1]==1&&b[1]==2){
                    System.out.println(a[0]+" "+b[0]);
                }
            }
        }
    }
    static long[] find(int k,int p,List<Integer> path[],List<int[]> last[][]){
        //0代表这个点没有翻转，1代表翻转了，2代表没翻转但是准备跟父节点翻转
        long ans[]=new long[]{0,(int)1e9,0};
        List<long[]> list=new ArrayList<>();
        long sum=0;
        for(int a:path[k]){
            if(a!=p){
                long cur[]=find(a,k,path,last);
                ans[0]+=cur[1];
                last[k][0].add(new int[]{a,1});
                ans[2]+=Math.min(cur[0],cur[1]);
                last[k][2].add(new int[]{a,cur[0]<=cur[1]?0:1});
                sum+=Math.min(cur[0],cur[1]);
                list.add(new long[]{cur[2],Math.min(cur[0],cur[1]),a,cur[0]<=cur[1]?0:1});
            }
        }
        int next=-1;
        for(long a[]:list){
            long d=1+a[0]+sum-a[1];
            if(d<ans[1]){
                ans[1]=d;
                next=(int)a[2];
            }
        }
        for(long a[]:list){
            last[k][1].add(next==a[2]?new int[]{next,2}:new int[]{(int)a[2],(int)a[3]});
        }
        return ans;
    }
}