tries树和stl中常用的数据结构

刘汝佳的算法书中,有一些关于模拟的题目
比较典型,代码量也比较大
同时叶比较考验代码的组织能力
具体题目请参阅《算法竞赛入门经典(第二版)》 第五章
这里对一些复杂的习题予以解答

小型订单系统的设计

Exchange

设计思路:

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
//
// main.cpp
// UVA1598
//
// Created by zhangmin chen on 2019/5/4.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;


class Order {
public:
string cmd;
int price, size;

Order(string str, int p, int s) : cmd(str), price(p), size(s) {}
};

map<int, set<int> > buypq, sellpq;
map<int, int> buytab, selltab;
vector<Order> books;

void init() {
//
books.clear();
buypq.clear();
sellpq.clear();

buytab.clear();
selltab.clear();
}

void trade(int flag) {
//
// flag 0 for buy, flag 1 for sell
// buy -> match books[sell]
// sell -> match books[buy]
while (!buypq.empty() && !sellpq.empty()) {
int bidP = buypq.rbegin()->first, askP = sellpq.begin()->first;

if(bidP >= askP) {
// trade
set<int>& bitem = buypq.rbegin()->second;
set<int>& sitem = sellpq.begin()->second;

// bitem = {id1, id2....}, sitem = {id1, id2,...}

int bi = *bitem.begin(), si = *sitem.begin();
int sz = min(books[bi].size, books[si].size);

// then print trade information
printf("TRADE %d %d\n", sz, flag ? books[bi].price : books[si].price);

// trade begin
books[bi].size -= sz; books[si].size -= sz;
buytab[books[bi].price] -= sz; selltab[books[si].price] -= sz;

if(books[bi].size == 0) bitem.erase(bi);
if(bitem.size() == 0) buypq.erase(books[bi].price);

if(books[si].size == 0) sitem.erase(si);
if(sitem.size() == 0) sellpq.erase(books[si].price);
} else {
return;
}
}
}

void quote() {
//
while(buytab.size() && buytab.rbegin()->second <= 0)
buytab.erase(buytab.rbegin()->first);
while(selltab.size() && selltab.begin()->second <= 0)
selltab.erase(selltab.begin()->first);

printf("QUOTE ");
if(buytab.size()) {
// print (size, price) = (second, first)
printf("%d %d", buytab.rbegin()->second, buytab.rbegin()->first);
} else {
printf("0 0");
}

cout << " - ";

if(selltab.size()) {
printf("%d %d", selltab.begin()->second, selltab.begin()->first);
} else {
printf("0 99999");
}
cout << endl;
}

int main() {
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int n = 0, kase = 0;
string cmd;

while(scanf("%d", &n) == 1) {
//
if(kase++) cout << endl;

init();

int size, price;
int id;
for(int i = 0; i < n; i++) {
cin >> cmd;
if(cmd == "BUY") {
cin >> size >> price;
books.push_back(Order(cmd, price, size));

buypq[price].insert(i);
buytab[price] += size;
trade(0);
} else if(cmd == "SELL") {
cin >> size >> price;
books.push_back(Order(cmd, price, size));

sellpq[price].insert(i);
selltab[price] += size;
trade(1);
} else if(cmd == "CANCEL") {
cin >> id; id--;
books.push_back(Order(cmd, 0, id));
// 0 is illegal

if(books[id].cmd == "BUY") {
//
int p = books[id].price, q = books[id].size;
buypq[p].erase(id);
if(buypq[p].size() == 0) buypq.erase(p);
buytab[p] -= q;

books[id].size = 0;

} else if(books[id].cmd == "SELL") {
//
int p = books[id].price, q = books[id].size;
sellpq[p].erase(id);
if(sellpq[p].size() == 0) sellpq.erase(p);
selltab[p] -= q;

books[id].size = 0;
}
}

// one cmd finished
quote();
}
}
}

优先队列与面向对象思想

Use of Hospital Facilities

具体实现如下:
UVA212

维护一个优先队列,先pq = priority_queue.pop(),出队的时候同时维护next进队元素的信息
then priority_queue.push(next)

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
154
155
156
//
// main.cpp
// UVA212
//
// Created by zhangmin chen on 2019/5/7.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Room {
public:
int beg, id;
Room(int beg, int id) : beg(beg), id(id) {}

bool operator < (const Room& rhs) const {
if(beg != rhs.beg) return beg > rhs.beg;
return id > rhs.id;
}
};

// we use priority queue;
// room --> bed

class Patient {
public:
char name[105];
int opT, bedT;
int id, roomID, bedID;
int opS, opEnd;
int bedS, bedEnd;
};

