题目链接：点击打开链接
题目大意：略。
解题思路：
- 原本是 map 改成 unordered_map 还是 TLE 了。
- 用 hash + sort 思想，AC。
TLE 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct cmp { bool operator()(int a,int b) { return a>b; } }; priority_queue<int,vector<int>,cmp> pq,tpq; unordered_map<string,priority_queue<int,vector<int>,cmp>> mp; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { mp.clear(); int id,k; char name[7]; for(int i=0;i<m;i++) { scanf("%d%d",&id,&k); for(int j=0;j<k;j++) { scanf("%s",name); mp[name].push(id); } } for(int i=0;i<n;i++) { scanf("%s",name); tpq=mp[name]; printf("%s",name); printf(" %d",tpq.size()); while(!tpq.empty()) { printf(" %d",tpq.top()); tpq.pop(); } puts(""); } } return 0; }
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MAX 26*26*26*10 using namespace std; typedef long long ll; vector<int> v[MAX]; int fhash(char s[]) { return (s[0]-'A')*26*26*10 + (s[1]-'A')*26*10 + (s[2]-'A')*10 + (s[3]-'0'); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int id,k; char name[7]; for(int i=0;i<m;i++) { scanf("%d%d",&id,&k); for(int j=0;j<k;j++) { scanf("%s",name); v[fhash(name)].push_back(id); } } for(int i=0;i<n;i++) { scanf("%s",name); printf("%s",name); id=fhash(name); int len=v[id].size(); printf(" %d",len); sort(v[id].begin(),v[id].end()); for(int i=0;i<len;i++) { printf(" %d",v[id][i]); } puts(""); } } return 0; }
