[关闭]
@rebirth1120 2019-08-08T09:31:04.000000Z 字数 1288 阅读 795

(洛谷P2264) 情书 解题报告

解题报告 洛谷


题目链接

题目大意

直接上题面吧

题目背景

一封好的情书需要撰写人全身心的投入。CYY同学看上了可爱的c**想对她表白,但却不知道自己写的情书是否能感动她,现在他带着情书请你来帮助他。
题目描述

为了帮助CYY,我们定义一个量化情书好坏的标准感动值。判断感动值的方法如下:

  1. 在情书的一句话中若含有给定词汇列表中的特定单词,则感动值加1,但每一单词在同一句话中出现多次感动值不叠加,不同单词不受影响。保证输入的单词不重复。
  2. 每句话以英文句号定界。
  3. 全文不区分大小写。

输入格式

第一行包含一个数字n,表示导致感动值提升的词汇列表中单词的数量,随后n行是给定单词,每行一个。保证单词只包含英文字母。

最后一行为情书正文,保证只包含以下几种字符: 英文字母、数字、空格、英文逗号、英文句号。

输出格式

一个数字g,表示情书带来的感动值。

输入输出样例

输入 #1

3
love
so
much
I love you so much.

输出 #1

3

说明/提示

对于所有的数据,保证1 ≤ n,m,k ≤ >100,每个单词不超过50字符,全文不超过1000字符。

解题思路

第一眼,AC自动机?
看了眼数据范围,……

本来还以为要 kmp 的,但是这里出现的单词必须是一个完整的单词(也就是由空格或逗号或句号隔开的),那么,就直接暴力枚举吧……

虽然是道大水题,但是还是有些坑的,比如什么“全文不区分大小写。”,最后竟然交了 5 次才过……

代码实现

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. using namespace std;
  5. const int N=100+7;
  6. const int M=50+7;
  7. const int S=1000+7;
  8. int n,len[N],ans;
  9. char t[N][M],s[S];
  10. void run(int lst,int end,int k){
  11. int j=1;
  12. for(int i=lst+1;i<end;i++){
  13. if(s[i]==t[k][j]||s[i]==t[k][j]-'a'+'A'||s[i]==t[k][j]-'A'+'a') j++;
  14. else{
  15. j=1;
  16. while(i<end&&s[i]!=' '&&s[i]!=','&&s[i]!='.') i++;
  17. }
  18. if(j==len[k]+1){
  19. j=1;
  20. if(s[i+1]==' '||s[i+1]==','||s[i+1]=='.'){
  21. ans++;
  22. return;
  23. }
  24. }
  25. }
  26. }
  27. int main(){
  28. //freopen("love.in","r",stdin);
  29. cin>>n;
  30. for(int i=1;i<=n;i++){
  31. scanf("%s",t[i]+1);
  32. len[i]=strlen(t[i]+1);
  33. }
  34. gets(s);
  35. gets(s+1);
  36. int lst=0;
  37. for(int i=1;i<=strlen(s+1);i++){
  38. if(s[i]!='.') continue;
  39. for(int j=1;j<=n;j++) run(lst,i,j);
  40. lst=i;
  41. }
  42. printf("%d\n",ans);
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注