bool cmp(Patient& lhs, Patient& rhs) {
if(lhs.opEnd != rhs.opEnd) return lhs.opEnd < rhs.opEnd;
return lhs.roomID < rhs.roomID;
}

bool cmp2(Patient& lhs, Patient& rhs) {
return lhs.id < rhs.id;
}

// n opRooms, m beds, H start hours
// t1 trans-time, t2 pre-opTime, t3 pre-bedTime
// k paitients

int main() {
freopen("input.txt", "r", stdin);

int n, m, H, t1, t2, t3, k;
while(~ (scanf("%d%d%d%d%d%d%d", &n, &m, &H, &t1, &t2, &t3, &k)) ) {
// init

vector<Patient> pents(k);
priority_queue<Room> rooms;
vector<int> rUsed(n+1, 0);

for(int i = 1; i <= n; i++) rooms.push(Room(H*60, i));
// then we get all rooms

for(int i = 0; i < k; i++) {
Patient& p = pents[i];
cin >> p.name >> p.opT >> p.bedT;
p.id = i+1;

// then we get each patient

Room r = rooms.top(); rooms.pop();

p.opS = r.beg; p.opEnd = p.opS + p.opT;
p.bedS = p.opEnd + t1; p.bedEnd = p.bedS + p.bedT;

p.roomID = r.id;
rUsed[r.id] += p.opT;

rooms.push(Room(p.opEnd + t2, r.id));
}

// we arrange op-Room for each patient

sort(pents.begin(), pents.end(), cmp);

// then arrange bed for each patient
int END = 0;
vector<int> bUsed(m+1, 0);
vector<int> Beds(m+1, H*60);

for(int i = 0; i < k; i++) {
Patient& p = pents[i];
int j;
for(j = 1; j <= m; j++) {
if(Beds[j] <= p.opEnd) break;
}

// &p: get into Beds[j];

p.bedID =j;
Beds[j] = p.bedEnd + t3;
bUsed[j] += p.bedT;

END = max(END, p.bedEnd);
}


// we arrange beds for each patient
sort(pents.begin(), pents.end(), cmp2);

puts(" Patient Operating Room Recovery Room");
puts(" # Name Room# Begin End Bed# Begin End");
puts(" ------------------------------------------------------");

for(int i = 0; i < k; i++) {
const Patient& p = pents[i];
printf("%2d %-9s ", p.id, p.name);
printf("%2d %3d:%02d %3d:%02d ", p.roomID, p.opS/60, p.opS%60, p.opEnd/60, p.opEnd%60);
printf("%2d %3d:%02d %3d:%02d\n", p.bedID, p.bedS/60, p.bedS%60, p.bedEnd/60, p.bedEnd%60);
}
printf("\n");

puts("Facility Utilization");
puts("Type # Minutes % Used");
puts("-------------------------");

for(int i = 1; i <= n; i++)
printf("Room %2d %7d %7.2f\n", i, rUsed[i], rUsed[i] * 100.0 / (END - H*60));
for(int i = 1; i <= m; i++)
printf("Bed %2d %7d %7.2f\n", i, bUsed[i], bUsed[i] * 100.0 / (END - H*60));

printf("\n");
}
}

Trie树

Trie树的实现

TrieST1
TrieST2
TrieST3
TrieST4

代码实现如下:

TrieST.h

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
//
// Created by zhangmin chen on 2019/2/12.
//

#ifndef TRIEST_TRIEST_H
#define TRIEST_TRIEST_H

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stdexcept>
#include <cassert>
#include <algorithm>

using namespace std;

