未完待续。。。

C小红的白色字符串

思路：1、由于大写字母只能出现在单词首位，且不能出现在小写字母后边，因此删除一个大写字母要优于删除小写字母的效果

2、字符串肯定是一段大写接着是一段小写的，处理一段大写字母，只需删除到大写字母不出现在小写字母后边就行了

3、注意区分前边有无小写祖母段的情况（其实最多一段这样的段）

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(),ans=0;
        boolean hasLower=false;//记录是否出现过小写字母
        for(int i=0;i<n;){
            if(Character.isUpperCase(s.charAt(i))){
                int j=i;
                while(j<n&&Character.isUpperCase(s.charAt(j))){
                    j++;
                }
                ans+=hasLower?(j-i+1)/2:(j-i)/2;
                i=j;
            }
            else{
                hasLower=true;
                i++;
            }
        }
        System.out.println(ans);
    }
}

E小红的小红走矩阵

思路：1、首先确定路线的形式：

1 2
1 3
3
4
5
.
.
.
20 21. . .25

此路线：右下左之后向下到最底面再一路向右，正好比最短的m+n-2多2，而且肯定放要小于m*n-1

2、现在保证路线不会偏离，需要在路线周围添加围挡，变成：

1 2 2
1 3 3
3 3 
4 4
5 5
. .
. .
.  21. . .25
20 21. . .25

3、其他位置随便填就得了，，为了保证不存在超过一半的字母，建议尽可能用上26种字母

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]),m=Integer.parseInt(arr[1]),ans[][]=new int[n][m];
        for(int i=0;i<n;i++){
            Arrays.fill(ans[i],-1);
        }
        ans[0][0]=0;
        //填充首列：
        for(int i=1;i<n;i++){
            ans[i][0]=(ans[i-1][0]+1)%26;
        }
        //填充最后一行：
        for(int j=1;j<m;j++){
            ans[n-1][j]=(ans[n-1][j-1]+1)%26;
        }
        //修改特殊位置：
        ans[0][1]=ans[0][2]=1;
        ans[1][0]=0;
        ans[1][1]=ans[2][1]=ans[1][2]=25;
        //填充剩余空位置：
        int count[]=new int[26];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(ans[i][j]!=-1){
                    count[ans[i][j]]++;
                }
            }
        }
        for(int i=0,k=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(ans[i][j]==-1){
                    while(count[k]>=n*m/3){
                        k=(k+1)%26;
                    }
                    ans[i][j]=k;
                    count[k]++;
                    //System.out.println(k);
                }
            }
        }
        for(int a[]:ans){
            for(int b:a){
                bw.write((char)(b+'a'));
            }
            bw.write("\n");
        }
        bw.flush();
    }
}

F小红的好子串询问

思路：通过枚举局部，发现只能是“red”或者“der”的无限重复的子串才能符合要求，且由于字符是三个以循环，需要用树状数组维护idx%3对应三种字母的前缀和，开9倍空间，，每个询问计算正反循环共6种情况的最小值即可

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));
        Map<Character,Integer> map=new HashMap<>();
        map.put('r',0);
        map.put('e',1);
        map.put('d',2);
        String arr[]=bf.readLine().split(" ");
        int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]),count[][][]=new int[n+5][3][3];
        char c[]=bf.readLine().toCharArray();
        for(int i=1;i<=n;i++){
            update(count,map.get(c[i-1]),i,i%3,1);
        }
        for(int i=0;i<q;i++){
            arr=bf.readLine().split(" ");
            int op=Integer.parseInt(arr[0]);
            if(op==1){
                int idx=Integer.parseInt(arr[1]);
                char ch=arr[2].charAt(0);
                update(count,map.get(ch),idx,idx%3,1);
                update(count,map.get(c[idx-1]),idx,idx%3,-1);
                c[idx-1]=ch;
            }
            else{
                int l=Integer.parseInt(arr[1]),r=Integer.parseInt(arr[2]),ans=(int)1e9;
                for(int j=0;j<3;j++){
                    for(int k=-1;k<=1;k+=2){
                        ans=Math.min(ans,find(count,l,r,j,k));
                    }
                }
                bw.write(ans+"\n");
            }
        }
        bw.flush();
    }
    static int find(int count[][][],int l,int r,int a,int neg){
        int ans=0;
        for(int i=0;i<3;i++){
            ans+=get(count,i,r,(a+3+neg*i)%3)-get(count,i,l-1,(a+3+neg*i)%3);
        }
        return r-l+1-ans;
    }
    static int get(int count[][][],int a,int idx,int remain){
        int ans=0;
        for(int i=idx;i!=0;i-=i&-i){
            ans+=count[i][a][remain];
        }
        return ans;
    }
    static void update(int count[][][],int a,int idx,int remain,int inc){
        for(int i=idx;i<count.length;i+=i&-i){
            count[i][a][remain]+=inc;
        }
    }
}