【HT-089-Div.4】核桃新手组周赛

https://htoj.com.cn/cpp/oj/contest/detail?cid=22589816735488

P10983 替换

特殊性质 20 分

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        string s,t;
        cin>>s>>t;
        if(s.size()<t.size())
            cout<<"NO\n";
        else
            cout<<"YES\n";
    }
    return 0;
}

子串性质，暴力枚举 40 分

#include<bits/stdc++.h>
using namespace std;
string s,t;
// 检查 s[l]~s[r] 是不是 t[0]~t[t.size()-1]
bool check(int l,int r){
    for(int i=l;i<=r;i++)
        if(s[i]!='?' && s[i]!=t[i-l])
            return false;
    return true;
}
void work(){
    cin>>s>>t;
    // 希望 t 是 s 的某个子串
    if(s.size()<t.size())
    {      
        cout<<"NO\n";
        return;
    }
    for(int i=0;i+t.size()-1<s.size();i++){
        // 如果 t 是 s[i]~s[i+t.size()-1] 就找到了
        if(check(i,i+t.size()-1))
        {
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
    return;
}
int main(){
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

正解

容易发现问号能用上就用，不然就浪费了。

#include<bits/stdc++.h>
using namespace std;
string s,t;
void work(){
    cin>>s>>t;
    // 希望 t 是 s 的某个子序列
    for(int i=0,j=0;i<t.size();i++){
        // 在 s[j]~末尾寻找 t[i]
        while(j+1<s.size() && s[j]!='?' && s[j]!=t[i])
            j++;
        // 1. 停在匹配的位置
        // 2. 找不到的时候停在最后一位
        if(s[j]=='?' || s[j]==t[i])
            j++;
        else
        {
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
    return;
}
int main(){
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

P10984 爱好

处理 R=1，意外拿到 40 分

#include<bits/stdc++.h>
using namespace std;
int r,c;
string s;
// cnt[i][1]: s[0]~s[i] 有几个 A
// cnt[i][2]: s[0]~s[i] 有几个 AB
// cnt[i][3]: s[0]~s[i] 有几个 ABC
long long cnt[1005][4];
int main(){
    cin>>r>>c;
    cin>>s;
    // 在 s 里面找 ABC
    cnt[0][1]=cnt[0][2]=cnt[0][3]=0;
    if(s[0]=='A')
        cnt[0][1]=1;
    for(int i=1;i<s.size();i++)
    {
        // 先继承之前的数量
        cnt[i][1]=cnt[i-1][1];
        cnt[i][2]=cnt[i-1][2];
        cnt[i][3]=cnt[i-1][3];
        // 看一下这一位多了几个
        if(s[i]=='A')
            cnt[i][1]++;
        // 之前几个 A 这里就有几个 AB
        if(s[i]=='B')
            cnt[i][2]+=cnt[i][1];
        // 之前几个 AB 这里就有几个 ABC
        if(s[i]=='C')
            cnt[i][3]+=cnt[i][2];
    }
    cout<<cnt[s.size()-1][3];
    return 0;
}

每一行每一列都按照40分的代码处理

#include<bits/stdc++.h>
using namespace std;
int r,c;
// cnt[i][1]: s[0]~s[i] 有几个 A
// cnt[i][2]: s[0]~s[i] 有几个 AB
// cnt[i][3]: s[0]~s[i] 有几个 ABC
string s;
long long cnt[1005][4];
// 返回字符串 s 里面有几个 ABC
int cal(){
    // 在 s 里面找 ABC
    cnt[0][1]=cnt[0][2]=cnt[0][3]=0;
    if(s[0]=='A')
        cnt[0][1]=1;
    for(int i=1;i<s.size();i++)
    {
        // 先继承之前的数量
        cnt[i][1]=cnt[i-1][1];
        cnt[i][2]=cnt[i-1][2];
        cnt[i][3]=cnt[i-1][3];
        // 看一下这一位多了几个
        if(s[i]=='A')
            cnt[i][1]++;
        // 之前几个 A 这里就有几个 AB
        if(s[i]=='B')
            cnt[i][2]+=cnt[i][1];
        // 之前几个 AB 这里就有几个 ABC
        if(s[i]=='C')
            cnt[i][3]+=cnt[i][2];
    }
    return cnt[s.size()-1][3];
}
char g[1005][1005];
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>g[i][j];
    long long ans = 0;
    // 每一行算一下
    for(int i=1;i<=r;i++){
        s="";
        for(int j=1;j<=c;j++)
            s+=g[i][j];
        ans+=cal();
    }
    // 每一列算一下
    for(int j=1;j<=c;j++)
    {
        s="";
        for(int i=1;i<=r;i++)
            s+=g[i][j];
        ans+=cal();
    }
    cout<<ans;
    return 0;
}