526互联

Educational Codeforces Round 147 (Rated for Div. 2) A ~ C

发布时间 2023-04-21 22:27:17作者: Yaowww

A. Matching

题意：

　　给定一个字符串，将其中的 ‘？’ 替换成数字，不含前导0，如果字符串前导为0，输出0.。

分析：

　　每个地方有10种可能方案，在特判一下第一位就行了。

代码：

#include <iostream>
#include <string>
#include <cmath>

#define endl '\n'

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int ans=1;
        for(int i=0;i<s.size();i++)
        {
            if(!i&&s[i]=='?') ans*=9;
            else if(s[i]=='?'&&i) ans*=10;
        }
        if(s[0]=='0') cout<<0<<'\n';
        else cout<<ans<<'\n';
    }
}

 

B. Sort the Subarray

题意：

　　给定一个数组以及他的部分排序数组，保证两数组不同，找出最大可能的排序区间。

分析：

　　先从两端开始遍历排除两数组相同元素确定区间，然后做左右区间再向两边扩展求出最大可能区间。

代码：

#include <iostream>
#include <cstdio>

using namespace std;

const int N=2e5+10;

int a[N],b[N];
bool st[N];

int main()
{
    int t;
    scanf("%d",&t);
    
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)
        {
            if(a[i]==b[i]) st[i]=true;
            else st[i]=false;
        }
        int maxn=0;
        int s=0,e=0;
        //cout<<e<<endl;
        for(int i=1;i<=n;i++)
        {
            if(!st[i])
            {
                int j=i+1;
                while(!st[j]&&b[j]>=b[j-1]&&j<=n)
                {
                    j++;
                }
                if(maxn<j-i)
                {
                    maxn=j-i;
                    s=i;
                    e=j-1;
                }
                i=j-1;
            }
        }
        //cout<<e<<endl;
        for(int i=s;i>=1;i--)
        {
            if(b[i]<=b[s])
            {
                s=i;
            }
            else break;
        }
        for(int i=e;i<=n;i++)
        {
            //cout<<b[i]<<endl;
            if(b[i]>=b[e])
            {
                e=i;
            }
            else break;
        }
        printf("%d %d\n",s,e);
    }
}

 

C. Tear It Apart

题意：

　　每次操作i可以选择字符串中不相邻的任意多个点，使操作后字符串元素相同，字符串只含小写字母，求最少操作数。

分析：

　　遍历字符串枚举26个小写字母，找出字符串中每一个单词的相邻最大间隔，最后求出每一种方案的最大间隔中的最小值，对一段区间最少可以每次除2来求出最小次数。

代码：

#include <iostream>
#include <string>

#define endl '\n'

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin>>t;
    
    while(t--)
    {
        string s;
        cin>>s;
        int ans=0x3f3f3f3f;
        for(int i=0;i<26;i++)
        {
            char ch=(char)(i+'a');
            int len=0;
            int cnt=0;
            for(int i=0;i<s.size();i++)
            {
                if(s[i]==ch)
                {
                    len=max(len,cnt);
                    cnt=0;
                }
                else cnt++;
            }
            len=max(len,cnt);
            ans=min(ans,len);
        }
        
        int res=0;
        while(ans)
        {
            res++;
            ans/=2;
        }
        
        cout<<res<<'\n';
    }
}