CF Round 966 Div3

A

给定一个字符串，判断是不是大于等于 1 0 2 10^2 102 的形式，例如 1 0 1 9 10^19 1019 -> 1019。

Solution
简单模拟即可，需要特别注意指数为个位数的情况有没有前导 0。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve()
{
    string s; cin>>s;
    if(s.size()>=3&&s[0]=='1'&&s[1]=='0'&&s[2]!='0'&&stoi(s.substr(2))>=2)
    cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return ;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

B

1 − n 1-n 1−n 的座位供车上的人选，第一个人可以任意选，其他人必须选左右至少有一个有人的座位，默认 0 和 n+1 位置没有人，求有没有人不按要求坐。

Solution
简单模拟，注意多测的初始化。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int maxn = 2e5+3;
bool b[maxn];

void solve()
{
    int n; cin>>n;
    for(int i=1;i<=maxn;i++)
    b[i]=0;
    int x,sig=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(i>1&&!b[x-1]&&!b[x+1])
        sig=1;
        b[x]=true;
    }
    if(sig) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return ;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

C

还是模拟，用两个 map 来存数字到字母的映射和字母到数字的映射，如果有一个不符合就直接跳出循环。

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int maxn = 2e5+3;
int a[maxn];

void solve()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int m; cin>>m;
    for(int i=1;i<=m;i++)
    {
        string t;
        cin>>t;
        if(t.length()!=n)
        {
            cout<<"NO"<<endl;
            continue;
        }
        map<int,char> num_to_char;
        map<char,int> char_to_num;
        bool sig=true;
        for(int j=0;j<n;j++)
        {
            int num=a[j+1];
            char ch=t[j];
            // 数字到字母
            if(num_to_char.count(num))
            {
                if(num_to_char[num]!=ch)
                {
                    sig=false;
                    break;
                }
            }
            else num_to_char[num]=ch;
            // 字母到数字
            if(char_to_num.count(ch))
            {
                if(char_to_num[ch]!=num)
                {
                    sig=false;
                    break;
                }
            }
            else char_to_num[ch]=num;
        }
        if(!sig)
        cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return ;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

D

贪心，每次让最左边的 L 和最右边的 R 进行匹配，这样一定最优。

#include<bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;
const int maxn = 2e5+3;
int a[maxn];
int sum[maxn];
int l[maxn],r[maxn];

void solve()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    sum[i]=sum[i-1]+a[i];
    string s;
    cin>>s;
    int cntl=0,cntr=0;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='L') l[++cntl]=i+1;
        else r[++cntr]=i+1;
    }
    // cout<<"LLLL"<<"   ";
    // for(int i=1;i<=cntl;i++)
    // cout<<l[i]<<" "<<" ";
    // cout<<endl;
    // cout<<"RRRRR"<<"   ";
    // for(int i=1;i<=cntr;i++)
    // cout<<r[i]<<" "<<" ";
    // cout<<endl;
    int q=1;
    int ans=0;
    while(l[q]<r[cntr]&&q<=cntl)
    {
        ans+=sum[r[cntr]]-sum[l[q]-1];
        q++,cntr--;
    }
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}