竞赛讨论区 > 牛客IOI周赛23-提高组题解

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

头像
Deep_Kevin
编辑于 2021-03-09 15:30:44 APP内打开
赞 3 | 收藏 1 | 回复4 | 浏览748

正题

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

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

下面就是正经的题解了。

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

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

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

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

推理,有,即

即有

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

需要令最小。

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

4条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