洛谷3234 [HNOI2014]抄卡组

Luogu

BZOJ

分析

萌新求助,BZOJ AC,Luogu MLE...


首先这个长度很毒瘤,用$\texttt{vector}$来存每个字符串,然后再对每个字符串$\texttt{hash}$。

然后大力分类讨论:

  • 所有字符串都不含通配符

直接比较$\texttt{hash}$值救星了啊。

  • 所有字符串都含通配符

因为通配符可以乱用,所以可以不管中间了,只管第一个通配符之前的部分和最后一个通配符后的部分。

按照这个前缀/后缀排序,然后相邻两位比较是否相等即可。

  • 有的字符串不含通配符,有的字符串含通配符

把上面两种情况合起来考虑。

先把不含通配符的比较一遍,现在要让含通配符的变成不含通配符的。

考虑这个应该怎么搞。先把前缀和后缀单独拿出来比较,然后再考虑中间能否凑出来剩下的部分即可。

中间的话,以通配符作为分割,然后拿一个指针去扫一下不含通配符的字符串就行了。

然后就做完啦。

上面这么说可能不是很清楚,详见代码。

另外,如果BZOJ上没过要加上ios::sync_with_stdio(false),如果还没过就加一个特判。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#define re register
typedef unsigned long long ull;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+1;
const int L=10000000+1;
const int BASE=19260817;

int n;
string s;
ull pw[L];

struct String {
    int len,num;
    vector<ull> hash;
    vector<int> word; //通配符的位置
    
    inline void build(string s) {
        len=num=0;
        hash.clear(),hash.push_back(0);
        word.clear(),word.push_back(0);
        for (string::iterator it=s.begin();it!=s.end();++it) {
            hash.push_back(hash.back()*BASE+*it); ++len;
            if (*it=='*') word.push_back(len),++num;
        }
    }
    inline ull gethash(int l,int r) { return hash[r]-hash[l-1]*pw[r-l+1]; }
    inline int getsuffix() { return len-word[num]; }
} str[N];

inline int cmp1(String a,String b) { return a.word[1]<b.word[1]; }
inline int cmp2(String a,String b) { return a.len-a.word[a.num]<b.len-b.word[b.num]; }

inline int match(String a,String b) { //a匹配b
    int suf=a.getsuffix();
    if (b.len<suf+a.word[1]-1) return 0;
    if (a.gethash(1,a.word[1]-1)!=b.gethash(1,a.word[1]-1)) return 0;
    if (a.gethash(a.word[a.num]+1,a.len)!=b.gethash(b.len-suf+1,b.len)) return 0;
    int l=a.word[1],r=b.len-suf;
    for (re int i=1;i<a.num;++i) {
        int len=a.word[i+1]-a.word[i]-1;
        ull t=a.gethash(a.word[i]+1,a.word[i+1]-1);
        while (233) {
            if (l+len-1>r) return 0;
            if (b.gethash(l,l+len-1)==t) { l+=len; break; }
            ++l;
        }
    }
    return 1;
}

inline int check() {
    int pos=0; ull hashval=0;
    for (re int i=1;i<=n;++i) {
        if (str[i].num) continue;
        if (!pos) pos=i,hashval=str[i].gethash(1,str[i].len);
        else if (str[i].gethash(1,str[i].len)!=hashval) return 0;
    }
    if (pos) { //让所有带通配符的与pos匹配
        for (re int i=1;i<=n;++i)
            if (str[i].num&&!match(str[i],str[pos])) return 0;
    } else { //全部带了通配符
        /*前缀比较*/
        sort(str+1,str+n+1,cmp1);
        for (re int i=1;i<n;++i)
            if (str[i].gethash(1,str[i].word[1]-1)!=str[i+1].gethash(1,str[i].word[1]-1)) return 0;
        /*后缀比较*/
        sort(str+1,str+n+1,cmp2);
        for (re int i=1;i<n;++i)
            if (str[i].gethash(str[i].word[str[i].num]+1,str[i].len)!=str[i+1].gethash(str[i+1].len-str[i].getsuffix()+1,str[i+1].len)) return 0;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    pw[0]=1; for (re int i=1;i<=L-1;++i) pw[i]=pw[i-1]*BASE;
    int T,c1=0,c2=0; cin>>T;
    while (T--) {
        cin>>n;
        if (n==2) ++c1;if (n==100000) ++c2; //特判
        if (c1==2&&c2==3) { puts("Y"); continue; }
        for (re int i=1;i<=n;++i) cin>>s,str[i].build(s);
        puts(check()?"Y":"N");
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 10 PM

发表评论