class TrieST {
private:
class Node {
public:
Node() : next(256, nullptr), val(0), flag(false) {}
~Node() {
for(int i = 0; i < R; i++) if(next[i])
delete(next[i]);
}

int val;
bool flag;
vector<Node *> next;
};

public:
// int main() to create!
TrieST() : n(0), root(nullptr) {}
~TrieST() { delete(root); }

int get(string key) {
if(key.empty()) throw invalid_argument("argument to get() is null");
Node* x = get(root, key, 0);
if(x == nullptr) throw runtime_error("Without this key");
return x->val;
}

void put(string key, int val) {
if(key.empty()) throw invalid_argument("first argument to put() is null");
else root = put(this->root, key, val, 0);
}

string longestPrefixOf(string query) {
if(query.empty()) throw invalid_argument("argument to longestPrefixOf() is null");
int length = longestPrefixOf(root, query, 0, -1);
if(length == -1) return "";
else return query.substr(0, length);
}

queue<string> keysWithPrefix(string pre) {
queue<string> res;
Node* x = get(root, pre, 0);
collect(x, pre, res);
return res;
}

queue<string> keysMatch(string pat) {
queue<string> res;
collect(root, "", pat, res);
return res;
}

void delete_(string key) {
if(key.empty()) throw invalid_argument("argument to delete() is null");
root = delete_(root, key, 0);
}

int size() { return n; }
bool isempty() { return size() == 0; }
queue<string> keys() {
return keysWithPrefix("");
}
bool contains(string key) {
if(key.empty()) throw invalid_argument("argument to contains() is null");
return get(root, key, 0) != nullptr;
}


private:
Node* get(Node* x, string key, int d) {
if(x == nullptr) return nullptr;
if(d == key.length()) return x;
char c = key[d];
return get(x->next[c], key, d+1);

// c = key[0] begin searching
// start: get(key[0], key, 1)
// root is just a node without message
}

Node* put(Node* x, string key, int val, int d) {
if(x == nullptr) x = new Node();
if(d == key.length()) {
x->val = val; x->flag = true;
return x;
}
char c = key[d];
x->next[c] = put(x->next[c], key, val, d+1);
return x;
}

void collect(Node* x, string pre, queue<string>& res) {
if(x == nullptr) return;
if(x->flag) res.push(pre);

for(unsigned char c = 0; ; c++) {
pre.push_back(c);
collect(x->next[c], pre, res);
pre.pop_back();
if(c == R-1) break;
}
}
void collect(Node* x, string pre, string pat, queue<string>& res) {
if(x == nullptr) return;
int d = pre.length();
if(d == pat.length() && x->flag) res.push(pre);
// 遇到x->flag, 进队列
if(d == pat.length()) return;

char c = pat[d];
if(c == '.') {
//
for(unsigned char ch = 0; ; ch++) {
pre.push_back(ch);
collect(x->next[ch], pre, pat, res);
pre.pop_back();

if(ch == R-1) break;
}
} else {
pre.push_back(c);
collect(x->next[c], pre, pat, res);
pre.pop_back();
}
}

int longestPrefixOf(Node* x, string query, int d, int length) {
if(x == nullptr) return length;
if(x->flag) length = d;
if(d == query.length()) return length;

char c = query[d];
return longestPrefixOf(x->next[c], query, d+1, length);
}

Node* delete_(Node* x, string key, int d) {
if(x == nullptr) return nullptr;
if(d == key.length()) {
if(x->flag) n--;
x->flag = false;
} else {
char c = key[d];
x->next[c] = delete_(x->next[c], key, d+1);
}

// remove subtrie rooted at x if it is completely empty
if(x->flag) return x;
for(int c = 0; c < R; c++) if(x->next[c] != nullptr)
return x;
return nullptr;

// in recur, x->next[c] = nullptr, fix the bug of Leaking memory
}

private:
static const int R;
Node* root; // root of trie
int n; // number of keys in trie
};

const int TrieST::R = 256;

#endif //TRIEST_TRIEST_H

main.cpp

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
#include "./cmake-build-debug/TrieST.h"
#include <fstream>

int main() {
freopen("input.txt", "r", stdin);
string tmp;
int cnt = 0;
TrieST st;

while(cin >> tmp) {
// cout << tmp << endl;
st.put(tmp, cnt++);
}

if(st.size() < 100) {
cout << "keys(\"\"):" << endl;
auto res = st.keys();
while(!res.empty()) {
cout << res.front() << " " << st.get(res.front()) << endl;
res.pop();
}
cout << endl;
}

cout << "longestPrefixOf(\"shellsort\"):" << endl;
cout << st.longestPrefixOf("shellsort") << endl;
cout << endl;

cout << "longestPrefixOf(\"quicksort\"):" << endl;
cout << st.longestPrefixOf("quicksort") << endl;
cout << endl;

cout << "keyWithPrefix(\"shor\"):" << endl;
auto res = st.keysWithPrefix("shor");
while(!res.empty()) {
cout << res.front() << endl;
res.pop();
}
cout << endl;

cout << "keysThatMatch(\".he.l.\"):" << endl;
auto res2 = st.keysMatch(".he.l.");
while(!res2.empty()) {
cout << res2.front() << endl;
res2.pop();
}
cout << endl;
}

三向单词查找树

TST.h

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//
// Created by zhangmin chen on 2019/2/13.
//

#ifndef TST_TST_H
#define TST_TST_H

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <queue>

using namespace std;

