（以“分类:组合数学 ==摘要== {{信息题|Subsequences Of Substrings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}506|1|100|没有用lld|10|time=2015...”为内容创建页面） |
小 （→题解： 排版） |
||
| （未显示1个用户的1个中间版本） | |||
| 第9行： | 第9行： | ||
xbaax | xbaax | ||
baa | baa | ||
| − | + | 容易得到方案数为2*2=4种 | |
| + | |||
*栗子2： | *栗子2： | ||
xbaaxbaax | xbaaxbaax | ||
baa | baa | ||
| − | + | 容易得到方案数为对于第一个baa，方案数为2*6种，第二个baa，除去之前算过的，共4*2种，合起来共20种。 | |
| + | |||
| + | *栗子3： | ||
| + | xbaaa | ||
| + | baa | ||
| + | 容易得到方案数为2*2=4种（按照最前的匹配运算即可，同栗子1） | ||
| − | + | *类比得到匹配一段字符串从索引i至索引j，其方案数为： | |
(s1.size()-j)*(i-last)//last为上一个i | (s1.size()-j)*(i-last)//last为上一个i | ||
| − | + | 统计求和即可<ref>http://vawait.com/sgu-506/</ref>，详见代码。 | |
| + | |||
==代码== | ==代码== | ||
{{折叠|506.cpp代码已折叠 | {{折叠|506.cpp代码已折叠 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| Subsequences Of Substrings | ★☆☆☆☆ | 答案正确 | 100 | 2015-2-22 21:08:21 | 没有用lld（10） |
（AC 458）
给定字符串s1,s2，要求s1首尾去除若干连续位后，s2仍然是s1的子串（子串的定义是s1移除若干位后为s2，如ac是abc的子串）。
xbaax baa
容易得到方案数为2*2=4种
xbaaxbaax baa
容易得到方案数为对于第一个baa，方案数为2*6种，第二个baa，除去之前算过的，共4*2种，合起来共20种。
xbaaa baa
容易得到方案数为2*2=4种（按照最前的匹配运算即可，同栗子1）
(s1.size()-j)*(i-last)//last为上一个i
统计求和即可[1]，详见代码。
| 506.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define si(n) scanf("%d",&n)
#define ci const int &
#define lld unsigned long long
#define dsi(n) int n;si(n)
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(i,p,n) for(int i=p;i<=n;++i)
#define fd(i,n) for(int i=n;i!=0;--i)
#define fdi(i,p,n) for(int i=n;i>=p;--i)
int main()
{
string s1,s2;
cin>>s1>>s2;
lld last=-1,ans=0;
fi(i,0,s1.size()-1)
{
if(s1[i]==s2[0])
{
int p=0;
fi(j,i,s1.size()-1)
if(s1[j]==s2[p])
if(++p==s2.size())
{
ans+=(lld)(s1.size()-j)*(i-last);
last=i;
break;
}
}
}
cout<<ans;
return 0;
}
|
CloudLunar