模拟赛题讲解[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;
}