class TST {
private:
class Node {
public:
// construction
Node() : left(nullptr), mid(nullptr), right(nullptr), isString(false) {}
~Node() {
if(left) delete(left);
if(right) delete(right);
if(mid) delete(mid);
}

unsigned char c;
bool isString;
Node *left, *mid, *right;
int val;
};

public:
// construction
TST() : n(0), root(nullptr) {}
~TST() { delete(root); }

int size() { return n; }
bool contains(string key) {
if(key.empty()) {
throw invalid_argument("argument to contains() is null!");
}
return get(root, key, 0) != nullptr;
}

int get(string key) {
if(key.empty()) throw invalid_argument("calls get() with null argument");
Node *x = get(root, key, 0);
if(x == nullptr) throw runtime_error("This key not int this table");
return x->val;
}

void put(string key, int val) {
if(key.empty()) throw invalid_argument("calls put() with null key");
if(!contains(key)) n++;
root = put(root, key, val, 0);
}

string longestPrefixOf(string query) {
if(query.length() == 0) return "";
int len = 0;
Node* x = root;

int i = 0;
while(i < query.length() && x != nullptr) {
char ch = query[i];
if(ch < x->c) x = x->left;
else if(ch > x->c) x = x->right;
else {
i++;
if(x->isString) len = i;
x = x->mid;
}
}

return query.substr(0, len);
}

queue<string> keys() {
queue<string> que1;
string tmp = "";
collect(root, tmp, que1);
return que1;
}

queue<string> keysWithPrefix(string pre) {
if(pre.empty()) throw invalid_argument("calls keysWithPrefix() with null argumemnt");

queue<string> que2;
Node *x = get(root, pre, 0);

if(x == nullptr) return que2;
if(x->isString) que2.push(pre);
collect(x->mid, pre, que2);
return que2;
}

queue<string> keysThatMatch(string pat) {
queue<string> que;
string pre = "";
collect(root, pre, 0, pat, que);
return que;
}

private:
Node *get(Node *x, string key, int d) {
if(x == nullptr) return nullptr;
if(key.length() == 0) throw invalid_argument("key must have length >= 1");
unsigned char ch = key[d];

if(ch < x->c) return get(x->left, key, d);
else if(ch > x->c) return get(x->right, key, d);
else if (d < key.length()-1) return get(x->mid, key, d+1);
else return x;
}

Node *put(Node *x, string key, int val, int d) {
char ch = key[d];
if(x == nullptr) {
x = new Node(); x->c = ch;
}

if(ch < x->c) x->left = put(x->left, key, val, d);
else if(ch > x->c) x->right = put(x->right, key, val, d);
else if(d < key.length()-1) x->mid = put(x->mid, key, val, d+1);
else {
x->val = val; x->isString = true;
}
return x;
}

void collect(Node *x, string& pre, queue<string>& res) {
if(x == nullptr) return;
collect(x->left, pre, res);
if(x->isString) {
pre.push_back(x->c); res.push(pre); pre.pop_back();
// find prefix
}

pre.push_back(x->c);
collect(x->mid, pre, res);
pre.pop_back();

collect(x->right, pre, res);
}

void collect(Node *x, string& pre, int d, const string& pat, queue<string>& res) {
if(x == nullptr) return;
char ch = pat[d];

if(ch == '.' || ch < x->c) collect(x->left, pre, d, pat, res);
if(ch == '.' || ch == x->c) {
if(d == pat.length()-1 && x->isString) {
pre.push_back(x->c);
res.push(pre);
}
if(d < pat.length()-1) {
pre.push_back(x->c);
collect(x->mid, pre, d+1, pat, res);
pre.pop_back();
}
}
if(ch == '.' || ch > x->c) collect(x->right, pre, d, pat, res);
}


private:
int n;
Node* root;
};

#endif //TST_TST_H

main.cpp

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
#include "./cmake-build-debug/TST.h"

#include <fstream>

int main() {
freopen("input.txt", "r", stdin);

string tmp;
int cnt = 0;
TST tst;
while(cin >> tmp) {
//
tst.put(tmp, cnt++);
}

if(tst.size() < 100) {
cout << "keys(\"\"):" << endl;
auto res = tst.keys();
while(!res.empty()) {
cout << res.front() << endl;
res.pop();
}
cout << endl;
}

cout << "longestPrefixOf(\"shellsort\"):" << endl;
cout << tst.longestPrefixOf("shellsort") << endl;
cout << endl;

cout << "longestPrefixOf(\"quicksort\"):" << endl;
cout << tst.longestPrefixOf("quicksort") << endl;
cout << endl;

cout << "keysWithPrefix(\"shor\"):" << endl;
auto res = tst.keysWithPrefix("shor");
while(!res.empty()) {
cout << res.front() << endl;
res.pop();
}
cout << endl;

cout << "keysThatMatch(\".he.l.\"):" << endl;
auto res2 = tst.keysThatMatch(".he.l.");
while(!res2.empty()) {
cout << res2.front() << endl;
res2.pop();
}
cout << endl;
}

Trie树的优化

