首页 > 代码库 > 2014 Super Training #6 F Search in the Wiki --集合取交+暴力

2014 Super Training #6 F Search in the Wiki --集合取交+暴力

2024-07-11 03:39:27   220人阅读

原题: ZOJ 3674 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3674

题意不难理解，很容易想到用暴力，但是无从下手，不知道怎么实现。后来看了网上的代码，直接用vector和map暴力，用到了set_intersection()函数，之前也听过这个函数，但是一直没写过，于是照着他的代码打了一遍，算是见识一下这个函数了。

代码看一下就能看懂了，关键看自己能不能写出来。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>#include <set>#include <cstdlib>using namespace std;#define N 10007char name[35],ss[210],tips[210];int check[110];int main(){    int n,m,i,j,a,b;    int cword,ctips,ind,ccheck;    while(scanf("%d",&n)!=EOF)    {        cword = ctips = 0;        map<string,int> word;        map<string,int> tip;        map<int,string> atip;        vector<int> G[110],K1,K2;        for(j=1;j<=n;j++)        {            scanf("%s",name);            if(!word[name])                word[name] = ++cword;  //hash            a = word[name];            getchar();            gets(ss);            ind = 0;            for(i=0;ss[i];i++)            {                if(ss[i] == ‘ ‘)                {                    tips[ind] = ‘\0‘;                    if(!tip[tips])                    {                        tip[tips] = ++ctips;                        atip[ctips] = tips;                    }                    b = tip[tips];                    G[a].push_back(b);                    ind = 0;                }                else                    tips[ind++] = ss[i];            }            tips[ind] = 0;            if(!tip[tips])            {                tip[tips] = ++ctips;                atip[ctips] = tips;            }            b = tip[tips];            G[a].push_back(b);            sort(G[a].begin(),G[a].end());        }        scanf("%d",&m);        getchar();        while(m--)        {            ccheck = 0;            gets(ss);            ind = 0;            for(i=0;ss[i];i++)            {                if(ss[i] == ‘ ‘)                {                    name[ind] = 0;                    check[ccheck++] = word[name];                    ind = 0;                }                else                    name[ind++] = ss[i];            }            name[ind] = 0;            check[ccheck++] = word[name];            K1.clear();            vector<int> ::iterator it;            for(it=G[check[0]].begin();it<G[check[0]].end();it++)                K1.push_back(*it);            for(i=1;i<ccheck;i++)            {                K2.clear();                set_intersection(K1.begin(),K1.end(),G[check[i]].begin(),G[check[i]].end(),back_inserter(K2));                i++;                if(i >= ccheck)  //last one                {                    K1.clear();                    for(it=K2.begin();it<K2.end();it++)                        K1.push_back(*it);                    break;                }                K1.clear();                set_intersection(K2.begin(),K2.end(),G[check[i]].begin(),G[check[i]].end(),back_inserter(K1));            }            //最终结果看K1            if(!K1.size())            {                puts("NO");                continue;            }            set<string> ans;            for(it=K1.begin();it<K1.end();it++)                ans.insert(atip[*it]);            set<string>::iterator st;            st = ans.begin();            cout<<*st;            for(st++;st!=ans.end();st++)                cout<<" "<<*st;            puts("");        }    }    return 0;}
View Code

 

 


联系
我们