首页 > 代码库 > 浙江省赛C What Kind of Friends Are You?(MAP)
浙江省赛C What Kind of Friends Are You?(MAP)
题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3960
题意:对01矩阵中第i行j个数 1表示第j个问题中的名字和c个已知名字取交集
0表示已知名字去除第j个问题中的名字
问对于矩阵中i行 是否存在q个问题中的名字和c个已知名字的元素个数为1的交集
若有输出该名字 否则输出Let‘s go to the library!!
思路:将第i个问题中的Yes数值化为1<<i(压位 相当于转化为二进制数后左移i位) 这样可以保证c中名字有唯一对应值
要让名字和值对应需要用到 STL中的map<string,int>
代码:
#include<bits/stdc++.h> using namespace std; int main(){ string s,s0; int t,n,q,c,m,a; map<string,int> mp; map<string,int>::iterator it; cin>>t; while(t--){ mp.clear(); cin>>n>>q; cin>>c; for(int i=0;i<c;i++){ cin>>s0; mp[s0]=0;//需初始化 否则会WA } for(int i=0;i<q;i++){ cin>>m; for(int j=0;j<m;j++){ cin>>s; mp[s]+=1<<i; } } for(int i=0;i<n;i++){ int sum=0; for(int j=0;j<q;j++){ cin>>a; if(a==1) sum+=1<<j; } int cnt=0; string name; for(it=mp.begin();it!=mp.end();it++){//遍历图 是否存在唯一对应值 if(it->second==sum){ name=it->first; cnt++; } } if(cnt==1) cout<<name<<endl; else cout<<"Let‘s go to the library!!"<<endl; } } return 0; }
浙江省赛C What Kind of Friends Are You?(MAP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。