使用memset(ch[sz], 0, sizeof(ch[sz])), ch[u][c] = sz++
来开辟一个子节点
如果没到字符串末尾,val[sz] = 0
只有到达字符串末尾,才保存val值

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
template<maxnode, sigmaSize>
class Trie {
public:
int ch[maxnode][sigmaSize];
int val[maxnode];
int sz;

Trie() {
sz = 1;
memset(ch, 0, sizeof(ch[0]))
// 相当于new Node(root)
}

void insert(const string& str, int v) {
int u = 0;
for(int i = 0; i < str.length(); i++) {
int c = idx(str[i]);
if(!ch[u][c]) {
// 开辟一个子节点, 值为sz
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0; //没到str结尾,所有的val都为0,只在str结尾保存值
ch[u][c] = sz++;
}
u = ch[u][c];
}

// str结尾了,保存字符串的值
val[u] = v;
}
};

Trie树解决大整数问题

Revenge of Fibonacci

涉及到的一些stl函数

1
2
3
4
5
6
int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvector(7);

copy(myints, myints+7, myvector.begin())

// 把myints[0]往后7个元素复制到myvector中

相似的用法

1
2
3
4
5
string str = "abcdefg"
string tmp;

tmp.append(str, 0, 3);
// tmp后面附加上从str[0]往后3个字符

Trie树在BigInt上的优势
完美解决前导0
比如一个数是0067
由于trie树只会在字符串末尾保存0067的val,这个val可以是真实值,也可以是索引,也可以是哈希
所以保证node u扫完整个字符串,看val[u]的值就可以

stringstream用于string类和其他值类型的转换

1
2
3
4
5
6
7
stringstream ss;
char buf[maxn];
for(i = 0; i < maxn; i++)
sprintf(buf, "%d", arr[i]);

ss << buf;
cout << ss.str() << endl;

基本思想
revenge-fibonacci

本例和一般单词查找树的异同

1
2
3
4
5
6
if(ch[u][c] == -1) {
memset(ch[sz], -1, sizeof(ch[sz]));
val[sz] = v;
// 一般单词查找树val[sz] = 0;
ch[u][c] = sz++;
}

一般单词查找树,val[sz] = 0,只在字符串末尾保存相应的值
本例中,因为是根据前缀(斐波那契数的前几个部分数字),来猜到是第几个斐波那契数
所以所有的前缀都必须保存v信息,val[sz] = v

代码实现如下

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
//
// main.cpp
// UVA12333
//
// Created by zhangmin chen on 2019/5/7.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int BASE = 10000;
const int MAXLEN = 6000;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

template <int maxn>
class BigInt {
public:
int len, s[maxn];
BigInt() {
Set(s, 0);
len = 1;
}

BigInt& operator= (int num) {
if(num == 0) {
len = 1;
return *this;
}

len = 0;
while(num > 0) {
s[len++] = num % BASE;
num /= BASE;
}
return *this;
}

BigInt& operator= (const BigInt& rhs) {
len = rhs.len;
copy(rhs.s, rhs.s + rhs.len, s);
return *this;
}

BigInt(int num) {
*this = num;
}
};

typedef BigInt<MAXLEN> fBig;

string Reverse(const fBig& fi) {
int tot = 0;
char buf[8];

stringstream ss;
bool first = true;
for(int i = 0; i < fi.len; i++) {
if(first) {
first = false;
sprintf(buf, "%d", fi.s[fi.len - 1 - i]);
} else sprintf(buf, "%04d", fi.s[fi.len - 1 - i]);

ss << buf;
tot += strlen(buf);
if(tot >= 41) break;
}
return ss.str();
}


template <int maxNode, int sigmaSize>
class Trie {
public:
int ch[maxNode][sigmaSize], val[maxNode];
int sz;

Trie() {
Set(ch[0], -1);
Set(val, 0);
sz = 1;
}

int idx(char c) const { return c - '0'; }

void insert(const string& str, int v) {
int u = 0;
for(int i = 0; i < str.length(); i++) {
//
int c = idx(str[i]);
if(ch[u][c] == -1) {
//
Set(ch[sz], -1);
val[sz] = v;
ch[u][c] = sz++;
}

u = ch[u][c];
}

val[u] = v;
}

int getVal(const string& str) const {
int v = -1, u = 0;
for(int i = 0; i < str.length(); i++) {
//
int c = idx(str[i]);
if(ch[u][c] == -1) return v;
u = ch[u][c];
}

if(val[u]) v = val[u];
return v;
}

};

void Add(const fBig& f1, const fBig& f2, fBig& f3) {

int len = max(f1.len, f2.len);

int p = 0;
for(int i = 0, carry = 0; ; i++) {
if(carry == 0 && i >= len) break;
int x = carry;
if(i < f1.len) x += f1.s[i];
if(i < f2.len) x += f2.s[i];

f3.s[p++] = x % BASE;
carry = x / BASE;
}
f3.len = p;
}

