CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看Sgu/506的源代码
←
Sgu/506
因为以下原因,你没有权限编辑本页:
你刚才请求的操作只对属于该用户组的用户开放:
用户
您可以查看并复制此页面的源代码:
[[分类:组合数学]] ==摘要== {{信息题|Subsequences Of Substrings|http://acm.sgu.ru/problem.php?contest{{=}}0&problem{{=}}506|1|100|没有用lld|10|time=2015-2-22 21:08:21}} (AC 458) ==题意== 给定字符串s1,s2,要求s1首尾去除若干连续位后,s2仍然是s1的子串(子串的定义是s1移除若干位后为s2,如ac是abc的子串)。 ==题解== *栗子1: xbaax baa 容易得到方案数为2*2=4种 *栗子2: xbaaxbaax baa 容易得到方案数为对于第一个baa,方案数为2*6种,第二个baa,除去之前算过的,共4*2种,合起来共20种。 *栗子3: xbaaa baa 容易得到方案数为2*2=4种(按照最前的匹配运算即可,同栗子1) *类比得到匹配一段字符串从索引i至索引j,其方案数为: (s1.size()-j)*(i-last)//last为上一个i 统计求和即可<ref>http://vawait.com/sgu-506/</ref>,详见代码。 ==代码== {{折叠|506.cpp代码已折叠 |<pre> #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; } </pre> |sgu506}} ==参考资料和拓展阅读== <references/>
该页面使用的模板:
模板:=
(
查看源代码
)
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
Sgu/506
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接