XJTUOJ #1193. 表象[弹幕偏执症]

题目

https://oj.xjtuicpc.com/problem/1193

恋恋天下第一！（然而本菜鸡总是被阿空锤死而根本开不了normal）TAT

思路

挺吓人的一道题，看起来很像是要匹配加字符串算法乱搞。但是既然放在套题的第一道想必其实是简单题。（2e6的数据范围基本上是线性算法了，除非出题人卡常）

反正我什么字符串算法都不会，那不妨暴力乱搞一波。我们令\(n=strlen(S),m=strlen(T)\)

考虑S[0]作为前缀，那显然新增种数为\(m\)，没有任何重复。

S[1]作为前缀时哪些会重复呢？我们手玩一下数据。S="ababa" T="babab"

ababa babab

a babab

a abab

a bab

a ab

a b

ab babab

ab bab

ab b

不难发现，如果当前的前缀是S[0]到S[i]，后缀为T[j]到T[m]，当T[j-1]==S[i]时它与之前的情况重复掉了，没有贡献。

所以我们只要对每个字母x预处理出T中有多少后缀使得它前面一位是x即可。

代码

点击查看代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define maxn 2000010

#define ll long long

using namespace std;

char S[maxn],T[maxn];

int cnt[26];

int main(){

    int n,m,i,j;

    ll ans=0;

    scanf("%s%s",S,T);

    n=strlen(S);

    m=strlen(T);

    for(i=0;i<m-1;++i) cnt[T[i]-'a']++;

    ans+=m;

    for(i=1;i<n;++i){

        ans+=m-cnt[S[i]-'a'];

    }

    printf("%lld",ans);

    // system("pause");

    return 0;

}

巴特西

XJTUOJ #1193. 表象[弹幕偏执症]

题目

思路

代码

最新文章

热门文章