题目链接：点击打开链接
题目大意：根据人的回答问题的答案完全匹配上，当且仅当只有一位匹配上，则该朋友已鉴定（已找到），否则没有匹配上或者多个匹配上都算无法鉴定（未找到）。如图。
解题思路：首先利用 map、结构体 来数据初始化，通过 B2D （否则数据溢出）来映射，并且统计数组 rrr[maxn] + sort结构体 + lower_bound二分查找。
AC 代码
#include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; struct Peo { char name[50]; int vrr[50],idx,val; }; int n,q; //vector<string> vec; map<string,int> mp; int rrr[5000000]; void init() { mp.clear(); mem(rrr,0); // vec.clear(); } int cmp(Peo p1,Peo p2) { return p1.val<p2.val; } int lbcmp(Peo p1,Peo p2) { return p1.val<p2.val; } int main() { int T; scanf("%d",&T); while(T-- && ~scanf("%d%d",&n,&q)) { init(); int c; scanf("%d",&c); Peo ps[c+10]; int nameCnt=c; char name[50]; for(int i=0;i<c;i++) // 初始化 { scanf("%s",name); // memset(mp[name].vrr,0,sizeof mp[name].vrr); mem(ps[i].vrr,0); ps[i].idx=i; ps[i].val=0; strcpy(ps[i].name,name); // vec.push_back(name); mp[name]=i; } for(int i=0;i<q;i++) { scanf("%d",&c); for(int j=0;j<c;j++) { scanf("%s",name); // mp[name].vrr[i]=1; ps[mp[name]].vrr[i]=1; // 没有赋值为 1 的，则是 0 } } for(int i=0;i<nameCnt;i++) { int sum=0,two=1; for(int j=q-1;j>=0;j--) // B2D sum+=two*ps[i].vrr[j],two<<=1; rrr[sum]++; // 为了匹配时统计当且仅当存在一位朋友 ps[i].val=sum; // 为了sort排序，二分查找 } // for(int i=0;i<nameCnt;i++) // { // printf("%s == %d\n",ps[i].name,ps[i].val); // } int trr[q]; for(int i=0;i<n;i++) { for(int j=0;j<q;j++) { scanf("%d",&trr[j]); } int sum=0,two=1; for(int j=q-1;j>=0;j--) // B2D { sum+=two*trr[j],two<<=1; } Peo psum; // 为了与 lbcmp函数 语法对齐 psum.val=sum; sort(ps,ps+nameCnt,cmp); // 根据 val 从小到大排序 if(rrr[sum]==1) // 排除了找不到或者找到多个的情况 { printf("%s\n",ps[lower_bound(ps,ps+nameCnt,psum,lbcmp)-ps].name); } else { puts("Let's go to the library!!"); } } // TLE 常规思路 // int trr[q]; // for(int i=0;i<n;i++) // { // for(int j=0;j<q;j++) // scanf("%d",&trr[j]); // // int tmp[q],cnt=0,ans=-1; // for(int j=0;j<nameCnt;j++) // { // // for(int k=0;k<q;k++) // { // tmp[k]=mp[vec[j]].vrr[k]; // } // // int flag=1; // for(int k=0;k<q;k++) // { // if(tmp[k]!=trr[k]) // { // flag=0; // break; // } // } // // if(flag) // { // cnt++; // ans=j; // } // } // // if(cnt==0 || cnt>1) // puts("Let's go to the library!!"); // else if(cnt==1) // printf("%s\n",vec[ans].c_str()); // } } return 0; }
