参考资料和拓展阅读: 标签打错
摘要: 比赛名称
 
(未显示1个用户的1个中间版本)
第2行: 第2行:
 
==摘要==
 
==摘要==
 
{{信息题|E-mail Addresses|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/H|2|100|数据类型|0|time=2015-02-24 12:42:17}}
 
{{信息题|E-mail Addresses|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/H|2|100|数据类型|0|time=2015-02-24 12:42:17}}
*来自寒假练习:[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70594 2015 Winter Warm up div2] H题
+
*来自寒假练习:[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70594 2015 Winter Day 1 div1] H题
 
*原题链接:http://codeforces.com/problemset/problem/412/E
 
*原题链接:http://codeforces.com/problemset/problem/412/E
 +
 
==题意==
 
==题意==
 
给一个字符串,找出其子串中是E-mail的。
 
给一个字符串,找出其子串中是E-mail的。
第12行: 第13行:
 
  【default】 --[有字母开头]--> 【a1】 --[碰到'@']--> 【a2】 --[碰到'.']-->【a3】
 
  【default】 --[有字母开头]--> 【a1】 --[碰到'@']--> 【a2】 --[碰到'.']-->【a3】
 
     ↑                          ┃                    ┃                  ┃  
 
     ↑                          ┃                    ┃                  ┃  
     ┃                [非字母、数字、'_']        [非字母数字]          [非字母]   
+
     |                  [非字母、数字、'_']        [非字母数字]          [非字母]   
 
     └--------------------------┻---- ---------------┻----------------- ┛       
 
     └--------------------------┻---- ---------------┻----------------- ┛       
 
*在a3状态统计 字母序列1长度*字母序列2长度 即可。
 
*在a3状态统计 字母序列1长度*字母序列2长度 即可。
 +
 
==代码==
 
==代码==
 
{{折叠|412E.cpp代码已折叠
 
{{折叠|412E.cpp代码已折叠

2015年2月27日 (五) 15:43的最后版本

摘要

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

题意

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

题解

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

代码

412E.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
#define dsi(n) int n;scanf("%d",&n)
#define si(n) scanf("%d",&n)
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(n) f(i,n)
#define f0(i,n) for(int i=0;i!=n;++i)
#define fd(i,n) for(int i=n;i>=1;--i)
#define ci const int&
#define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
#define c(x) const x&
class st
{
    int x,y;
    friend bool operator <(const st&a,const st&b){return a.x<b.x;}
};
string s;
unsigned long long a1=0,a2=0,a3=0,p1=0,p2=0,ans=0;//fixed数据类型//
int main()
{
//[{字母+字母数字_}+{@+字母数字+.}+{字母}//
//a1->a2->a3//
    cin>>s;
    foreach(i,s)
    {
        //a3continue;
        if(a3)
        {
            if(isalpha(*i))
            {
                ++a3;
                if(a3>=2)
                {
                    ans+=p1;
                    //cout<<"[]";
                }
            }
            else
                a3=0;
        }
        //a3in//
        if(a2>=2/*fixed:>=2而非>0*/&&*i=='.')
            a3=1;
        //a2continue//
        if(!isalnum(*i)&&a2)
            a2=0;
        if(isalnum(*i)&&a2)
            ++a2;
        //a2in//
        if(*i=='@'&&a1)
            ++a2,p1=p2;
        //a1continue//
        if(isalpha(*i)&&a1)
            ++p2;
        if((isalnum(*i)||*i=='_')&&a1)
            ++a1;
        else
            a1=0,p2=0;
        //a1in//
        if(isalpha(*i)&&a1==0)
            ++a1,++p2;
        //cout<<*i<<" "<<a1<<" "<<a2<<" "<<a3<<" "<<p1<<endl;
    }
    cout<<ans;
    return 0;
}


参考资料和拓展阅读

  1. 维基百科 - 有限状态机

著作权声明[编辑]

关于[编辑]