正确答案

Tire map

题面

外卡组试卷中共有$m$道判断题,小Y一共从其他$n$个神犇那问了答案。
这$n$个神犇中有$p$个考了满分,$q$个考了零分,其他神犇不为满分或零分。
这可让小Y犯了难。你能帮助他们还原出标准答案吗?如有多解则输出字典序最小的那个。无解输出$-1$。

• $n\leq30000,m\leq500$

解析

很显然，我们可以把这些神犇的答案变成一堆$01$字符串。
然后若要标准答案，对这些字符串进行排序，找出个数恰好为$p$的和反过来个数恰好为$q$的字符串即可。

如何排序？
$Tire$树（注意空间复杂度为$O(mn)$，要卡空间）和$map$都可以。
复杂度估计不超过$O(100n)$

如果$p=0,q=0$,直接暴搜即可，复杂度不超过$O(2n)$。
（然而我不判有没有当前字符串才能AC是什么情况）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int n,m,p,q,a[30005][505],tot,id[15000005][2],num[15000005],now[600],f;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
il void dfs(re int x,re int u,re int dep)
{
  if(dep==m) return;
  if(!a[x][dep+1])
    {
      if(!id[u][0]) id[u][0]=++tot,++num[tot];
      else ++num[id[u][0]];
      dfs(x,id[u][0],dep+1);
    }
  else
    {
      if(!id[u][1]) id[u][1]=++tot,++num[tot];
      else ++num[id[u][1]];
      dfs(x,id[u][1],dep+1);
    }
}
il int work(re int x,re int dep)
{
  if(dep==m) return num[x];
  re int way=now[dep]^1;
  if(id[x][way]) return work(id[x][way],dep+1);
  else return 0;
}
il void print()
{
  fp(i,0,m-1) putchar((now[i]^f)?'Y':'N');
  puts("");
  exit(0);
}
il void dfs1(re int x,re int dep)
{
  if(dep==m)
    { 
      if(num[x]!=p) return;
      if(work(0,0)==q) print();
      return;
    }
  if(id[x][0]) now[dep]=0,dfs1(id[x][0],dep+1);
  if(id[x][1]) now[dep]=1,dfs1(id[x][1],dep+1);
}
il void dfs2(re int x,re int dep)
{
  if(dep==m)
    {
      if(num[x]!=p) return;
      if(work(0,0)==q) print();
      return;
    }
  now[dep]=0,dfs2(id[x][0],dep+1);
  now[dep]=1,dfs2(id[x][1],dep+1);
}
int main()
{
  freopen("answer.in","r",stdin);
  freopen("answer.out","w",stdout);
  n=gi();m=gi();p=gi();q=gi();
  fp(i,1,n)
    fp(j,1,m)
    {
      re char ch=getchar();
      while(ch!='N'&&ch!='Y'){ch=getchar();}
      a[i][j]=(ch!='N');
    }
  fp(i,1,n) dfs(i,0,0);
  if(!p&&q) swap(p,q),f=1;
  if(p||q) dfs1(0,0);
  else dfs2(0,0);
  puts("-1");
  fclose(stdin);
  fclose(stdout);
  return 0;
}