首页 > 代码库 > 2017-7-14测试

2017-7-14测试

问题 A: 正确答案

时间限制: 2 Sec  内存限制: 256 MB
提交: 665  解决: 76
[提交][状态][讨论版]

题目描述

小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 0YYYY

样例输出

YY

提示

"Times New Roman";mso-hansi-font-family:"Times New Roman"">【数据范围】

 

30% : n <= 100.

 

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

 

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

此题思路很容易,但是c++我纠结于如何读入一个string类的字符串,pascal又不会手写map。最后发现其实c++可以直接用map标记string

技术分享
#include<cstdio>#include<iostream>#include<cstdlib>#include<map>#include<cstring>#include<string>#include<queue>#include<algorithm>using namespace std;map<string,int>Z,F;map<string,int>::iterator it;int n,m,p,q,num;    char ST[510],IST[510],ans[510];bool pl(){    int point=m-1;    while (ST[point]==Y) {        if (point==0) return false;        ST[point]=N,point--;    }    ST[point]=Y;    return true;}int main(){    scanf("%d%d%d%d",&n,&m,&p,&q);    for(int i=1;i<=n;i++){        scanf("%s",ST);        for(int j=0;j<m;j++)            ST[j]==Y?IST[j]=N:IST[j]=Y;        Z[ST]++;        //cout<<IST<<endl;        F[IST]++;    }    it=Z.begin();    string st;    string data;    bool firstans=true;    if ((p==0)&&(q==0)){        for(int j=0;j<m;j++)ST[j]=N;        do{            //cout<<ST;            if ((Z[ST]==0)&&(F[ST]==0)){                cout<<ST;                return 0;            }        }while(pl());        cout<<-1;        return 0;    }    while(it!=Z.end()){        num=it->second;        //printf("%d\n",num);        if (num!=p) {            it++;            continue;        }        st=it->first;        //cout<<st<<en6dl;        num=F[st];        if (num!=q) {            it++;            continue;        }        if ((firstans)||(st<data))            firstans=false,data=http://www.mamicode.com/st;        it++;    }    /*    it=F.begin();    while(it!=F.end()){        num=it->second;        if (num!=q) {            it++;            continue;        }        st=it->first;        //cout<<st<<endl;        num=Z[st];        if (num!=p) {            it++;            continue;        }        if ((firstans)||(st<data))            firstans=false,data=http://www.mamicode.com/st;>*/    if (firstans) cout<<-1; else cout<<data;}
View Code

序列问题

时间限制: 1 Sec  内存限制: 256 MB
提交: 340  解决: 29
[提交][状态][讨论版]

题目描述

小H是个善于思考的学生,她正在思考一个有关序列的问题。

她的面前浮现出了一个长度为n的序列{ai},她想找出两个非空的集合S、T。

这两个集合要满足以下的条件:

1. 两个集合中的元素都为整数,且都在 [1, n] 里,即Si,Ti ∈ [1, n]。

2. 对于集合S中任意一个元素x,集合T中任意一个元素y,满足x < y。

3. 对于大小分别为p, q的集合S与T,满足

            a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].

小H想知道一共有多少对这样的集合(S,T),你能帮助她吗?

输入

第一行,一个整数n

       第二行,n个整数,代表ai。

输出

仅一行,表示最后的答案。

样例输入

4 1 2 3 3

样例输出

4

提示

【样例解释】

S = {1,2}, T = {3}, 1 ^ 2 = 3 = 3 (^为异或)

S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3

S = {1,2}, T = {3,4} 1 ^ 2 = 3 & 3 = 3 (&为与运算)

S = {3}, T = {4} 3 = 3 = 3


【数据范围】


    30%: 1 <= n <= 10


    60%: 1 <= n <= 100


    100%: 1 <= n <= 1000, 0 <= ai < 1024

一开始以为爆搜能拿30分——开心,后来爆弹(气死了),后来发现hzw的搜索代码也是0分——开心。

其实这道题的DP很好想。

F[i][j]表示前i个数(第i个数一定要取)亦或值为j的方案数。

但这样转移的时候要同时枚举j,k。时间复杂度n^2*1024;

其实我们可以加个辅助数组,f[i][j]表示前i个数(第i个数不一定要取的方案数)这样就可以直接转移啦。(其实求答案时的时间复杂度还是n^2*1024);

最后这道题要开高精度+压位

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define maxn 1110#define ll long long using namespace std;ll f[maxn][maxn],F[maxn][maxn],g[maxn][maxn],G[maxn][maxn],n,a[maxn],ans;int main(){    scanf("%lld",&n);    for(ll i=1;i<=n;i++)    scanf("%lld",&a[i]);    //f[i] means the number of ways to choose  when i needn‘t to be choosen but F[i] means i must to be choosen    //g is same as f    for(ll i=1;i<=n;i++)    {        f[i][a[i]]++;        F[i][a[i]]++;        for(ll k=0;k<1024;k++)            f[i][k]+=f[i-1][k];        for(ll k=0;k<1024;k++)            f[i][a[i]^k]+=f[i-1][k],F[i][a[i]^k]+=f[i-1][k];    }    for(ll i=n;i>=1;i--)    {        g[i][a[i]]++;        G[i][a[i]]++;        for(ll k=0;k<1024;k++)            g[i][k]+=g[i+1][k];        for(ll k=0;k<1024;k++)             g[i][a[i]&k]+=g[i+1][k],G[i][a[i]&k]+=g[i+1][k];        }    for(ll i=1;i<=n;i++)        for(ll k=i+1;k<=n;k++)        //if(a[i]<a[k])        {            for(ll j=0;j<1024;j++)            ans+=F[i][j]*G[k][j];        }    printf("%lld\n",ans);        }

 

 

2017-7-14测试