【字符串hs+双模挂链+自然溢出】正确答案

题目描述
小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。 “吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。 外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。这可让小Y与小H犯了难。你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。无解输出-1。

输入格式
第一行四个整数n, m, p, q，意义如上描述。 接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。

输出格式
仅一行，一个长度为m的字符串或是-1。

样例一
input

2 2 2 0
YY
YY
output

YY
限制与约定
对于30%的数据,n≤100n≤100
对于60%的数据,n≤5000，m≤100n≤5000，m≤100
对于100%的数据,1≤n≤30000，1≤m≤500,0≤p,q且p+q≤n1≤n≤30000，1≤m≤500,0≤p,q且p+q≤n
时间限制：1s1s
空间限制：256MB

这道题是个毒瘤！！，我差不多卡了一天

首先挂一个双模挂链hs+自然溢出（其实单模也能过，但是联系下双模）

 1 struct edge{int nxt,to;}o[N];
 2 struct Double_Hashset
 3 {
 4     void clear(){memset(head,-1,sizeof(head));I = 1;}
 5     void insert(int from,int t)
 6     {
 7         o[I].to = t;
 8         o[I].nxt = head[from];
 9         head[from] = I++;
10     }
11     int find(int from,int t)
12     {
13         int num = 0;
14         for(int i = head[from];i!=-1;i = o[i].nxt)
15             if(o[i].to==t)num++;
16         return num;
17     }
18 }Map;

相当于手写了个map（其实并不是，map底层是红黑树，复杂得多QAQ）

然后考虑这道题

这道题的思路就是

先将名字按字典序排一遍，然后枚举每一个人，假如第一个人的答案就是正确答案，看全对的等不等于p，然后看第一个人的反有几个，就是看有几个人爆零了，看是不是q

如果是直接输出

然后数据很毒瘤

会有p==0的点，这时候没有人全对，那么我们就只能枚举每个人，然后假如这个人爆零了，然后看这个人的答案是不是出现q次，再看全对的是不是0个（我就是弄反了卡了好久）

然后更毒的是p==0，q==0的点，这就更恶心，我的方法是搜索，到每个地方都Y或者N往下搜，到最后一层就验证，注意先搜Y再搜N，否则会字典序不是最优而且Y和N都要算！！（这个地方我又卡了好久）

最后附一个字典序比较升级版

1 bool cmp(input a,input b) 2 {return strcmp(a.a+1,b.a+1)<0;}

这样就OK，之前我写麻烦了

注意取得模要开大一些

附代码

  1 #include<bits/stdc++.h>
  2 #define mod1 100003
  3 #define mod2 23333333333333333
  4 #define ull unsigned long long
  5 #define seed1 13131
  6 #define seed2 131
  7 #define N 30011
  8 using namespace std;
  9 int n,m,p,q;
 10 char sou[N];
 11 ull val1[N],val2[N],fan1[N],fan2[N];
 12 struct input{char a[511];}in[N];    
 13 int head[mod1+100],I;
 14 bool yeah=0;
 15 struct edge{int nxt,to;}o[N];
 16 struct Double_Hashset
 17 {
 18     void clear(){memset(head,-1,sizeof(head));I = 1;}
 19     void insert(int from,int t)
 20     {
 21         o[I].to = t;
 22         o[I].nxt = head[from];
 23         head[from] = I++;
 24     }
 25     int find(int from,int t)
 26     {
 27         int num = 0;
 28         for(int i = head[from];i!=-1;i = o[i].nxt)
 29             if(o[i].to==t)num++;
 30         return num;
 31     }
 32 }Map;
 33 bool cmp(input a,input b)
 34 {return strcmp(a.a+1,b.a+1)<0;}
 35 inline void init()
 36 {
 37     for(int i=1;i<=n;i++)
 38     {
 39         for(int j=1;j<=m;j++)
 40         {
 41             val1[i]=(val1[i]*seed1+in[i].a[j])%mod1;
 42             val2[i]=(val2[i]*seed2+in[i].a[j])%mod2;
 43             if(in[i].a[j]=='Y')
 44             {
 45                 fan1[i]=(fan1[i]*seed1+'N')%mod1;
 46                 fan2[i]=(fan2[i]*seed2+'N')%mod2;
 47             }else 
 48             {
 49                 fan1[i]=(fan1[i]*seed1+'Y')%mod1;
 50                 fan2[i]=(fan2[i]*seed2+'Y')%mod2;
 51             }
 52         }
 53         Map.insert(val1[i],val2[i]);
 54     }
 55 }
 56 void dfs(int dep)
 57 {
 58     sou[dep]='N';
 59     if(dep!=m)dfs(dep+1);
 60     if(dep==m)
 61     {
 62         ull m1=0,m2=0,f1=0,f2=0;
 63         for(int i=1;i<=m;i++)
 64         {
 65             m1=(m1*seed1+sou[i])%mod1;
 66             m2=(m2*seed2+sou[i])%mod2;
 67             if(sou[i]=='Y')
 68             {
 69                 f1=(f1*seed1+'N')%mod1;
 70                 f2=(f2*seed2+'N')%mod2;
 71             }else 
 72             {
 73                 f1=(f1*seed1+'Y')%mod1;
 74                 f2=(f2*seed2+'Y')%mod2;
 75             }
 76         }
 77         if(Map.find(m1,m2)==0 && Map.find(f1,f2)==0 && yeah==0)
 78             {printf("%s
",sou+1);yeah=1;return;}
 79     }
 80     sou[dep]='Y';
 81     if(dep!=m)dfs(dep+1);
 82     if(dep==m)
 83     {
 84         ull m1=0,m2=0,f1=0,f2=0;
 85         for(int i=1;i<=m;i++)
 86         {
 87             m1=(m1*seed1+sou[i])%mod1;
 88             m2=(m2*seed2+sou[i])%mod2;
 89             if(sou[i]=='Y')
 90             {
 91                 f1=(f1*seed1+'N')%mod1;
 92                 f2=(f2*seed2+'N')%mod2;
 93             }else 
 94             {
 95                 f1=(f1*seed1+'Y')%mod1;
 96                 f2=(f2*seed2+'Y')%mod2;
 97             }
 98         }
 99         if(Map.find(m1,m2)==0 && Map.find(f1,f2)==0 && yeah==0)
100             {printf("%s
",sou+1);yeah=1;return;}
101     }
102 }
103 int main()
104 {
105     Map.clear();
106     scanf("%d%d%d%d",&n,&m,&p,&q);
107     for(int i=1;i<=n;i++)
108         scanf("%s",in[i].a+1);
109     sort(in+1,in+n+1,cmp);
110 //(((((0*1313131+89)%100003)*1313131+89)%100003*1313131+89)%100003*1313131+78)%100003
111     init();
112     if(p==0 && q==0)
113     {
114         dfs(1);
115         if(yeah==1)return 0;
116     }else if(p==0 && q!=0)
117     {
118         for(int i=1;i<=n;i++)
119         {
120             if(Map.find(fan1[i],fan2[i])==0 && Map.find(val1[i],val2[i])==q)
121             {
122                 for(int g=1;g<=m;g++)
123                 {
124                     if(in[i].a[g]=='Y')printf("N");
125                     else printf("Y");
126                     
127                 }printf("
");return 0;
128             }
129         }
130     }else 
131     {
132         for(int i=1;i<=n;i++)
133         {
134             if(Map.find(val1[i],val2[i])==p && Map.find(fan1[i],fan2[i])==q)
135             {printf("%s
",in[i].a+1);return 0;}
136         }    
137     }
138     puts("-1");
139     return 0;
140 }