牛客周赛 Round 34 题解 | DEFG

D小红的陡峭值

思路见注释

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];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        int b[]=a.clone();
        Arrays.sort(b);
        if(b[n-1]==0){
            //说明全是0：
            for(int i=0;i<n-1;i++){
                a[i]=1;
            }
            a[n-1]=2;
        }
        boolean head=a[0]==0,tail=a[n-1]==0;
        //先处理所有0变成左边的数字或者右边的非零数字，方法就是正着溜一遍，反着溜一遍
        for(int i=0,j=-1;i<n;i++){
            if(a[i]!=0){
                j=a[i];
            }
            else if(j!=-1){
                a[i]=j;
            }
        }
        for(int i=n-1,j=-1;i>=0;i--){
            if(a[i]!=0){
                j=a[i];
            }
            else if(j!=-1){
                a[i]=j;
            }
        }
        //接下来验证所有数字的陡峭值是不是小于等于1
        long sum=0;
        for(int i=1;i<n;i++){
            sum+=Math.abs(a[i]-a[i-1]);
        }
        if(sum>1){
            System.out.println("-1");
            return;
        }
        if(sum==0){
            //此时只能修改首尾的数字，不然陡峭值至少是2了
            if(!head&&!tail){
                System.out.println("-1");
                return;
            }
            if(head){
                a[0]++;
            }
            else{
                a[n-1]++;
            }
        }
        for(int num:a){
            System.out.print(num+" ");
        }
    }
}

E小红的树形 dp

验证图是否为二分图即可

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char c[]=sc.next().toCharArray();
        List<Integer> path[]=new List[n];
        for(int i=0;i<n;i++){
            path[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            int u=sc.nextInt()-1,v=sc.nextInt()-1;
            path[u].add(v);
            path[v].add(u);
        }
        System.out.println(find(n,path,c));
    }
    static String find(int n,List<Integer> path[],char c[]){
        //先判断是否有非？的字符，有的话直接开始BFS，否则从0开始赋值并BFS
        boolean all=false;
        for(char ch:c){
            if(ch!='?'){
                all=true;
            }
        }
        if(!all){
            c[0]='p';
        }
        Queue<Integer> q=new LinkedList<>();
        boolean has[]=new boolean[n];
        for(int i=0;i<n;i++){
            if(c[i]!='?'){
                q.add(i);
                has[i]=true;
                while(!q.isEmpty()){
                    int a=q.poll();
                    for(int b:path[a]){
                        if(!has[b]){
                            if(c[a]==c[b]){
                                return "-1";
                            }
                            c[b]=(char)('p'+'d'-c[a]);
                            has[b]=true;
                            q.add(b);
                        }
                    }
                }
                break;
            }
        }
        return new String(c);
    }
}

F小红的矩阵构造

思路见注释：

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(),x=sc.nextInt(),ans[][]=new int[n][m];
        //x必定为偶数，那么x mod 4 的取值只能是0或者2
        if(x%4==0){
            //此时左上角四个都填上x/4，这样每行每列异或为0
            ans[0][0]=ans[0][1]=ans[1][0]=ans[1][1]=x/4;
        }
        else{
            //此时需要考虑x==2
            if(x==2){
                //只有在n和m等于2的时候可以得到{{1,0},{0,1}}，但是题目要求m和n大于等于4，所以直接返回
                System.out.println("-1");
                return;
            }
            //可以先考虑左上的边长为3的正方形，分出6个数先保持异或和为0：
            //填充反对角6个位置为1
            ans[0][1]=ans[0][2]=ans[1][2]=ans[1][0]=ans[2][0]=ans[2][1]=1;
            //填充四角，依旧保持异或为0：
            ans[0][0]=ans[0][m-1]=ans[n-1][0]=ans[n-1][m-1]=(x-6)/4;
        }
        for(int a[]:ans){
            for(int b:a){
                System.out.print(b+" ");
            }
            System.out.println();
        }
    }
}

G小红的元素交换

思路： 1、首先如果没有颜色要求，那么就是找自环就行了，每个环内的交换次数就是环大小减1； 2、加上颜色，对于每个环，如果存在两种颜色，那么必定存在某俩可交换的位置是颜色相反的，否则二者所在的集体不构成环，，那么这样的环依旧可以环大小减1次交换到位； 3、对于某个环，如果其中的颜色单一，那么必然需要先从别的环内交换一个另外颜色的字符，之后进行环内交换，最后把换出去的那个再换回来，也就是比多了2步操作； 4、如何进一步减少次数呢？发现可以在纯色环之间进行交换，也就是纯白环可以先跟纯红环交换一个元素，再各自交换完后换回来，那么相当于只加了一个环的2，那么多余的交换次数，就是2倍的max(纯白环数，纯红环数) 5、还有啊，需要特判，非升序且全部纯色，无解

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),idx[]=new int[n];
        for(int i=0;i<n;i++){
            idx[sc.nextInt()-1]=i;
        }
        String s=sc.next();
        int ans=0,red=0,white=0;
        boolean visited[]=new boolean[n];
        for(int i=0;i<n;i++){
            if(!visited[i]){
                int count=1,p=i;
                boolean hasRed=s.charAt(i)=='R',hasWhite=s.charAt(i)=='W';
                visited[i]=true;
                while(!visited[idx[p]]){
                    count++;
                    p=idx[p];
                    visited[p]=true;
                    if(s.charAt(p)=='R'){
                        hasRed=true;
                    }
                    else{
                        hasWhite=true;
                    }
                }
                ans+=count-1;
                if(count!=1){
                    if(hasRed&&!hasWhite){
                        red++;
                    }
                    else if(!hasRed&&hasWhite){
                        white++;
                    }
                }
            }
        }
        if(ans!=0){
            //此时假如全是一种颜色，但是排列并不是有序的，那么无法交换，无解
            char c[]=s.toCharArray();
            Arrays.sort(c);
            if(c[0]==c[n-1]){
                System.out.println("-1");
                return;
            }
        }
        System.out.println(ans==0?0:ans+Math.max(red,white)*2);
    }
}

待续。。