A. Matching

橘子熊：这题太简单了我不想写

题面

Description

给定给一个带问号的字符串，求有多少种可能的数字

Input
多次询问，一次一个字符串

Output
对于每次询问，输出可能的数字的总数

数据范围与约定

2e5次询问，单词询问不超过5个字符

思路

主要思路

签到题
大部分情况下，一个问号对答案的贡献的 X10 ，但是存在首位X9的特殊情况，以及前导零对应没有的情况，特判下就行。

完整代码

#include<bits/stdc++.h>
using namespace std ;
void solve(){
    string s ;
    cin>>s ; 
    int len = s.length() ; 
    int ans = 1 ;
    if( s[0] == '0' ){
        cout<<0<<endl ; return ; 
    }
    for( int i = 0 ; i < len ; ++i ){
        if( s[i] == '?' )ans *= 10 ; 
    }
    if( s[0] == '?' )ans = ans*9/10  ; 
    cout<<ans<<endl ; 
}
int main(){
    int t ;
    cin>>t ; 
    while( t-- )solve() ; 
    return 0 ; 
}

B. Sort the Subarray

fxs：哎呀，这道题你想复杂了

题面

Description

给定2个数列，第二个数列是第一个数列的部分排序，求题目要求的最大合法区间

Input
2个数列

Output
最大合法区间

数据范围与约定

1e4次询问，单词询问数列不超过2e5

思路

主要思路

考虑到我们一旦有一个合法区间，那么这个合法区间向左右扩展的条件是：a[i]=b[i]并且符合排序

进一步思考，我们此题可以从两头向中间找不同，当然存在相同的情况，我们再往外扩展，一定能够得到最大值

完整代码

#include<bits/stdc++.h>
using namespace std ;
inline int read(){
    int s=0 ; char g=getchar() ; while( g>'9'||g<'0')g=getchar() ; 
    while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ; 
}
int a[200005] , b[200005]; 
void solve(){
    int n = read() ;
    for( int i = 1 ; i <= n ; ++i )a[i] = read() ;
    for( int i = 1 ; i <= n ; ++i )b[i] = read() ; 
    int l = 0 , r = n ;
    while( l <= n ){
        ++l ;
        if( a[l] != b[l] )break ; 
    }
    while( r >= 1 ){
        if( a[r] != b[r] )break ;
        r-- ; 
    }
    while( l > 1 ){
        if( b[l] >= b[l-1] && a[l-1] == b[l-1] ) l-- ; 
        else break ; 
    }
    while( r < n ){
        if( b[r] <= b[r+1] && a[r+1] == b[r+1]) r++ ; 
        else break ; 
    }
    cout<<l<<" "<<r<<endl ; 
}
int main(){
    int t = read() ; 
    while( t-- )solve() ; 
    return 0 ; 
}

C. Tear It Apart

开始后半个小时不到，橘子熊：我A了

题面

Description

对于一个只含有字母的字符串，每次操作可以删除多个非相邻的字符，问至少多少次操作后，字符串会变为一个全由一个字母组成的字符串

Input
多次询问，每次一个字符串

Output
对于每次询问，输出最少操作次数

数据范围与约定

1e4次询问，单词询问数列不超过2e5

思路

主要思路

考虑到操作是向下兼容的？，也就是说，我一个只需要 k 次操作可以完全处理的区间，k+1次也一定可以处理。那我们就要找到对于每一个区间限制的k

那么，什么限制了我们每一个区间的k值呢？

连续且需要删除的字符串

那么一个合理的思路就出来了：枚举留下哪个字母，计算需要删除的连续最大区间。最后对于每个字母的情况求一下最小值即可。

完整代码

#include<bits/stdc++.h>
using namespace std ;
int get_ans( int s ){
    int tot = 0 ; s-- ;  
    if( s == 0 )return 0 ;
    while( s ){
        tot++ ; 
        s /= 2 ; 
    }
    return tot ; 
}
void solve(){
    string s ;
    cin>>s ; 
    int mi_num[26] ;
    int len = s.length() ; 
    for( int i = 0 ; i < 26 ; ++i )mi_num[i] = -1 ; 
    int ans = (1<<30) ; 
    for( int c = 0 ; c < 26 ; ++c ){
        char g = 'a'+c  ;
        int las = 0 , l = 0 ; 
        while( l <= len ){
            ++l ;
            if( s[l-1] == g ){
                mi_num[c] = max( mi_num[c] , l-las ) ; las = l ;
            }
            else continue ; 
        }
        mi_num[c] = max( mi_num[c] , len-las+1 ) ; 
        ans = min( ans , mi_num[c] ) ; 
    } 
    cout<<get_ans(ans)<<endl ; 
}
int main(){
    int t ;
    cin>>t ; 
    while( t-- )solve() ; 
    return 0 ; 
}