[关闭]
@IOU 2018-06-09T11:24:26.000000Z 字数 4515 阅读 1044

正确答案

哈希 MAP trie树 考试

题目

网盘里有。

正确答案

【题目描述】
小 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。
【样例输入】
2 2 2 0
YY
YY
【样例输出】
YY
【数据范围】
30% : n <= 100.
60% : n <= 5000 , m <= 100.
100% : 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n.

思路

map

map和unordered_map的区别
map是个好东西。看个例子就很容易懂了。

  1. map<string,int> h;
  2. char str[25],tar[25];
  3. for(int i=1;i<=n;i++)scanf("%s",str),h[str]++;
  4. cin>>tar;
  5. cout<<h[tar];

这段程序就是求tar这个字符串在之前输入的字符串中的出现次数。其实和字符串hash差不多。
这道题其实分三种情况讨论：
1.p!=0&&q!=0,就是让你选一种出现次数为p次，把它取反的字串出现q次，其实就和上面这个例子差不多，改一下就好。
2.p=0&&q!=0,一样的道理，找一个字串出现q次，把它取反的字串没有出现过，那把它取反的序列就是答案。
3.p=0&&q=0，那就从字典序最小的开始枚举，枚举2n+1次，一定可以得到一个不管是自己还是它的反序列都没有出现过的序列，最先找到的就是答案。
还有要注意，枚举序列的时候要先排序，这样确保找到的第一个字典序最小，可以直接break掉。
那么放在这道题复杂度应该是也就是30000×500×15=225 000 000好像是超过了的。。但是可以水过去的。。

字符串哈希

判断方法改一下，预处理复杂度,询问的时候是的，因为要枚举n此，查询是的。但是排序的时候还是要，所以总的复杂度和map是一样的。

代码

map

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<map>
  6. #include<string>
  7. using namespace std;
  8. string s[30005],ss,sss;
  9. int main()
  10. {
  11.     //freopen("answer.in","r",stdin);
  12.     //freopen("answer.out","w",stdout);
  13.     int n,mm,p,q;cin>>n>>mm>>p>>q;
  14.     map<string,int> m;
  15.     for(int i=1;i<=n;i++)cin>>s[i],m[s[i]]++;
  16.     sort(s+1,s+n+1);
  17.     if(p!=0)
  18.     {
  19.         for(int i=1;i<=n;i++)
  20.         {
  21.             ss.clear();
  22.             for(int j=0;j<mm;j++)ss.push_back((s[i][j]!='Y')?'Y':'N');
  23.             if(p==m[s[i]]&&q==m[ss]){cout<<s[i];return 0;}
  24.         }
  25.     }
  26.     else if(q!=0)
  27.     {
  28.         for(int i=1;i<=n;i++)
  29.         {
  30.             ss.clear();
  31.             for(int j=0;j<mm;j++)ss.push_back((s[i][j]!='Y')?'Y':'N');
  32.             if(q==m[s[i]]&&p==m[ss]){cout<<ss;return 0;}
  33.         }
  34.     }
  35.     else
  36.     {
  37.         for(int i=0;i<=2*n;i++)
  38.         {
  39.             ss.clear();
  40.             for(int j=0;j<mm;j++)ss.push_back('N');
  41.             int t=i,k=-1;
  42.             while(t){k++;if(t%2)ss[mm-k]='Y';t/=2;}
  43.             sss=ss;
  44.             for(int j=0;j<mm;j++)sss[j]=(ss[j]!='Y')?'Y':'N';
  45.             if(m[ss]==0&&m[sss]==0){cout<<ss;return 0;}
  46.         }
  47.     }
  48.     cout<<-1;
  49.     return 0;
  50. }

