Gym - 101972H Beautiful Substrings(思维+模拟)

题目链接：点击查看

题目大意：题目的意思挺难理解的。。尤其是对我这种英语渣来说，简单说一下，就是先给出三个数字n,m,k，然后再给出两个字符串a和b，n和m代表的是字符串a和b的长度，然后描述题意：

我们规定美丽子字符串指的是：

字符串b中任意长度的连续子字符串

该子字符串的首字母记做char1，尾字母记做char2，char1和char2满足：

任意一个字符串a中长度为k的连续子字符串

该子字符串的首字母记做char11，尾字母记做char22

满足char1==char11&&char2==char22

只要满足上述条件我们称该子字符串为美丽子字符串，问字符串b中有多少个美丽子字符串

题目分析：只要能看懂题意。。直接模拟即可，时间复杂度是1e5*26

上代码吧，比这代码理解题意应该更好理解一点：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int num[30];bool vis[30][30];int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){memset(num,0,sizeof(num));memset(vis,false,sizeof(vis));int n,m,k;scanf("%d%d%d",&n,&m,&k);string a,b;cin>>a>>b;for(int i=0;i+k-1<n;i++)vis[a[i]-'a'][a[i+k-1]-'a']=true;LL ans=0;for(int i=0;i<m;i++){num[b[i]-'a']++;for(int j=0;j<26;j++){if(vis[j][b[i]-'a'])ans+=num[j];}}printf("%lld\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的Gym - 101972H Beautiful Substrings(思维+模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。