模拟赛题讲解[10]

来自 xpp 2022-08-03 noi.ac #2723

题目描述

lzr给了xpp一个字符串 $s$ 和一个字符串 $t$ ，xpp想通过 $s$ 构造出 $t$ ，构造方式为xpp每次选择 $s$ 的一个子序列，放到当前串的后面，xpp想知道他需要构造多少次才能构造出 $t$ 呢？

输入格式

第一行一个数 $T$ 表示数据组数。

对于每组数据第一行一个字符串 $s$ ，第二行一个字符串 $t$ ，含义见题目描述

输出格式

每组数据输出一行表示次数。如果不能输出 $-1$。

输入1：

3
aabce
ace
abacaba
aax
ty
yyt

输出1：

1
-1
3

数据规模：

对于 $30\%$ 的数据， $\texttt{字符串长度} \le 100$

对于 $100\%$ 的数据，$\texttt{字符串长度} \le 10^5,~1\le T\le 10$

题解：

暴力的解法就是遍历 $t$ ，然后维护一个指针 $p$ 在 $s$ 上跳

仔细观察可以发现，如果 $s=\tt{aaabbbbbbc}$ ， $t=\tt{ac}$

那么 $p$ 就会慢悠悠的从 $s$ 的第一个 $\tt{a}$ 一直跑到最后的 $\tt{c}$

考虑维护一个 $\text{nx}_{i,j}$ 表示 $i$ 后面出现的第一个字符 $j$ 的位置

这个东西的预处理还是很有趣的，我当时没想到怎么搞，然后就用二分草过了

for(int i=0; i<26; i++)
    for(int j=1; j<=n+1; j++)
        nx[i][j]=n+1;
for(int i=0; i<26; i++)
    for(int j=n; j>=1; j--)
        nx[i][j]=(s[j]=='a'+i)?j:nx[i][j+1];

时间复杂度 $O(Qn)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,m,nx[26][N];
char s[N],t[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q;cin >> Q;
    while(Q--)
    {
        cin >> (s+1) >> (t+1);
        n=strlen(s+1); m=strlen(t+1);
        for(int i=0; i<26; i++)
            for(int j=1; j<=n+1; j++)
                nx[i][j]=n+1;
        for(int i=0; i<26; i++)
            for(int j=n; j>=1; j--)
                nx[i][j]=(s[j]=='a'+i)?j:nx[i][j+1];
        int p=1,ans=1;
        for(int i=1; i<=m; i++)
        {
            int c=t[i]-'a';
            if(nx[c][1]==n+1) {ans=-1; break;}
            if(nx[c][p]==n+1) ++ans,p=1;
            p=nx[c][p]+1;
        }
        cout << ans << '\n';
    }
    return 0;
}

顺便附上我的考场代码（二分写法）

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,m,p;
vector<int> ck[27];
string s,t;
void solve()
{
    cin >> s >> t; p=-1; int res=0;
    n=s.size(); m=t.size();
    for(int i=0; i<26; i++) ck[i].clear();
    for(int i=0; i<n; i++) ck[s[i]-'a'].push_back(i);
    for(int i=0; i<m; i++)
    {
        int c=t[i]-'a';
        if(ck[c].empty()) return cout << "-1\n",void(0);
        int nx=upper_bound(ck[c].begin(),ck[c].end(),p)-ck[c].begin();
        if(nx>=ck[c].size())
        {
            ++res;p=ck[c][0];
        }
        else p=ck[c][nx];
        // cout << p << '\n';
    }
    cout << res+1 << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q;
    while(Q--) solve();
    return 0;
}