牛客IOI周赛23-提高组题解

正题

首先因为撞题的原因,而导致比赛,给大家带来了不少的困扰,在此说声对不起。

出题人在构造的时候至少自己想了三小时,可能是由于先想算法再想题的原因,导致题目容易翻车,不管你对出题人抱有怎样的不满,不管你对这次的比赛有多么困惑,都是出题人的错,请大家继续相信的比赛。出题人水平不够,如果水平没有提高的话,以后也不太可能出题了,这次出比赛的确挺打击我的自信心的。评论区轻喷。

下面就是正经的题解了。

T1

首先使用kmp算法来找出每一个匹配的位置。为了不给不细心的人一血,改了模数。
考虑使用表示前缀中,提取组合包括i的一个后缀的方案数。

考虑当前位置为,我们枚举前面的断点位置,表示这次选择是,这个区间必须要包括最后一次匹配的位置,如果当前没有匹配过,显然
那么就有,即,其中表示上一次匹配的开头位置。

#include<bits/stdc++.h>
using namespace std;

const int mod=99824353;
const int N=1000010;
char s[N],t[N];
int nex[N],n,m,f[N],sum[N],ss[N];

int main(){
    scanf("%s",s+1);
    scanf("%s",t+1);
    n=strlen(s+1);m=strlen(t+1);
    nex[0]=-1;
    for(int i=1;i<=m;i++){
        int now=nex[i-1];
        while(now!=-1 && t[now+1]!=t[i]) now=nex[now];
        nex[i]=now+1;
    }
    int l=1,r=1;f[0]=sum[0]=ss[0]=1;
    int las=-1;
    while(l<=n){
        r--;while(r!=-1 && t[r+1]!=s[l]) r=nex[r];
        if(r==m-1) las=l-m;
        if(las!=-1) f[l]=ss[las];
        sum[l]=(sum[l-1]+f[l])%mod;
        ss[l]=(ss[l-1]+sum[l])%mod;
        r+=2;l++;
    }
    printf("%d\n",sum[n]);
}

T2

挺套路的,但是实在没有见过原题,就出了出来,再次抱歉。

考虑对于这些数字串建出自动机,然后将图建出来。

我们先在加字符串的时候,将每一个字符串的末尾标记一下,然后建图的时候下传一下标记,即指针若被标记了,那么当前就被标记。

现在我们在整张图上跑数位就可以了,设表示最后剩个位置没填,现在在图上走到的位置的方案数(无前缀0和位的限制)。

时间复杂度就为,可以通过此题。

T3

考虑设表示的星星数,特别的表示的星星数,注意这里的 是有符号的。

发现,如果确定了的值,其他也就确定了。

为平均数,关系表示为,即

推理,有,即

即有

我们将其通通减掉,得到一个序列

需要令最小。

考虑将设置为的中位数即可,证明显然。

全部评论
我觉得吧我发那个帖子也没有特别针对出题人的意思,希望你还能找回自信心😚就是说nowcoder也是一个全方面包括求职等等功能很强的网站,关于竞赛方面为什么人家codeforces atcoder能做得那么好,而你nowcoder却做不出那种感觉呢?希望能有所改善吧!
2 回复
分享
发布于 2021-03-08 12:27
冒昧的问一下,我只是表达疑问。请问出题人,在51nod上名为“Deep_ Kevin  ”的账号是您的吗?提交记录显示,此人在2月6日通过了本次比赛的原题。 信息由群友提出
2 回复
分享
发布于 2021-03-09 10:25
百信银行
校招火热招聘中
官网直投
想出了三道原题() 您能不能想一下今年的联合省选会出啥题啊()
1 回复
分享
发布于 2021-03-09 21:38
别骂了别骂了,谁都会犯错,出题人已经知道错了,给他一个改过自新的机会呗,就不要再去找什么证明了
点赞 回复
分享
发布于 2021-03-09 12:49

相关推荐

3 1 评论
分享
牛客网
牛客企业服务