Logo CloudLunar

“CodeForces/412E”的版本间的差异

小 （→‎参考资料和拓展阅读： 标签打错）
小 （→‎题解： 符号优化）
第12行： 第12行：
 
  【default】 --[有字母开头]--> 【a1】 --[碰到'@']--> 【a2】 --[碰到'.']-->【a3】
 
  【default】 --[有字母开头]--> 【a1】 --[碰到'@']--> 【a2】 --[碰到'.']-->【a3】
 
     ↑                          ┃                    ┃                  ┃  
 
     ↑                          ┃                    ┃                  ┃  
−
     ┃                [非字母、数字、'_']        [非字母数字]          [非字母]   
+
     |                  [非字母、数字、'_']        [非字母数字]          [非字母]   
 
     └--------------------------┻---- ---------------┻----------------- ┛       
 
     └--------------------------┻---- ---------------┻----------------- ┛       
 
*在a3状态统计 字母序列1长度*字母序列2长度 即可。
 
*在a3状态统计 字母序列1长度*字母序列2长度 即可。
 +
 
==代码==
 
==代码==
 
{{折叠|412E.cpp代码已折叠
 
{{折叠|412E.cpp代码已折叠

2015年2月27日 (五) 15:38的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
E-mail Addresses ★★☆☆☆ 答案正确 100 2015-02-24 12:42:17 数据类型（0）

题意

给一个字符串，找出其子串中是E-mail的。

题解

  • 复杂度肯定要求O(n)的，不能暴力枚举判断。写这题的时候，有一种状态机[1]的感觉。按照题目定义，一个Email应该满足：
显示/移除行号
  1. {字母序列1+字母、数字、'_'}+{‘@’+字母数字+‘.’}+{字母序列2}
  • 三个{...}看作状态a1,a2,a3，每个状态都有进入条件（开头字符+已经处于前一个状态），扫一遍字符串，每个字符分别判断它属于哪个状态。
显示/移除行号
  1. 【default】 --[有字母开头]--> 【a1】 --[碰到'@']--> 【a2】 --[碰到'.']-->【a3】
  2.     ↑                          ┃                    ┃                  ┃ 
  3.     |                   [非字母、数字、'_']        [非字母数字]          [非字母]   
  4.     └--------------------------┻---- ---------------┻----------------- ┛
  • 在a3状态统计 字母序列1长度*字母序列2长度 即可。

代码

412E.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<string>
  4. using namespace std;
  5. #define dsi(n) int n;scanf("%d",&n)
  6. #define si(n) scanf("%d",&n)
  7. #define f(i,n) for(int i=1;i<=n;++i)
  8. #define fi(n) f(i,n)
  9. #define f0(i,n) for(int i=0;i!=n;++i)
  10. #define fd(i,n) for(int i=n;i>=1;--i)
  11. #define ci const int&
  12. #define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
  13. #define c(x) const x&
  14. class st
  15. {
  16.     int x,y;
  17.     friend bool operator <(const st&a,const st&b){return a.x<b.x;}
  18. };
  19. string s;
  20. unsigned long long a1=0,a2=0,a3=0,p1=0,p2=0,ans=0;//fixed数据类型//
  21. int main()
  22. {
  23. //[{字母+字母数字_}+{@+字母数字+.}+{字母}//
  24. //a1->a2->a3//
  25.     cin>>s;
  26.     foreach(i,s)
  27.     {
  28.         //a3continue;
  29.         if(a3)
  30.         {
  31.             if(isalpha(*i))
  32.             {
  33.                 ++a3;
  34.                 if(a3>=2)
  35.                 {
  36.                     ans+=p1;
  37.                     //cout<<"[]";
  38.                 }
  39.             }
  40.             else
  41.                 a3=0;
  42.         }
  43.         //a3in//
  44.         if(a2>=2/*fixed:>=2而非>0*/&&*i=='.')
  45.             a3=1;
  46.         //a2continue//
  47.         if(!isalnum(*i)&&a2)
  48.             a2=0;
  49.         if(isalnum(*i)&&a2)
  50.             ++a2;
  51.         //a2in//
  52.         if(*i=='@'&&a1)
  53.             ++a2,p1=p2;
  54.         //a1continue//
  55.         if(isalpha(*i)&&a1)
  56.             ++p2;
  57.         if((isalnum(*i)||*i=='_')&&a1)
  58.             ++a1;
  59.         else
  60.             a1=0,p2=0;
  61.         //a1in//
  62.         if(isalpha(*i)&&a1==0)
  63.             ++a1,++p2;
  64.         //cout<<*i<<" "<<a1<<" "<<a2<<" "<<a3<<" "<<p1<<endl;
  65.     }
  66.     cout<<ans;
  67.     return 0;
  68. }


参考资料和拓展阅读

  1. 跳转 ↑ 维基百科 - 有限状态机
取自“https://blog.CloudLunar.com/index.php?title=CodeForces/412E&oldid=1237”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]