题解 | 牛客周赛 Round 38 CDEFG

C小红的字符串构造

思路：尽量用尽可能长的相同的字母连续段构造重复回文，剩下的空间用a-z循环填充

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();
        for(int i=0,count=0,p=0;i<n;i++){
            if(k>0){
                if(k>=count){
                    System.out.print((char)(p+'a'));
                    k-=count;
                    count++;
                }
                else{
                    p=(p+1)%26;
                    System.out.print((char)(p+'a'));
                    count=1;
                }
            }
            else{
                p=(p+1)%26;
                System.out.print((char)(p+'a'));
            }
        }
    }
}

D小红的平滑值插值

思路：假如相邻的之差最大值小于k，那么只需要在某一个空隙中加一个比较小的数字大k的数字，答案是1次；；否则在每个相邻差大于等于k的空隙尝试添加k间隔的数字，从而把最大差控制在k

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(),a[]=new int[n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        long ans=0;
        boolean maxOverK=false;
        for(int i=1;i<n;i++){
            int d=Math.abs(a[i]-a[i-1]);
            if(d>=k){
                maxOverK=true;
                ans+=(d-1)/k;
            }
        }
        System.out.println(maxOverK?ans:ans+1);
    }
}

E小苯的等比数列

思路：首先特判公差为1，也就是相同数字的最大数量；再考虑公差大于1的情况，此时序列中的数字只需判断有或者无，因为每个数字都不一样，配合剪枝：当max/a对公比q取对数的值小于当前答案时即可截断

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),count[]=new int[200005],ans=0;
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            count[a]++;
            ans=Math.max(ans,count[a]);
        }
        Set<Long> set=new HashSet<>();
        for(int i=1;i<=200000;i++){
            if(count[i]>0){
                for(int j=2;j*i<=200000;j++){
                    if(ans>Math.log(400000.0/i)/Math.log(j)){
                        break;
                    }
                    int len=1;
                    long cur=j*i;
                    while(cur<=200000){
                        long p=op(cur,j);
                        if(!set.add(p)){
                            break;
                        }
                        len=count[(int)cur]>0?len+1:0;
                        ans=Math.max(ans,len);
                        cur*=j;
                    }
                }
            }
        }
        System.out.println(ans);
    }
    static long op(long a,long b){
        //映射以a为结尾，公比为b的等比数列的长度
        return a*(long)1e9+b;
    }
}

F小苯的回文询问

思路：预处理对确定的左端点，寻找存在回文的最早右端点，有回文就表示，存在某种字符，在该区间内首次出现和末次出现的位置相差大于1，，用TreeSet有序维护，以上过程用双指针维护，之后只需离线查询

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        Map<Integer,TreeSet<Integer>> map=new HashMap<>();
        int n=sc.nextInt(),q=sc.nextInt(),a[]=new int[n+5],ans[]=new int[n+5];
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=1,j=1,count=0;i<=n;i++){
            while(j<=n&&count==0){
                map.putIfAbsent(a[j],new TreeSet<>());
                TreeSet<Integer> set=map.get(a[j]);
                boolean b=check(set);
                set.add(j);
                if(!b&&check(set)){
                    count++;
                }
                j++;
            }
            ans[i]=count>0?j-1:j;
            TreeSet<Integer> set=map.get(a[i]);
            boolean b=check(set);
            set.remove(i);
            if(b&&!check(set)){
                count--;
            }
        }
        for(int i=0;i<q;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            System.out.println(r>=ans[l]?"YES":"NO");
        }
    }
    static boolean check(TreeSet<Integer> set){
        return !set.isEmpty()&&set.last()-set.first()>1;
    }
}

G小红的区间删除

思路：构造前缀和和后缀的树状数组，双指针删除或者添加数字，找到对于每一个后缀的起点，满足删除的最大区间

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],pre[]=new int[1000005],suf[]=new int[1000005];
        long k=sc.nextLong(),ans=1,count=0;
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
            count+=i-get(suf,a[i]);
            update(suf,a[i],1);
        }
        if(count<k){
            System.out.println("0");
            return;
        }
        for(int i=0,j=0;i<n;i++){
            update(suf,a[i],-1);
            count-=get(suf,a[i]-1)+j-get(pre,a[i]);
            while(count<k){
                update(pre,a[j],1);
                count+=j+1-get(pre,a[j])+get(suf,a[j]-1);
                j++;
            }
            ans+=i-j+1;
        }
        System.out.println(ans);
    }
    static void update(int arr[],int idx,int inc){
        for(int i=idx;i<=1000000;i+=i&-i){
            arr[i]+=inc;
        }
    }
    static int get(int arr[],int idx){
        int ans=0;
        for(int i=idx;i!=0;i-=i&-i){
            ans+=arr[i];
        }
        return ans;
    }
}