专栏文章
题解:CF91A Newspaper Headline
CF91A题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqc6pxk
- 此快照首次捕获于
- 2025/12/04 02:24 3 个月前
- 此快照最后确认于
- 2025/12/04 02:24 3 个月前
题意
输入两个字符串 和 问构成 至少需要几个 。
思路
虽然用 set 和 vector 也可以,但这样用的知识点较多,所以今天介绍的是本题最见做法,直接枚举。输入后首先看有没有 字符串有的字符但 字符串没有,这种情况输出 -1 因为无论拼多少个 字符串也不会有这个字符。如果没有这样的字符就一个一个找。
代码
CPP#include<bits/stdc++.h>
#define l size()-1
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int dp[27][10005];
int lpos,pos,ans=1;
string s1,s2;
map<char,bool>mp;
int main(){
cin>>s1>>s2;
fo(i,0,s1.l)mp[s1[i]]=1;
fo(i,0,s2.l)
if(!mp[s2[i]])return cout<<-1,0;
fo(i,0,25)
if(mp[i+'a']){
int tmp=s1.l+1;
fd(j,s1.l,0){
if(s1[j]==i+'a')tmp=j;
dp[i][j]=tmp;
}
fo(j,0,s1.l)
if(dp[i][j]==s1.l+1)dp[i][j]=tmp;
}
fo(i,0,s2.l){
if(s2[i]==s2[(i+s2.l)%s2.size()]){
lpos=pos;
pos=dp[s2[i]-'a'][(pos+1)%s1.size()];
}
else{
lpos=pos;
pos=dp[s2[i]-'a'][pos];
}
if(pos<=lpos)ans++;
}
cout<<ans;
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...