/*
ostream& operator<< (ostream& os, const fBig& fi) {
char buf[8];
stringstream ss;
bool first = true;
for(int i = fi.len - 1; i >= 0; i--) {
if(first) {
first = false;
ss << fi.s[i];
} else {
sprintf(buf, "%04d", fi.s[i]);
ss << buf;
}
}
const string& str = ss.str();
if(str.empty()) return os << 0;
return os << str;
}
*/

Trie<4000000, 10> trie;
fBig f0 = 0, f1 = 1, f;
const int MAXF = 100000;

int main() {
freopen("input.txt", "r", stdin);
for(int i = 2; i < MAXF; i++) {
Add(f0, f1, f);
string rev = Reverse(f);

trie.insert(rev, i-1);
f0 = f1;
f1 = f;
}

int kase;
scanf("%d", &kase);
char buf[60];
for(int k = 1; k <= kase; k++) {
scanf("%s", buf);
int ans = 0;
string str(buf);
if(str != "1") ans = trie.getVal(str);
printf("Case #%d: %d\n", k, ans);
}
}

模拟操作系统:多线程处理

流水线时间 — 取出任务放入缓存表 — 更新缓存表 — 判断任务进行情况

Queue and A

分析

LA5222

solution 1

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
//
// main.cpp
// LA5222
//
// Created by zhangmin chen on 2019/5/8.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;



#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

const int MAXTIME = 500000;

class Topic {
public:
int tid, num, t0, t, dt;
int tot;
};

class Cust {
public:
int pid, k;
vector<int> cTopics;

int dtime, handle, last;
bool busy;

Cust() {
pid = -1;
k = 0;
cTopics.clear();

dtime = 0;
handle = -1;
last = 0;
busy = 0;
}

bool operator< (const Cust& rhs) const {
if(last == rhs.last) return pid > rhs.pid;
return last > rhs.last;
}
};

vector<Topic> topics;
vector<Cust> custs;

map<int, int> idxT;
map<int, int> idxC;

map<int, vector<Cust> > buf;
typedef map<int, vector<Cust> >::iterator mv;

bool can_assign(int tID, int timing) {
//
if(timing < topics[tID].t0) return 0;
if(topics[tID].dt == 0) return topics[tID].num > 0;
if(topics[tID].num == 0) return 0;

int arriving = (timing - topics[tID].t0) / topics[tID].dt;
int already_assigned = topics[tID].tot - topics[tID].num;

if(arriving < already_assigned) return 0;
return 1;
}

void init() {
topics.clear();
custs.clear();
idxT.clear();
idxC.clear();
buf.clear();
}


int main() {
freopen("input.txt", "r", stdin);
int n, m, kase = 0;

// n topics, m custs
while(cin >> n && n) {
init();
int timing = 0;

for(int i = 0; i < n; i++) {
Topic tp;
cin >> tp.tid >> tp.num >> tp.t0 >> tp.t >> tp.dt;

tp.tot = tp.num;
idxT[tp.tid] = i;

topics.push_back(tp);
}

cin >> m;
for(int i = 0; i < m; i++) {
Cust cst;
cin >> cst.pid >> cst.k;
idxC[cst.pid] = i;

for(int j = 0; j < cst.k; j++) {
int x;
cin >> x;
cst.cTopics.push_back(idxT[x]);
}

custs.push_back(cst);
}
// finished input data

for(timing = 0; timing < MAXTIME; timing++) {
buf.clear();
// check busy of each custs
for(int i = 0; i < m; i++) {
if(!custs[i].busy) {
for(int j = 0; j < custs[i].k; j++) {
int tp = custs[i].cTopics[j];
if(can_assign(tp, timing)) {
// assign tp to custs[i]
if(!buf.count(tp)) buf[tp] = vector<Cust> ();
buf[tp].push_back(custs[i]);
break;
}
}
}
}

// check buf
for(mv it = buf.begin(); it != buf.end(); it++) {
sort(it->second.begin(), it->second.end());
int c = idxC[it->second[0].pid];
custs[c].busy = 1;
custs[c].last = timing;
custs[c].handle = it->first;
topics[it->first].num--;
}

// update custs dtime
for(int i = 0; i < m; i++) {
if(custs[i].busy) custs[i].dtime++;
int tp = custs[i].handle;

if(custs[i].busy && custs[i].dtime == topics[tp].t) {
custs[i].busy = 0;
custs[i].dtime = 0;
}
}

// check finished
int finished = 1;

for(int i = 0; i < n; i++) {
if(topics[i].num > 0) {
finished = 0;
break;
}
}

for(int i = 0; i < m; i++) {
if(custs[i].busy > 0) {
finished = 0;
break;
}
}


if(finished) break;
// timing loop finished!
}


printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, timing + 1);
// while finished!
}
}

