专栏文章

题解:CF91A Newspaper Headline

CF91A题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqc6pxk
此快照首次捕获于
2025/12/04 02:24
3 个月前
此快照最后确认于
2025/12/04 02:24
3 个月前
查看原文

题意

输入两个字符串 s1s_1s2s_2 问构成 s2s_2 至少需要几个 s1s_1

思路

虽然用 set 和 vector 也可以,但这样用的知识点较多,所以今天介绍的是本题最见做法,直接枚举。输入后首先看有没有 s2s_2 字符串有的字符但 s1s_1 字符串没有,这种情况输出 -1 因为无论拼多少个 s1s_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 条评论,欢迎与作者交流。

正在加载评论...