首页 > 代码库 > 140725模拟赛总结

140725模拟赛总结

2024-07-14 01:32:14   224人阅读


A：hdu4847    字符串匹配
第一想法是KMP，写了好长时间结果还TLE了-_-||，实际上用个简单的枚举判断就能解决。因为待验证的字符串"doge"很小。
写A题的时候还被输入卡了半天。
Tips1:输入至文件结尾(eof)的常用方法：
　　    while (cin>>a)        //最常用的
 　　   while (cin.getline(s,30))    //按行读入前30个字符。空格也读入
  　　  getline(cin,s)        //和getline相似，
Reference：http://www.cnblogs.com/flatfoosie/archive/2010/12/22/1914055.html
Tips2:自己的KMP还是两年前用Pascal写的......
找了个KMP模版，以后用就行：
Reference:http://www.cnblogs.com/183zyz/archive/2011/03/24/1994380.html

 1 # include<stdio.h> 2 # include<string.h> 3  char P[10005],T[1000005]; 4  int next[10005],n,m; 5 void Pnex() 6 {     7     int k,q;     8     next[1]=0;    9     k=0;   10     for(q=2;q<=n;q++)  11     {       12         while(k>0 && P[k+1]!=P[q])   13         {          14             k=next[k];    15         }      16         if(P[k+1]==P[q]) k++; 17         next[q]=k;   18     }19 }20 int main()21 {    22     int i,t,q,num;  23     scanf("%d",&t);    24     getchar();     25     while(t--)     26     {           27         gets(P);    28         gets(T);      29         n=strlen(P);     30         m=strlen(T);    31         for(i=n-1;i>=0;i--)  32             P[i+1]=P[i];    33         for(i=m-1;i>=0;i--)     34             T[i+1]=T[i];          35         Pnex();    36         q=0;     37         num=0;    38         for(i=1;i<=m;i++) 39         {            40             while(q>0 && P[q+1]!=T[i])  41             {              42                 q=next[q];     43             }            44             if(P[q+1]==T[i]) q++; 45             if(q==n)      46             {            47                 num++;       48                 q=next[q];    49             }      50         }          51         printf("%d\n",num);   52     }   53     return 0;54 }
View Code

 


Tips3:补充一个更快的字符串匹配算法：Boyer-Moore算法
Reference：http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

Tips4:补充李大神发的一个神图：


B:hdu4848    搜索+强剪枝
题目大意：图上每个点都有各自的deadline，需要在deadline之前遍历完所有的点。求最少时间
Reference：http://www.tuicool.com/articles/vERnuqZ

C:hdu4849    最短路
D:hdu4850
先留着点，本周一定要写！


联系
我们