【JZOJ3888】正确答案【模拟】【dfs】

题目：

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

---

思路：

当$p≠0$时，直接用$map$记录每一个字符串出现的次数$cnt1$，然后把每一个字符串取反也记录一下出现次数$cnt1$。然后排序比较即可。
如果$p=0,q=0$，那么直接爆搜出第一个没有出现且取反后伊朗没有出现的字符串即可，即第一个$cnt1[s]=0$且$cnt2[s]=0$的$s$。
如果$p=0,q≠0$，那么就枚举每一个$s$，如果$cnt2[s]=0$，那么就将$s$取反输出即可。

---

代码：

#include <map>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=30010;
int n,m,q,p;
string s[N],ss;
bool flag;
map<string,int> cnt1,cnt2;

void dfs(int x,string S)
{
	if (x>m)
	{
		if (cnt1[S]==p && cnt2[S]==q)
		{
			cout<<S;
			flag=1;
		}
		return;
	}
	dfs(x+1,S+'N');
	if (flag) return;
	dfs(x+1,S+'Y');
}

int main()
{
//	freopen("data.txt","r",stdin);
	scanf("%d%d%d%d
",&n,&m,&p,&q);
	for (int i=1;i<=n;i++)
	{
		cin>>s[i]; ss=s[i];
		cnt1[ss]++;
		for (int j=0;j<m;j++)
			ss[j]=(ss[j]=='Y'?'N':'Y');
		cnt2[ss]++;
	}
	sort(s+1,s+1+n);
	if (!p && !q)
	{
		dfs(1,"");
		if (!flag) printf("-1");
		return 0;
	}
	if (!p)
	{
		for (int i=1;i<=n;i++)
			if (cnt1[s[i]]==q)
			{
				for (int j=0;j<m;j++)
					putchar(s[i][j]=='Y'?'N':'Y');
				return 0;
			}
		printf("-1");
		return 0;
	}
	for (int i=1;i<=n;i++)
		if (cnt1[s[i]]==p && cnt2[s[i]]==q)
		{
			cout<<s[i];
			return 0;
		}
	printf("-1");
	return 0;
}