BZOJ 2295: 【POJ Challenge】我爱你啊
Description
ftiasch是个十分受女生欢迎的同学,所以她总是收到许多情书。虽然她十分有魅力,然而她却是个低调的人。因此她从来不会告诉别人她到底收到了多少情书。
ftiasch的好朋友1tthinking想知道她到底收到了多少情书。1tthinking知道,ftiasch每次收到一封情书,就会在日记最后写下一个包含”luvletter”子序列的串。比如现在ftiasch的日记是alduddvdletterflusvletetedr,那么ftiasch可能受到了0、1、2封情书。现在给出一些ftiasch的日记,问对于每篇日记,ftiasch最多可能受到多少的情书。
某个序列的子序列是从最初序列通过去除某些元素但不破坏馀下元素的相对位置而形成的新序列。參考wikipedia。
Input
第1行,一个整数 T (0 ≤ T ≤ 100), 日记的数量。
第2到 T + 1行,ftiasch的日记 (只包含’a’-‘z’ 和空格, 长度小于100001)
Output
第1到T行,一个整数, 最大可能的情书数量。
Sample Input
5
t
llllluvletterrr
luvletterlauavalaeatataearaluvletter
is wzk a famous boy yes buz he always receives a lot of luv letters
my heart beats her waves at the shore of the world and writes upon it her signature in tears with the words i love thee
Sample Output
1
3
1
题解
直接模拟、、一开始没看到可以包含空格、、、
刷道水体陶冶情操!
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/* Author:WNJXYK WebSite:http://wnjxyk.cn Weibo:http://weibo.com/WNJXYK */ #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<iostream> using namespace std; char le[500005]; string letter; string pfx="luvletter"; int n; int main(){ scanf("%d",&n);getchar(); for (;n--;){ int Ans=0,p=0; gets(le); letter=le; for (int i=0;i<letter.length();i++){ p+=letter[i]==pfx[p]; if (p==9){ Ans++; p=0; } } printf("%dn",Ans); } return 0; } |

原文链接:BZOJ 2295: 【POJ Challenge】我爱你啊
WNJXYKの博客 版权所有,转载请注明出处。
orz我第一反应直接当DP做了,结果跪TT
其实我是被题目吸引进去做的Orz
orz我第一反应直接当DP做了,结果跪TT
其实我是被题目吸引进去做的Orz
orz我第一反应直接当DP做了,结果跪TT