正确答案

题目描述

小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

样例输出

提示

30% : n <= 100.

60% : n <= 5000 , m <= 100.

100% : 1 <= n <= 30000 , 1 <= m <= 500. 0 <= p , q 且 p + q <= n.

题解

这道题在我看来是需要特判的恶心细节题,据说是一道noip模拟赛的题目

看到这道题目最开始的思路,把所有的答案hash一下,并把它们取反(即Y变N,N变Y),在hash一下,然后把每个答案都当做满分答案来做,因为只有Y和N两种答案,知道满分答案就能知道0分答案,统计一下这两种答案的个数是否满足题目所给的p和q,这里我用的是multiset,可重集合,直接计算元素个数,时间复杂度\(O(logn+szie),size\)是所查找元素的个数.

但是这样直接交的话只有60+左右,因为我们并没有考虑满分答案等于0的情况,其实这也很简单,就把所有答案都当成0分答案来做,像上面一样,只是反了过来,加上这个特判80+左右

最后还需要特判一下p和q都等于0的情况,这时我们直接深搜即可,因为要求字典序最小,我们就先搜N再搜Y,遇到第一个可行解直接输出并退出程序

#include<bits/stdc++.h>

#define Min(a,b) (a)<(b)?(a):(b)

#define Max(a,b) (a)>(b)?(a):(b)

#define in(i) (i=read())

using namespace std;

int read() {

    int ans=0,f=1; char i=getchar();

    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}

    while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}

    return ans*f;

}

multiset<int>t;

int n,m,p,q;

int base=3,mod=1e9+7;

struct str {

    int v;

    char s[510];

}ans;

char s[30010][510],ac[30010];

int Hash[30010],Hash2[30010],len[30010];

void dfs(int len) {

    if(len==m) {

        int sum1=0,sum2=0;

        for(int i=1;i<=m;i++) {

            sum1=(sum1*base%mod+(ac[i]=='N'))%mod;

            sum2=(sum2%base%mod+(ac[i]=='Y'))%mod;

        }

        if(!t.count(sum1) && !t.count(sum2)) {

            for(int i=1;i<=m;i++) printf("%c",ac[i]);

            puts(""),exit(0);

        }

        return;

    }

    ac[len+1]='N'; dfs(len+1);

    ac[len+1]='Y'; dfs(len+1);

}

int main()

{

    ans.v=0; in(n); in(m); in(p); in(q);

    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);

    for(int i=1;i<=n;i++) {

        string po; len[i]=strlen(s[i]+1);

        for(int j=1;j<=len[i];j++) {

            Hash[i]=(Hash[i]*base%mod+(s[i][j]=='Y'))%mod;

            po+=(s[i][j]=='Y'?'N':'Y');

            Hash2[i]=(Hash2[i]*base%mod+(po[j-1]=='Y'))%mod;

        }

    }

    if(!p && !q) {

        for(int i=1;i<=n;i++) t.insert(Hash[i]),t.insert(Hash2[i]);

        dfs(0); cout<<-1<<endl;

        return 0;

    }

    else if(!p && q) {

        for(int i=1;i<=n;i++) t.insert(Hash2[i]);

        for(int i=1;i<=n;i++) {

            if(!t.count(Hash[i]) && t.count(Hash2[i])==q) {

                if(ans.v==0 || ans.v>Hash2[i]) {

                    for(int j=0;j<len[i];j++) ans.s[j]=(s[i][j+1]=='Y'?'N':'Y');

                    ans.v=Hash2[i];

                }

            }

        }

        if(ans.v!=0) cout<<ans.s<<endl;

        else cout<<-1<<endl;

        return 0;

    }

    else {

        for(int i=1;i<=n;i++) t.insert(Hash[i]);

        for(int i=1;i<=n;i++) {

            if(t.count(Hash2[i])==q && t.count(Hash[i])==p) {

                if(ans.v==0 || ans.v>Hash[i]) {

                    for(int j=0;j<len[i];j++) ans.s[j]=s[i][j+1];

                    ans.v=Hash[i];

                }

            }

        }

        if(ans.v!=0) cout<<ans.s<<endl;

        else cout<<-1<<endl;

        return 0;

    }

}

博主自认为代码算比较短的了,我看网上其他的题解一个个分分钟一两百行上下啊

巴特西

正确答案 [Hash/枚举]

正确答案

题目描述

输入

输出

样例输入

样例输出

提示

题解

博主蒟蒻,随意转载.但必须附上原文链接

http://www.cnblogs.com/real-l/

最新文章

热门文章