字符串哈希

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<map>
  6. #include<string>
  7. #define mod 12345678
  8. using namespace std;
  9. string ss,sss;
  10. int hash[12345679],num[30005];
  11. int n,mm,p,q;
  12. struct node
  13. {
  14.     int id,h1,h2;
  15.     char s[505];
  16.     bool operator <(node x)const
  17.         {
  18.             return strcmp(s,x.s)<0;
  19.         }
  20.     void h()
  21.         {
  22.             int base=1,sum=0;
  23.             for(int j=0;j<mm;j++)
  24.             {
  25.                 int w=(s[j]=='Y')?1:0;
  26.                 sum+=base*w;sum%=mod;
  27.                 base*=2;base%=mod;
  28.             }
  29.             h1=sum;base=1,sum=0;
  30.             for(int j=0;j<mm;j++)
  31.             {
  32.                 int w=(s[j]!='Y')?1:0;
  33.                 sum+=base*w;sum%=mod;
  34.                 base*=2;base%=mod;
  35.             }
  36.             h2=sum;
  37.         }
  38. }f[30005];
  39. int main()
  40. {
  41.     //freopen("answer.in","r",stdin);
  42.     //freopen("answer.out","w",stdout);
  43.     cin>>n>>mm>>p>>q;
  44.     for(int i=1;i<=n;i++)
  45.     {
  46.         scanf("%s",f[i].s);
  47.         f[i].h();hash[f[i].h1]++;
  48.     }
  49.     sort(f+1,f+n+1);
  50.     if(p!=0)
  51.     {
  52.         for(int i=1;i<=n;i++)
  53.             if(p==hash[f[i].h1]&&q==hash[f[i].h2]){cout<<f[i].s;return 0;}
  54.     }
  55.     else if(q!=0)
  56.     {
  57.         for(int i=1;i<=n;i++)
  58.         {
  59.             if(q==hash[f[i].h1]&&p==hash[f[i].h2])
  60.             {for(int j=0;j<mm;j++)printf("%c",((f[i].s[j]=='Y')?'N':'Y'));return 0;}
  61.         }
  62.     }
  63.     else
  64.     {
  65.         for(int i=0;i<=2*n;i++)
  66.         {
  67.             node x;memset(x.s,0,sizeof(x.s));
  68.             for(int j=0;j<mm;j++)x.s[j]='N';int t=i,k=-1;
  69.             while(t){k++;if(t%2)x.s[mm-k]='Y';t/=2;}
  70.             x.h();//cout<<hash[x.h1]<<" "<<hash[x.h2]<<endl;
  71.             if(hash[x.h1]==0&&hash[x.h2]==0){cout<<x.s;return 0;}
  72.         }
  73.     }
  74.     cout<<-1;
  75.     return 0;
  76. }

trie树

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<map>
  6. #include<string>
  7. #define maxn 15000005
  8. using namespace std;
  9. int n,mm,p,q,ch[maxn][2],rt,end[maxn],cnt=1;
  10. char f[30005][505],rec[505];
  11. void insert(char *s)
  12. {
  13.     int now=1;
  14.     for(int i=0;i<mm;i++)
  15.     {
  16.         int k=s[i]=='Y';
  17.         if(!ch[now][k])ch[now][k]=++cnt;
  18.         now=ch[now][k];end[now]++;
  19.     }
  20. }
  21. int query(char *s)
  22. {
  23.     int now=1;
  24.     for(int i=0;i<mm;i++)
  25.     {
  26.         int k=s[i]=='Y';
  27.         if(!ch[now][k])return 0;
  28.         now=ch[now][k];
  29.     }
  30.     return end[now];
  31. }
  32. int query2(char *s)
  33. {
  34.     int now=1;
  35.     for(int i=0;i<mm;i++)
  36.     {
  37.         int k=s[i]!='Y';
  38.         if(!ch[now][k])return 0;
  39.         now=ch[now][k];
  40.     }
  41.     return end[now];
  42. }
  43. void dfs(int x1,int x2,int k)
  44. {
  45.     if(k==mm)
  46.     {
  47.         if(p==end[x1]&&q==end[x2]){cout<<rec;exit(0);}
  48.         return;
  49.     }
  50.     if(ch[x1][0])rec[k]='N',dfs(ch[x1][0],ch[x2][1],k+1);
  51.     if(ch[x1][1])rec[k]='Y',dfs(ch[x1][1],ch[x2][0],k+1);
  52. }
  53. void dfs2(int x1,int x2,int k)
  54. {
  55.     if(k==mm)
  56.     {
  57.         if(q==end[x1]&&p==end[x2])
  58.         {for(int j=0;j<mm;j++)printf("%c",((rec[j]=='Y')?'N':'Y'));exit(0);}
  59.         return;
  60.     }
  61.     if(ch[x1][1])rec[k]='Y',dfs2(ch[x1][1],ch[x2][0],k+1);
  62.     if(ch[x1][0])rec[k]='N',dfs2(ch[x1][0],ch[x2][1],k+1);
  63. }
  64. int main()
  65. {
  66.     //freopen("answer.in","r",stdin);
  67.     //freopen("answer.out","w",stdout);
  68.     cin>>n>>mm>>p>>q;
  69.     for(int i=1;i<=n;i++)
  70.     {
  71.         scanf("%s",f[i]);
  72.         insert(f[i]);
  73.     }
  74.     if(p!=0)
  75.         dfs(1,1,0);
  76.     else if(q!=0)
  77.         dfs2(1,1,0);
  78.     else
  79.     {
  80.         for(int i=0;i<=2*n;i++)
  81.         {
  82.             char s[505];
  83.             memset(s,0,sizeof(s));
  84.             for(int j=0;j<mm;j++)s[j]='N';int t=i,k=0;
  85.             while(t){k++;if(t%2)s[mm-k]='Y';t/=2;}
  86.             //cout<<i<<" "<<s<<" "<<query(s)<<" "<<query2(s)<<endl;
  87.             if(query(s)==0&&query2(s)==0){cout<<s;return 0;}
  88.         }
  89.     }
  90.     cout<<-1;
  91.     return 0;
  92. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注