即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

ZOJ 3960 What Kind of Friends Are You?(STL map,状态压缩)

编程语言 mr_zj_ 13℃ 0评论

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5592

题意:向c个朋友询问q个问题,现在给出对于每个问题每个朋友的回答(每个问题给出回答”yes”的朋友,其他即为回答”no”的朋友),然后给出一个n行q列的01矩阵,代表n个朋友的回答,要求判断这n个回答分别是谁答的,如果能唯一确定则输出他的名字,否则输出”Let’s go to the library!!”。

解题方案:如果直接暴力用map >,复杂度为O(100 * 100 * 200 * 21),会T。可以将01序列看成2进制数从而进行状态压缩,最多只有21位,不会爆int,即用map得到每个朋友的回答,然后在查找前先预处理一下,将前一个map的key和value互换,存到另一个map里,然后如果发现一个回答对应有多个朋友,则将其string赋值成空格。复杂度为O(
100 * 100 * ( 21 + log(200) ) )。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define FOR(i,k,n) for(int i=k;i mp1;
map mp2;

int main()
{
    //freopen("../in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t;
    scan(t);
    while(t--)
    {
        mp1.clear(); mp2.clear();//之前忘了初始化,WA了好久。。
        int n,q;
        scann(n,q);
        int c; scan(c);
        FOR(i,0,c)
        {
            string s;
            cin>>s;
            mp1[s]=0;
        }
        FOR(i,0,q)
        {
            int m; scan(m);
            for(map::iterator it=mp1.begin();it!=mp1.end();it++)
                it->second<<=1;
            FOR(i,0,m)
            {
                string s;
                cin>>s;
                mp1[s]+=1;
            }
        }

        for(map::iterator it=mp1.begin();it!=mp1.end();it++)
        {
            int state=it->second;
            string s=it->first;
            if(mp2.find(state)!=mp2.end()) mp2[state]=" ";
            else mp2[state]=s;
        }

        FOR(i,0,n)
        {
            int a=0;
            FOR(j,0,q)
            {
                int b; scan(b);
                a<<=1;
                a+=b;
            }
            if(mp2.find(a)!=mp2.end()&&mp2[a]!=" ") cout<





转载请注明:CodingBlog » ZOJ 3960 What Kind of Friends Are You?(STL map,状态压缩)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情