描述
题解
这个题的难点是翻译,翻译好了,一遍 AC。
首先输入 T,表示数据组数。
接着输入 n 和 q 表示 n 次询问与 q 次关系。
然后一个 c 表示可能出现的名字,接着就是 c 个名字。
然后是 q 次关系,每次开头一个 m 表示关系人数,接着 m 个人组成的关系网。
最后是 n 次询问,每次询问给出 q 个 0 或 1,表示某人是否出现在第 q 次关系网中。
问,针对每次询问,能否找到唯一匹配的人,如果能就输出人名,不能就输出Let's go to the library!!
。
题意就是酱紫,没毛病,map 打标签,Hash 搞搞匹配,然后就 AC 了!!!对了,这里的 Hash 实际上就是将 01 串看成二进制,转化为十进制就行了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int MAXN = 110;
const int MAXQ = 25;
const int MAXC = 210;
int stateNQ[MAXN][MAXQ];
int stateCQ[MAXC][MAXQ];
int stateCQHash[MAXC];
int pow[MAXQ] = {
1, 2};
int n, q, c;
string name;
string name_[MAXC];
map<string, int> msi;
void init()
{
memset(stateNQ, 0, sizeof(stateNQ));
memset(stateCQ, 0, sizeof(stateCQ));
memset(stateCQHash, 0, sizeof(stateCQHash));
msi.clear();
}
int Hash(int *state)
{
int res = 0;
for (int j = 0; j < q; j++)
{
res += state[j] * pow[j];
}
return res;
}
int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);
for (int i = 2; i < MAXQ; i++)
{
pow[i] = pow[i - 1] * 2;
}
int T;
cin >> T;
while (T--)
{
init();
cin >> n >> q >> c;
for (int i = 0; i < c; i++)
{
cin >> name;
msi[name] = i;
name_[i] = name;
}
int m;
for (int i = 0; i < q; i++)
{
cin >> m;
for (int j = 0; j < m; j++)
{
cin >> name;
stateCQ[msi[name]][i] = 1;
}
}
for (int i = 0; i < c; i++)
{
stateCQHash[i] = Hash(stateCQ[i]);
}
int flag, cnt;
for (int i = 0; i < n; i++)
{
flag = -1;
cnt = 0;
for (int j = 0; j < q; j++)
{
scanf("%d", &stateNQ[i][j]);
}
int res = Hash(stateNQ[i]);
for (int j = 0; j < c; j++)
{
if (res == stateCQHash[j])
{
if (flag == -1)
{
flag = j;
}
cnt++;
}
}
if (cnt != 1)
{
cout << "Let's go to the library!!\n";
}
else
{
cout << name_[flag] << '\n';
}
}
}
return 0;
}