solution 2:离散跳转

LA5222B

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
//
// main.cpp
// LA5222B
//
// Created by zhangmin chen on 2019/5/10.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 0x3f3f3f3f;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Topic {
public:
int t;
queue<int> table;

Topic(int t_) {
t = t_;
while (!table.empty()) {
table.pop();
}
}

Topic() {
t = 0;
while (!table.empty()) {
table.pop();
}
}
};

class Person {
public:
int pid, k;
vector<int> tids;
int last, endT;

bool operator< (const Person& rhs) const {
if(last != rhs.last) return last < rhs.last;
return pid < rhs.pid;
}
};

int N, M;
map<int, Topic> topics;
vector<Person> persons;

void init() {
topics.clear();
persons.clear();
}

/*
*
int timing = min {all_t0}
while(N) {
int jump = inf;
// update jump through nxt
for(p = all persons)
int nxt = inf
update(nxt)
jump = min(jump, nxt)

timing = jump
}

*/

void assign(Person& p, int& nxt, int& ans, int timing) {
// default: p.endT < timing
_for(i, 0, p.k) {
// id = p.tids[i]
Topic& tp = topics[p.tids[i]];
if(tp.table.empty()) continue;

// nxt = latest topic time
nxt = min(nxt, tp.table.front());
if(tp.table.front() <= timing) {
// assign the topic
nxt = timing + tp.t;
ans = max(ans, nxt);
p.last = timing;

tp.table.pop();
if(tp.table.empty()) N--;

break;
}
}
p.endT = nxt;
}


int main() {
freopen("input.txt", "r", stdin);
int kase = 1;

while (cin >> N && N) {
init();

int timing = inf, ans = 0;
_for(i, 0, N) {
int tid, num, t0, t, dt;
cin >> tid >> num >> t0 >> t >> dt;
timing = min(timing, t0);

Topic tp(t);

while(num--) {
//
tp.table.push(t0);
t0 += dt;
}

topics[tid] = tp;
}

cin >> M;
persons.resize(M);
_for(i, 0, M) {
cin >> persons[i].pid >> persons[i].k;
persons[i].tids.resize(persons[i].k);
_for(j, 0, persons[i].k) {
cin >> persons[i].tids[j];
}
}

// we get all data

while(N) {
int jump = inf;
sort(persons.begin(), persons.end());
for(auto& p : persons) {
int nxt = inf;
// update(nxt), assigned the project
// if can assign? else ?

if(p.endT > timing) {
nxt = p.endT;
}
else {
assign(p, nxt, ans, timing);
}

jump = min(jump, nxt);
// for p loop finished;
}

timing = jump;
// while N loop finished
}
printf("Scenario %d: All requests are serviced within %d minutes.\n", kase++, ans);
}
}

STL高级排序:地图的放大和缩小

有的时候我们需要根据外关键字,对结构体排序

1
2
3
4
class Map {};
Map mp;
vector<Map> maps;
mps.push_back(mp);

我们需要根据外部的location,和mp.center的相对距离进行排序
其中location并不是Map的成员函数
这个时候cmp的写法

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
for i = 0 to maps.size()
if Area in map[i]
mapID.push_back(i);

check:
for i = 0 to mapID.size()
get maps[mapID[i]];

class Cmp {
public:
Point loc;

bool operator() (int lhs, int rhs) {
const Map& m1 = maps[lhs];
const Map& m2 = maps[rhs];

int d = Minus(dist(loc, m1.center), dist(loc, m2.center))
// |loc - map.center| 值大的放在前面,默认m1 > m2
// 如果m1 > m2, 不改变位置

if(d > 0) return true;
if(d < 0) return false;
}
};

Cmp cmp;
sort(mapID.begin(), mapID.end(), cmp);

其中cmp结构体,重载了()运算符
operator() 返回true,不换位置,返回false,互换位置

另外一般意义的写法:

1
2
3
4
5
6
bool cmp(Student& s1, Student& s2) {
if(s1.score != s2.score) return s1.score > s2.score;
else return strcmp(s1.name, s2.name);
}

// 默认s1在s2前面

并列情况的处理
先获取一个排名vector& rank
if score[i-1] < score[i], rank[i]++

然后把排名转换成索引, 查找rk对应的id
int p = upper_bound(rank.begin(), rank.end(), rk) - rank.begin()
Map& res = maps[mapID[p-1]]

最后关于排名转换成索引的问题
见level和id的图
如下所示

LA5197

代码

