The 2017 ACM-ICPC Asia Beijing Regional Contest 北京区域赛 A、Domains

题意

给N个VPN域名规则，由域名模式和VPN名字组成，域名模式中含有通配符，通配符*和#能匹配任何字符串，#只有在其他规则都不匹配时才生效。

合法的VPN域名模式：

1.只能含有通配符、小写字母、数字、点、连字符，

2.不能以点开头或结尾、两个点不能相连，

3.通配符必须在开头，后面跟着.或者空，

4.连字符必须在两个小写字母之间；

合法的VPN名字：

1.只能含有小写字母，数字和连字符，

2.以小写字母开头，

3.连字符必须在两个小写字母之间；

有的规则相互矛盾：

1.存在一个域名能同时匹配这两个规则，

2.因为一个规则的存在，另一个永远不会被匹配。

要求排除不合法的、和前面出现的规则矛盾的规则。

M个询问，每个询问给一个域名模式（保证合法且不含#）代表一个域名集合，求几个VPN规则能匹配该集合。

题解

排除不合法的域名。创建3棵字典树分别储存3种串（带*、带#、不带通配符），然后用字典树排除矛盾的情况。具体排除要讨论的细节太多了，再把合法的规则插入字典树。对询问分类讨论查询字典树。

代码

#include 
    
     using namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,l,r) for(int i=l,ed=r;i
     
      =ed;--i)#define all(x) (x).begin(),(x).end()#define SZ(x) ((int)(x).size())#define pb push_back#define mp make_pair#define se second#define sf(x) scanf("%d",&x)#define db(x) cout<< #x <<"="<<(x)<<" "typedef long long ll;typedef double dd;typedef vector
      
        VI;typedef pair
       
         PII;const ll LINF=0x3f3f3f3f3f3f3f3fLL;const int INF=0x3f3f3f3f;const dd EPS=1e-6;const dd PI=acos(-1.0);const ll mod=1e9+7;const int N=451000;const int MAX_N=40;int n;int get(char c){    if(c>='a'&&c<='z')return c-'a';    if(c>='0'&&c<='9')return c-'0'+26;    if(c=='.')return 36;    if(c=='-')return 37;    if(c=='#')return 38;    if(c=='*')return 39;    return -1;}struct TrieNode{    int cnt;    int lf;    int next[MAX_N];};struct Trie{    TrieNode node[N];    int tot;    char o;    Trie(char o=0):o(o){}    void insert(string&s){        int cur=0;        ++node[cur].cnt;        rep(i,0,SZ(s)){            int p=get(s[i]);            if(node[cur].next[p]==0)                node[cur].next[p]=++tot;            cur=node[cur].next[p];            ++node[cur].cnt;        }        ++node[cur].lf;    }    void init(){        tot=0;        mem(node,0);    }    bool match(string&s,int jin=0){        int cur=0;        rep(i,0,SZ(s)){            int p=get(s[i]);            if(node[cur].next[p]==0){                if(i){                    if(s[i]=='*')return true;//遇到了*，且前面匹配                    if(s[i]=='#'&&o=='#'||node[cur].next[get('#')]&&jin)return true;//遇到了#，另一个后面也是#，前面匹配                }                return (node[cur].next[get('*')]);            }            cur=node[cur].next[p];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     }        return node[cur].lf;    }    int find(string&s,int xin,int &t){        int cur=0;        int ans=0;        rep(i,0,SZ(s)){            int p=get(s[i]);            if(node[cur].next[p]==0){                if(node[cur].next[get('*')]||node[cur].next[get('#')])return t=1;                if(xin&&s[i]=='*')return ans+node[cur].cnt;                return 0;            }            if(node[cur].next[get('*')])t=1;            if(node[cur].next[get('#')])++ans;            cur=node[cur].next[p];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               }        return node[cur].lf;//都匹配了    }}xin('*'),jin('#'),non;bool ckConflict(string s){    int ch=s[0];    reverse(s.begin(),s.end());    if(ch=='#'){        if(jin.match(s,1))return 0;        if(xin.match(s,1))return 0;        jin.insert(s);        return 1;    }else if(ch=='*'){        if(non.match(s))return 0;        if(jin.match(s))return 0;        if(xin.match(s))return 0;        xin.insert(s);        return 1;    }else {        if(non.match(s))return 0;        if(xin.match(s))return 0;        non.insert(s);        return 1;    }}/*a.cpoj.org vpn-chinawww.pku.edu.cn vpn-pku1mail.pku.edu.cn vpn-pku1*.test.pku.edu.cn vpn-pku2//*.test.pku.edu.cn vpn-pku2//*.a.test.pku.edu.cn vpn-pku2*.test2.pku.edu.cn vpn-pku2//*.pku.edu.cn vpn-pku2#.pku.edu.cn vpn-pku0//#.www.pku.edu.cn vpn-pku0*/bool islower(char c){    return c>='a'&&c<='z';}bool ckName(string&s){    if(!s.size())return false;    if(!islower(s[0]))return false;    rep(i,1,SZ(s)){        if(!(islower(s[i])||isalnum(s[i])||s[i]=='-'))            return false;        if(s[i]=='-'){            if(!islower(s[i-1]))return false;            if(i+1==SZ(s)||!islower(s[i+1]))return false;        }    }    return true;}bool ckDomain(string&s){    if(!SZ(s))return false;    if(s[0]=='.')return false;    if((s[0]=='#'||s[0]=='*')&&SZ(s)>1&&s[1]!='.')return false;    rep(i,0,SZ(s)){        int c=get(s[i]);        if((c==-1)||(i&&c>37))return false;        if(s[i]=='-'&&(!i||!islower(s[i-1])||i+1==SZ(s)||!islower(s[i+1])))return false;        if(s[i]=='.'&&i+1
        
         >n){        non.init();xin.init();jin.init();        int VPN=0;        rep(i,0,n){            string name,domain;            cin>>domain>>name;            if(ckName(name)&&ckDomain(domain)&&ckConflict(domain)){                ++VPN;                //cout<
         
          <<" "<
          
           <
           
            >q; rep(i,0,q){ string s; int x=0,ans=0; cin>>s; if(s[0]=='*'){ x=1; if(SZ(s)==1){ cout<
            
             <