牛客小白月赛19 F/H/J 题解

比赛链接:https://ac.nowcoder.com/acm/contest/2272


F -「水」悠悠碧波

题意:给定一个字符串s找最长的一个子串t,满足ts的前后缀且t至少出现3次。

思路:考虑kmpnext数组,根据定义答案一定在next[n],next[next[n]]...里,相当于求出next数组以后我们遍历next[n],next[next[n]]..然后判断相应的前缀出现次数即可,再考虑对于每个位置i我们指定它的父亲是next[i],那么我们可以得到一个fail树,且i的所有祖先都是以i为后缀能匹配的前缀,所以对于指定前缀i,它的出现次数就是以它为根的子树大小,可以显示或隐式的求一遍子树大小即可,时间复杂度O(n)

代码:

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
int i,j,len,ans,nxt[N],cnt[N];
char s[N];
int main(){
    scanf("%s",s+1);len=strlen(s+1);
    for (nxt[1]=j=0,i=2;i<=len;nxt[i++]=j){
        while (j&&s[j+1]!=s[i]) j=nxt[j];
        j+=(s[j+1]==s[i]);
    }
    for (i=1;i<=len;++i) cnt[i]=1;
    for (i=len;i>=1;--i) cnt[nxt[i]]+=cnt[i];
    for (ans=nxt[len];ans;ans=nxt[ans]){
        if (cnt[ans]>=3) break;
    }
    for (i=1;i<=ans;++i) putchar(s[i]);
    puts("");
    return 0;
}

H -「土」巨石滚滚

题意:大概就是起始体力为m,需要经过n次试炼,每次先减a_i,然后加b_i,中途体力小于0即试炼失败,现在可以rearrangen次试炼,问是否能使试炼成功。

思路:贪心,先按差值排序,然后b_i-a_i大于等于0的肯定a_i小的放前面,小于0的肯定让b_i大的放前面,然后模拟一遍即可。
代码:

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
struct Node{
    int a,b,c;
}a[N];
int T,n,m,i,idx;
inline bool cmp1(const Node&A,const Node&B){return A.c>B.c;}
inline bool cmp2(const Node&A,const Node&B){return A.a<B.a;}
inline bool cmp3(const Node&A,const Node&B){return A.b>B.b;}
int main(){
    for (read(T);T--;){
        read(n),read(m);
        for (idx=0,i=1;i<=n;++i){
            read(a[i].a),read(a[i].b);
            a[i].c=a[i].b-a[i].a;
            idx+=a[i].c>0;
        }
        if (idx==n){
            puts("Yes");
            continue;
        }
        sort(a+1,a+1+n,cmp1);
        sort(a+1,a+1+idx,cmp2);
        sort(a+1+idx,a+1+n,cmp3);
        bool flag=0;
        for (i=1;i<=n;++i){
            if (m<a[i].a){
                flag=1;
                break;
            }
            m+=a[i].c;
        }
        puts(flag?"No":"Yes");
    }
    return 0;
}

J - 「火」皇家烈焰

题意:略。
思路:定义dp[i][0/1][0/1]表示考虑前i个位置,当前位有无火焰,下一位有无火焰的方案数,分类讨论转移即可,时间复杂度O(n)
代码:

#include<bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e6+10;
const int P=1e9+7;
int n,i,dp[N][2][2];
char s[N];
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    dp[0][0][0]=dp[0][0][1]=1;
    for (i=1;i<=n;++i){
        if (s[i]=='0'){
            dp[i][0][0]=dp[i-1][0][0];
        }
        else if (s[i]=='1'){
            dp[i][0][0]=dp[i-1][1][0];
            dp[i][0][1]=dp[i-1][0][0];
        }
        else if (s[i]=='2'){
            dp[i][0][1]=dp[i-1][1][0];
        }
        else if (s[i]=='*'){
            dp[i][1][0]=dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%P;
        }
        else if (s[i]=='?'){
            dp[i][0][0]=dp[i][0][1]=(dp[i-1][0][0]+dp[i-1][1][0])%P;
            dp[i][1][0]=dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%P;
        }
    }
    printf("%d\n",(dp[n][0][0]+dp[n][1][0])%P);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注