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.
考场：只考虑了p!=0的情况。忘记输出-1了。本来分就不高。
。结果只得了50分。再考虑上p！=0但q=0的情况，得到了80分。改了一下午，快恶心死我了。不管了，就95分吧。
p！=0的时候，找出所有相同的且总数为p的字符串，然后将它与其它不同的字符串比较，看看是否有q个完全不同的字符串。若有，就输出答案。
p==0，q！=0时，可以找出一组相同的且总数为q的字符串，输出答案即可。
p==0,q==0时，按字典序枚举全对的字符串，与全部的字符串比较，若字符串中有与它相同或完全不同的字符串。继续查询。知道找到解或枚举完所有情况。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define N 30010 #define M 510 #define ll long long using namespace std; int n,m,p,q,num(1),k(0); char ss[N][M]; int l[N],r[N]; struct node { char s[M]; }a[N]; bool cmp(node x,node y) { int j=0; while (j<m&&x.s[j]==y.s[j]) j++; if (x.s[j]<y.s[j]) return 1; else return 0; } bool pd1(int x) { for (int l=0;l<m;l++) if (a[x].s[l]!=a[x-1].s[l]) return 0; return 1; } bool pd2(int x,int y) { int sum(0); for (int l=0;l<m;l++) if (ss[x][l]==a[y].s[l]) return 0; return 1; } void solve(int ki) { for (int i=2;i<=n;i++) if (pd1(i)) num++; else { if (num==ki) { k++; r[k]=i-1; l[k]=i-p; for (int j=0;j<m;j++) ss[k][j]=a[i-1].s[j]; }; num=1; } if (num==ki) { k++; for (int j=0;j<m;j++) ss[k][j]=a[n].s[j]; }; if (ki==p)//p!=0 { for (int i=1;i<=k;i++) { int num2(0); for (int j=1;j<=n;j++) { if (j>=l[i]&&j<=r[i]) continue; if (pd2(i,j)) num2++; } if (num2==q) { printf("%s ",ss[i]); fclose(stdin); fclose(stdout); } } } else//p==0,q!=0 { if (k) { for (int i=0;i<m;i++) if (ss[1][i]=='Y') printf("N"); else printf("Y"); fclose(stdin); fclose(stdout); } } } void solve2()//p==0&&q==0 { bool ff=1; int K(-1),KI=0,Ki=0; while (ff&&Ki<n) { bool F(0); for (int i=0;i<m;i++) ss[1][i]='N'; if (K==KI) { Ki++; ss[1][m-Ki]='Y'; KI=(1+Ki)*Ki/2; } else { if (Ki!=0) ss[1][m-Ki]='Y'; for (int i=m-1;i>=m-Ki+KI-K;i--) ss[1][i]='Y'; } for (int i=1;i<=n;i++) { int sum1(0); for (int j=0;j<m;j++) if (a[i].s[j]!=ss[1][j]) sum1++; if (sum1==0||sum1==m) { F=1; break; } } K++; if (!F) ff=0; cout<<ss[1]<<endl; } if (!ff) { printf("%s ",ss[1]); fclose(stdin); fclose(stdout); } } int main() { freopen("answer.in","r",stdin); freopen("answer.out","w",stdout); scanf("%d%d%d%d",&n,&m,&p,&q); for (int i=1;i<=n;i++) scanf("%s",a[i].s); sort(a+1,a+n+1,cmp);//按字典序排序 if (p!=0) solve(p); else if (q!=0) solve(q); else solve2(); printf("-1 "); fclose(stdin); fclose(stdout); }
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; const int N = 3e4 + 2, M = 5e2 + 2, sed = 31, SED = 131, mod = 70177, MOD = 92311; int n, m, p, q, ans, hash[N], HASH[N]; int top, info[mod], nxt[N * 2], fet[N * 2], cnt[N * 2]; struct node { char s[M]; inline bool operator < (const node &b) const { return strcmp(s, b.s) < 0; } } 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] = 1; 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 0; } inline void Solve1() { int tmp, TMP; ans = -1; for (int i = 0; i < n; ++i) { tmp = TMP = 0; for (int j = 0; 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 = 0; i < n; ++i) if (Query(hash[i], HASH[i]) == p) { tmp = TMP = 0; for (int j = 0; 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 != -1) printf("%s ", a[ans].s); else puts("-1"); return ; } char cur[M]; inline void Solve2() { int tmp, TMP; ans = -1; for (int i = 0; i < n; ++i) { tmp = TMP = 0; for (int j = 0; 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 - 1; i >= 0; --i) if (Query(hash[i], HASH[i]) == q) { tmp = TMP = 0; for (int j = 0; 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 != -1) { for (int i = 0; i < m; ++i) cur[i] = a[ans].s[i] == 'N' ? 'Y' : 'N'; printf("%s ", cur); } else puts("-1"); return ; } void Solve3() { int tmp, TMP; for (int i = 0; i < n; ++i) { tmp = TMP = 0; for (int j = 0; 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 = 0; for (int j = 0; 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 = 0; i < m; ++i) cur[i] = 'N'; do { tmp = TMP = 0; for (int j = 0; j < m; ++j) { tmp = (tmp * sed + (cur[j] == 'N')) % mod; TMP = (TMP * SED + (cur[j] == 'N')) % MOD; } if (Query(tmp, TMP) == 0) { flag = true; break; } flag = false; for (int j = m - 1; j >= 0; --j) if (cur[j] == 'Y') cur[j] = 'N'; else { cur[j] = 'Y'; flag = true; break; } } while (flag); if (flag) printf("%s ", 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 = 0; 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 0; }