pat 1039

一点教训

  • 使用map、string会导致超时,因此上述程序有case通不过
  • 由于数据量庞大,因此不能使用cin、cout
  • 如果使用二维数组存放学生所选课程的编号,会导致最后一组数据内存超限,因此要使用vector

这种题一旦超时立刻要想到字符串hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/*#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
#define MAX 50000
using namespace std;
int n , k;
map<string , int> stringToInt;
map<int , string> intToString;
map<int , vector<int> > C;
int numCount = 0;
int change(string x)
{
if(stringToInt.find(x) != stringToInt.end())
{
return stringToInt[x];
}
else
{
stringToInt[x] = numCount;
intToString[numCount] = x;
return numCount++;
}
}
void findCourse(string name)
{
int nameID = change(name);
set<int> stuInfo;
int i;
for(map<int,vector<int> >::iterator it = C.begin() ; it != C.end() ; ++it)
{
if(find(C[it->first].begin() , C[it->first].end() , nameID) != C[it->first].end())
{
stuInfo.insert(it->first);
}
//lower_bound(C[it->first].begin() , C[it->first].end() , nameID);
}
cout<<name<<" "<<stuInfo.size();
// sort(stuInfo.begin() , stuInfo.end());
for(set<int>::iterator iter = stuInfo.begin() ; iter != stuInfo.end() ; ++iter)
{
cout<<" "<<*iter;
}
cout<<endl;
}
int main()
{
cin>>n>>k;
int i , j;
for(i = 0 ; i < k ; ++i)
{
int id , numPerson;
string course;
cin>>id>>numPerson;
for(j = 0 ; j < numPerson ; ++j)
{
int courseID;
cin>>course;
courseID = change(course);
C[id].push_back(courseID);
}
}
string query;
for(i = 0 ; i < n ; ++i)
{
cin>>query;
findCourse(query);
}
return 0;
}
*/
//使用map、string会导致超时,因此上述程序有case通不过
//由于数据量庞大,因此不能使用cin、cout
//如果使用二维数组存放学生所选课程的编号,会导致最后一组数据内存超限,因此要使用vector
//以下是最简洁最省空间的代码
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 40010;
const int M = 26 * 26 * 26 * 10 +1; //由姓名哈希成的数字上界(why?因为题目规定字母组成是三个大写字母+一个数字喽)<hash字符串>
vector<int> selectCourse[M];
int getID(char name[]) //hash函数,将字符串name转化成数字
{
int id = 0;
for(int i = 0 ; i < 3 ; ++i)
{
id = id * 26 + (name[i] - 'A');
}
id = id * 10 + (name[3] - '0');
return id;
}
int main()
{
char name[5];
int n , k;
scanf("%d%d" , &n , &k);
int i , j;
for(i = 0 ; i < k ; ++i)
{
int course , x;
scanf("%d%d" , &course , &x);
for(j =0 ; j < x ; ++j)
{
scanf("%s" , name);
int id = getID(name);
selectCourse[id].push_back(course); //直接存储目标,唉,把握题意不准
}
}
for(i = 0 ; i < n ; ++i)
{
scanf("%s" , name);
int id = getID(name);
sort(selectCourse[id].begin() , selectCourse[id].end());
printf("%s %d" , name , selectCourse[id].size());
for(j = 0 ; j < selectCourse[id].size() ; ++j)
{
printf(" %d" , selectCourse[id][j]);
}
printf("\n");
}
return 0;
}

热评文章