CodeForces/412E

摘要

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

• 来自寒假练习：2015 Winter Day 1 div1 H题
• 原题链接：http://codeforces.com/problemset/problem/412/E

题意

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

题解

• 复杂度肯定要求O(n)的，不能暴力枚举判断。写这题的时候，有一种状态机的感觉。按照题目定义，一个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; }