1.正确答案
【题目描述】
小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.
题解是这样说的：
30%: O(n ^ 2 * m)暴力判断。
100%: 很显然答案的可能性最多只有n种，所以我们将所有人的答案按字典序排序后枚举 将每个人的答案作为正确答案来进行判断。由于是判断题，若当前人的答案为正确答 案则零分者的答案也就确定了，那么只需统计出这两种答案的人数判断是否满足题意 即可。这一步使用字符串哈希即可解决。
代码如下 ：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std; const int N = 3e4 + , M = 5e2 + , sed = , SED = , mod = , MOD = ;
int n, m, p, q, ans, hash[N], HASH[N];
int top, info[mod], nxt[N * ], fet[N * ], cnt[N * ];
struct node {
char s[M];
inline bool operator < (const node &b) const {
return strcmp(s, b.s) < ;
}
} a[N]; inline void Insert(const int &x, const int &y) {
for (int k = info[x]; k; k = nxt[k])
if (fet[k] == y) {
++cnt[k]; return ;
}
nxt[++top] = info[x]; info[x] = top;
fet[top] = y; cnt[top] = ;
return ;
} inline int Query(const int &x, const int &y) {
for (int k = info[x]; k; k = nxt[k])
if (fet[k] == y) return cnt[k];
return ;
} inline void Solve1() {
int tmp, TMP; ans = -;
for (int i = ; i < n; ++i) {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
}
hash[i] = tmp, HASH[i] = TMP;
Insert(tmp, TMP);
}
for (int i = ; i < n; ++i)
if (Query(hash[i], HASH[i]) == p) {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
}
if (Query(tmp, TMP) == q) {
ans = i; break;
}
}
if (ans != -) printf("%s\n", a[ans].s);
else puts("-1");
return ;
} char cur[M];
inline void Solve2() {
int tmp, TMP; ans = -;
for (int i = ; i < n; ++i) {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
}
hash[i] = tmp, HASH[i] = TMP;
Insert(tmp, TMP);
}
for (int i = n - ; i >= ; --i)
if (Query(hash[i], HASH[i]) == q) {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
}
if (Query(tmp, TMP) == p) {
ans = i; break;
}
}
if (ans != -) {
for (int i = ; i < m; ++i)
cur[i] = a[ans].s[i] == 'N' ? 'Y' : 'N';
printf("%s\n", cur);
}
else puts("-1");
return ;
} void Solve3() {
int tmp, TMP;
for (int i = ; i < n; ++i) {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'N')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'N')) % MOD;
}
Insert(tmp, TMP);
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (a[i].s[j] == 'Y')) % mod;
TMP = (TMP * SED + (a[i].s[j] == 'Y')) % MOD;
}
Insert(tmp, TMP);
}
bool flag = true;
for (int i = ; i < m; ++i) cur[i] = 'N';
do {
tmp = TMP = ;
for (int j = ; j < m; ++j) {
tmp = (tmp * sed + (cur[j] == 'N')) % mod;
TMP = (TMP * SED + (cur[j] == 'N')) % MOD;
}
if (Query(tmp, TMP) == ) {
flag = true; break;
}
flag = false;
for (int j = m - ; j >= ; --j)
if (cur[j] == 'Y') cur[j] = 'N';
else {
cur[j] = 'Y'; flag = true; break;
}
} while (flag);
if (flag) printf("%s\n", cur);
else puts("-1");
return ;
} int main() {
freopen("answer.in", "r", stdin);
freopen("answer.out", "w", stdout);
scanf("%d%d%d%d", &n, &m, &p, &q);
for (int i = ; i < n; ++i) scanf("%s", a[i].s);
sort(a, a + n);
if (p) Solve1();
else if (q) Solve2();
else Solve3();
fclose(stdin); fclose(stdout);
return ;
}