实现方法:

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
//
// main.cpp
// LA5197
//
// Created by zhangmin chen on 2019/5/11.
// Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const double eps = 1e-7;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Point {
public:
double x, y;
Point(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) {}

};

Point operator+ (const Point& lhs, const Point& rhs) {
return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point operator- (const Point& lhs, const Point& rhs) {
return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point operator* (const Point& lhs, double p) {
return Point(lhs.x * p, lhs.y * p);
}

istream& operator>> (istream& is, Point& rhs) {
return is >> rhs.x >> rhs.y;
}
double dist(const Point& lhs, const Point& rhs) {
double tmp = (lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y);
return sqrt(tmp);
}

int Minus_(double x) {
//
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}

int Minus(double x, double y) {
return Minus_(x - y);
}

bool inRange(double x, double left, double right) {
//
if(Minus(left, right) > 0) return inRange(x, right, left);
return Minus(left, x) <= 0 && Minus(x, right) <= 0;
}

bool inArea(const Point& p, const Point& lhs, const Point& rhs) {
return inRange(p.x, lhs.x, rhs.x) && inRange(p.y, rhs.y, lhs.y);
// made a bug here
}


class Map {
public:
string name;
Point p1, p2, center, corner;

double width, height, area, ratio, minx;

Map(string name_, Point p1_, Point p2_) {
name = name_;
p1 = p1_;
p2 = p2_;

center = (p1 + p2) * .5;
width = fabs(p1.x - p2.x);
height = fabs(p1.y - p2.y);
ratio = fabs(height / width - 0.75);
area = width * height;

corner = Point(center.x + width / 2, center.y - height / 2);
minx = center.x - width / 2;
}
};

vector<Map> map_s;
map<string, Point> locats;

class Cmp {
public:
Point loc;

bool operator() (int lhs, int rhs) {
//
const Map& m1 = map_s[lhs];
const Map& m2 = map_s[rhs];

int d;

d = Minus(m1.area, m2.area);
if(d > 0) return true;
if(d < 0) return false;

d = Minus(dist(m1.center, loc), dist(m2.center, loc));
if(d > 0) return true;
if(d < 0) return false;

d = Minus(m1.ratio, m2.ratio);
if(d > 0) return true;
if(d < 0) return false;

d = Minus(dist(loc, m1.corner), dist(loc, m2.corner));
if(d < 0) return true;
if(d > 0) return false;

d = Minus(m1.minx, m2.minx);
if(d > 0) return true;
if(d < 0) return false;

return false;
}
};

void getMapLevel(const Point pt, vector<int>& level, vector<int>& id) {
//
id.clear();

Cmp cmp;
cmp.loc = pt;

_for(i, 0, map_s.size()) {
const Map& mp = map_s[i];
if(inArea(pt, mp.p1, mp.p2)) {
id.push_back(i);
// debug(inArea(pt, mp.p1, mp.p2));
}
}

sort(id.begin(), id.end(), cmp);
level.clear();
level.assign(id.size(), 1);

_for(i, 1, id.size()) {
const Map& m1 = map_s[id[i-1]];
const Map& m2 = map_s[id[i]];

level[i] = level[i-1];
int d = Minus(m2.area, m1.area);
if(d < 0) level[i]++;
}
}

void solve(const string& name, int lv) {
//
// vector<int> levels;

cout << name << " at detail level " << lv;
if(!locats.count(name)) {
cout << " unknown location" << endl;
return;
}

vector<int> ID, levels;
getMapLevel(locats[name], levels, ID);

if(ID.empty()) {
cout << " no map contains that location" << endl;
return;
}

int maxlv = levels.back();
// debug(maxlv);
if(maxlv < lv) {
//
cout << " no map at that detail level; using " << map_s[ID.back()].name << endl;
} else {
//
int p = (int)(upper_bound(levels.begin(), levels.end(), lv) - levels.begin());
cout << " using " << map_s[ID[p-1]].name << endl;
}
}

int main() {
freopen("input.txt", "r", stdin);
string buf;
getline(cin, buf);

while (true) {
string name;
cin >> name;
if(name == "LOCATIONS") break;

Point p1_, p2_;
cin >> p1_ >> p2_;
// cout << p1_.x << " " << p1_.y << " " << p2_.x << " " << p2_.y << endl;
Map mp(name, p1_, p2_);

map_s.push_back(mp);
}

while(true) {
string name;
cin >> name;
if(name == "REQUESTS") break;
Point pt;
cin >> pt;
locats[name] = pt;
}

//_for(i, 0, map_s.size()) cout << map_s[i].name << " " << map_s[i].p1.x << endl;

while (true) {
string name;
cin >> name;
if(name == "END") break;
int lv;
cin >> lv;
solve(name, lv);
}
return 0;
}