C~F Java题解，代码已去冗余~~~~

C 移动

本质上，就是寻找区间内障碍物的左右端点的距离，这个问题可以预处理一下每个位置左右最近的障碍物在哪里，时间复杂度O(n+q)

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));
        StringTokenizer st=new StringTokenizer(bf.readLine());
        int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken()),l[]=new int[n+5],r[]=new int[n+5];
        String s=bf.readLine();
        r[n+1]=n+1;
        for(int j=1;j<=n;j++){
            l[j]=s.charAt(j-1)=='#'?j:l[j-1];
        }
        for(int j=n;j>0;j--){
            r[j]=s.charAt(j-1)=='#'?j:r[j+1];
        }
        for(int j=0;j<q;j++){
            st=new StringTokenizer(bf.readLine());
            int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken());
            if(x>y){
                x^=y;
                y^=x;
                x^=y;
            }
           bw.write(Math.max(0,l[y]-r[x]+1)+"\n");
        }
        bw.flush();
    }
}

D 字符串操作

操作的区间越靠前越好，且操作的趋近必须字母序要升高，因此需要找到这样一个不是z的位置升到z，再找到后边最长的能升同样距离，且不超过z的最长段进行上升，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char s[]=sc.next().toCharArray();
        for(int i=0;i<n;i++){
            if(s[i]!='z'){
                int d='z'-s[i];
                for(int j=i;j<n;j++){
                    char c=(char)((s[j]-'a'+d)%26+'a');
                    if(c>=s[j]){
                        s[j]=c;
                    }
                    else{
                        break;
                    }
                }
                break;
            }
        }
        System.out.println(new String(s));
    }
}

E 平衡排列

首先特判sum是奇数的情况；；当偶数的的时候，需要从n到1逐渐先凑出sum/2，具体操作为，当前值不大于剩余的值就留下，否则直接留下剩余值并结束，时间复杂度O(Tn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt();
            long sum=n*(n+1L)/2;
            if(sum%2==1){
                System.out.println(-1);
            }
            else{
                sum>>=1;
                boolean has[]=new boolean[n+5];
                for(int j=n;j>0&&sum>0;j--){
                    if(sum>=j){
                        sum-=j;
                        System.out.print(j+" ");
                        has[j]=true;
                    }
                    else{
                        has[(int)sum]=true;
                        System.out.print(sum+" ");
                        break;
                    }
                }
                for(int j=1;j<=n;j++){
                    if(!has[j]){
                        System.out.print(j+" ");
                    }
                }
                System.out.println();
            }
        }
    }
}

F 小苯的序列分段

首先b再a中的相对顺序要正确，其次前缀最大值和后缀最大值要等于b的首尾两项，，利用线段树处理区间最大值，将以b在a中位置的每个分割的可能性的数量相乘即可，时间复杂度O(T(m+nlogn))

import java.util.*;
public class Main{
    static int mod=998244353;
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        for(int i=sc.nextInt();i!=0;i--){
            int n=sc.nextInt(),m=sc.nextInt(),a[]=new int[n],b[]=new int[m],idx[]=new int[n+5];
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
                idx[a[j]]=j;
            }
            long ans=1;
            for(int j=0;j<m;j++){
                b[j]=sc.nextInt();
                if(j>0&&idx[b[j-1]]>idx[b[j]]){
                    ans=0;
                }
            }
            SegTree st=new SegTree(0,n-1);
            build(st,a);
            if(find(st,0,idx[b[0]])!=b[0]||find(st,idx[b[m-1]],n-1)!=b[m-1]){
                ans=0;
            }
            else{
                for(int j=0;j<m-1&&ans!=0;j++){
                    int count=0;
                    for(int k=idx[b[j]];k<idx[b[j+1]];k++){
                        if(find(st,idx[b[j]],k)==b[j]&&find(st,k+1,idx[b[j+1]])==b[j+1]){
                            count++;
                        }
                    }
                    ans=ans*count%mod;
                }
            }
            System.out.println(ans);
        }
    }
    static int find(SegTree st,int a,int b){
        int l=st.l,r=st.r;
        if(a==l&&r==b){
            return st.max;
        }
        int mid=(l+r)>>1;
        return b<=mid?find(st.left,a,b):a>mid?find(st.right,a,b):Math.max(find(st.left,a,mid),find(st.right,mid+1,b));
    }
    static void build(SegTree st,int a[]){
        int l=st.l,r=st.r;
        if(l==r){
            st.max=a[l];
        }
        else{
            int mid=(l+r)>>1;
            st.left=new SegTree(l,mid);
            st.right=new SegTree(mid+1,r);
            build(st.left,a);
            build(st.right,a);
            st.max=Math.max(st.left.max,st.right.max);
        }
    }
}
class SegTree{
    int l,r,max;
    SegTree left,right;
    SegTree(int l,int r){
        this.l=l;
        this.r=r;
    }
}