JZTXT

牛客小白赛 65 题解

发布时间 2023-07-21 09:05:34作者: shyiaw

牛客小白赛 65

A. 牛牛去购物

标签

统计类 DP

思路

  1. 因为值域很少，故可设 \(dp_i\) 表示 \(i\) 是否出现过。则初始化为 \(dp_{0}=1\)，之后分别从 \(1\) 到 \(x\) 进行转移方程 \(dp_i|=dp_{i-x},i-x\ge 0\)，其中 \(x=a,b\)。
  2. 时间复杂度为 \(\mathcal O(T)\)，\(T\) 为值域。

代码

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int dp[maxn],n,a,b;
int main()
{
    cin>>n>>a>>b;
    dp[0]=1;
    for(int i=a;i<=n;i++)
        dp[i]|=dp[i-a];
    for(int i=b;i<=n;i++)
        dp[i]|=dp[i-b];
    int ans=0;
    for(int i=1;i<=n;i++)
        if(dp[i])ans=max(ans,i);
    printf("%d",n-ans);
    return 0;
}

B. 牛牛写情书

标签

KMP 字符串

思路

  1. 将特殊字符的 ascii 码统计下来，遍历字符串 \(a\)，将非特殊字符加入到新字符串 \(a'\) 中。
  2. 以 \(b\) 为模式串，\(a'\) 为主串进行 KMP。
  3. 时间复杂度为 \(\mathcal O(\max(len_a,len_b))\)

代码

点击查看代码 
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
const char consts[39]={'0', '1', '2', '3', 
                '4', '5', '6', '7',
                '8', '9', '+', '-',
                '*', '|', ',', '.',
                '~', '!', '@', '#',
                '$', '%', '^', '&', 
                '(', ')', '[', ']',
                '{', '}', '"', ';', 
                ':', '?', '<', '>',
                '\\', '/'};
char a[maxn],b[maxn],sa[maxn];
int n,m,nxt[maxn],vis[300],ni;
int main()
{
    for(int i=0;i<39;i++)
        vis[int(consts[i])]=1;
    vis[39]=1;
    scanf("%d%d",&n,&m);
    cin>>a+1>>b+1;
    for(int i=1;i<=n;i++)
        if(!vis[int(a[i])]) 
            sa[++ni]=a[i];
    for(int i=2,j=0;i<=m;i++)
    {
        while(j&&b[i]!=b[j+1])
            j=nxt[j];
        j+=(b[i]==b[j+1]);
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=ni;i++)
    {
        while(j&&sa[i]!=b[j+1])
            j=nxt[j];
        j+=(sa[i]==b[j+1]);
        if(j==m)
        {
            cout<<"YES";
            return 0;
        }
    }
    printf("NO");
    return 0;
}