题解 | 牛客周赛 Round 41 BCDEF Java

B~F 题解

B 小红的排列构造

首先特判无解的情况，k==1 or k>n 的时候无解，其他情况的，只需要把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(),k=sc.nextInt();
        if(k==1||k>n){
            System.out.println("-1");
        }
        else{
            for(int i=0;i<n;i++){
                int p=sc.nextInt();
                System.out.print((p<=k?p%k+1:p)+" ");
            }
        }
    }
}

C 小红的循环移位

先特判一位数，此时有解的前提是数字本身为4的倍数；否则从最后一位枚举后两位，判断后缀是否为4的倍数，时间复杂度O(len(s))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int n=s.length();
        if(n==1){
            System.out.println(Integer.parseInt(s)%4==0?0:-1);
            return;
        }
        for(int i=0;i<n;i++){
            if((s.charAt((n+i-2)%n)*10+s.charAt((n+i-1)%n))%4==0){
                System.out.println(i);
                return;
            }
        }
        System.out.println("-1");
    }
}

D 小红的好串

容易证明，要想让字母不浪费，必须将区间分为三组，第一组全是r，第二组全是e，第三组全是d，且是哪个组的数量越接近，乘积越大，因此根据区间长度，枚举三个数最接近的时候的各种情况，处理处理得到字母不对应的位子的个数，统计时可用前缀和加速运算，（另外需要特判区间长度小于3时，无需修改，因为无论如何子序列都是0），代码实现的时候可以预处理出偏移量数组，核心算法时间复杂度O(n+q)

import java.util.*;
public class Main{
    static int move[][][][]={{{{0,0},{0,0},{0,0}}},{{{0,0},{0,0},{0,1}},{{0,0},{0,1},{1,1}},{{0,1},{1,1},{1,1}}},{{{0,1},{1,2},{2,2}},{{0,1},{1,1},{1,2}},{{0,0},{0,1},{1,2}}}};
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        Map<Character,Integer> map=new HashMap<>();
        map.put('r',0);
        map.put('e',1);
        map.put('d',2);
        int n=sc.nextInt(),q=sc.nextInt(),pre[][]=new int[n+1][3];
        String s=sc.next();
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1].clone();
            pre[i][map.get(s.charAt(i-1))]++;
        }
        for(int i=0;i<q;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            System.out.println(find(pre,l,r));
        }
    }
    static int find(int pre[][],int l,int r){
        if(r-l<2){
            return 0;
        }
        l--;
        int ans=(int)1e9,d=(r-l)/3;
        for(int m[][]:move[(r-l)%3]){
            int sum=0;
            for(int i=0;i<3;i++){
                sum+=d+m[i][1]-m[i][0]-(pre[l+d*(i+1)+m[i][1]][i]-pre[l+d*i+m[i][0]][i]);
            }
            ans=Math.min(ans,sum);
        }
        return ans;
    }
}

E 小红的树上赋值（easy） and F 小红的树上赋值（hard）

通过观察可知，树可以在每个红色节点头顶处截断，形成若干连通块，连通块内的数字之和为0即可，划分连通块可以一次遍历得到；下边来看如何分配节点的值，为了使得绝对值之和尽可能大，节点值尽可能是绝对值最大数字，且往接近0的方向变化，也就是比在赋值的时候，记录当前总和，总和大于0则填充l否则填充r，直到最后，根据sum的值，选择调整其中的正数或者负数，时间复杂度O(n)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),l=Integer.parseInt(arr[1]),r=Integer.parseInt(arr[2]),group[]=new int[n+5];
        String s=bf.readLine();
        long ans[]=new long[n+5];
        List<Integer> path[]=new List[n+5],list[]=new List[n+5];
        for(int i=1;i<=n;i++){
            path[i]=new ArrayList<>();
            list[i]=new ArrayList<>();
            group[i]=i;
        }
        for(int i=0;i<n-1;i++){
            arr=bf.readLine().split(" ");
            int u=Integer.parseInt(arr[0]),v=Integer.parseInt(arr[1]);
            path[u].add(v);
            path[v].add(u);
        }
        find(1,1,path,list,s,new boolean[n+5]);
        for(int i=1;i<=n;i++){
            if(list[i].size()>0){
                if(s.charAt(i-1)=='W'){
                    for(int a:list[i]){
                        ans[a]=r>=-l?r:l;
                    }
                }
                else{
                    //为了使得绝对值之和最大，要尽量让每个位置的数字不为0，先用绝对值最大的数字去尝试填充
                    long sum=0;
                    for(int a:list[i]){
                        if(sum<=0){
                            sum+=r;
                            ans[a]=r;
                        }
                        else{
                            sum+=l;
                            ans[a]=l;
                        }
                    }
                    if(sum!=0){
                        for(int a:list[i]){
                            if(sum>0&&ans[a]>0||sum<0&&ans[a]<0){
                                ans[a]-=sum;
                                break;
                            }
                        }
                    }
                }
            }
        }
        for(int i=1;i<=n;i++){
            bw.write(ans[i]+" ");
        }
        bw.flush();
    }
    static void find(int k,int parent,List<Integer> path[],List<Integer> list[],String s,boolean has[]){
        //给相邻的点分组
        has[k]=true;
        if(s.charAt(k-1)=='R'){
            parent=k;
        }
        list[parent].add(k);
        for(int a:path[k]){
            if(!has[a]){
                find(a,parent,path,list,s,has);
            }
        }
    }
}