这篇文章主要针对一些复杂的模拟题，给出stl处理模拟题的一些思路
以及一部分模版

栈，队列与优先队列

求抽象数据结构的ID(), 并且构建map映射
策略1：线程池MemPool
策略2：用vector.size()值作为哈希

相关的实现如下：

LA3634

The SetStack Computer

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
//
//  main.cpp
//  LA3634
//
//  Created by zhangmin chen on 2019/4/21.
//  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>

using namespace std;
typedef long long llong;

#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)


template <typename T>
class MemPool {
public:
    vector<T*> buf;
    
    T* create() {
        buf.push_back(new T());
        return buf.back();
    }
    
    void dispose() {
        for(int i = 0; i < buf.size(); i++) delete buf[i];
        buf.clear();
    }
};

map<set<int>, int> IDCache;
vector<set<int> > setCache;
MemPool<set<int> > pool;

void fresh() {
    IDCache.clear();
    setCache.clear();
}

int ID(const set<int>& st) {
    if(IDCache.count(st)) return IDCache[st];
    setCache.push_back(st);
    return IDCache[st] = (int)setCache.size() - 1;
}

// important

void solve() {
    stack<int> stk;
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        
        if(cmd[0] == 'P') {
            set<int> cur = *(pool.create());
            int pid = ID(cur);
            stk.push(pid);
        } else if (cmd[0] == 'D') {
            stk.push(stk.top());
        }
        else {
            set<int> st1 = setCache[stk.top()]; stk.pop();
            set<int> st2 = setCache[stk.top()]; stk.pop();
            set<int> combine;
            
            if(cmd[0] == 'U') set_union(st1.begin(), st1.end(), st2.begin(), st2.end(), inserter(combine, combine.begin()));
            if(cmd[0] == 'I') set_intersection(st1.begin(), st1.end(), st2.begin(), st2.end(), inserter(combine, combine.begin()));
            
            if(cmd[0] == 'A') {
                combine = st2;
                combine.insert(ID(st1));
            }
            
            stk.push(ID(combine));
        }
        cout << setCache[stk.top()].size() << endl;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    while(kase--) {
        solve();
        printf("***\n");
        pool.dispose();
    }
}

大整数类BigInteger

A + B Problem II

BigInteger

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string.h>

using namespace std;
typedef long long llong;

struct BigInteger{
    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> bit;

    BigInteger(llong num = 0) { *this = num; }
    BigInteger operator= (llong num){
        bit.clear();
        do{
            bit.push_back(num % BASE);
            num /= BASE;
        }while(num > 0);
        return *this;
    }
    BigInteger operator= (const string& str){
        bit.clear();
        int x;
        int len = (str.length()-1)/WIDTH + 1;

        for(int i = 0; i < len; i++){
            int end = str.length()-i*WIDTH;
            //end :[start..end-1] end empty
            int start = max(0,end-WIDTH);
            sscanf(str.substr(start,end-start).c_str(),"%d",&x);
            bit.push_back(x);
        }
        return *this;
    }
    BigInteger operator+ (const BigInteger& b) const{
        BigInteger sum;
        sum.bit.clear();

        for(int i = 0, carry = 0; ;i++){
            if(carry == 0 && i >= bit.size() && i >= b.bit.size())
                break;

            int x = carry;
            if(i < bit.size())
                x += bit[i];
            if(i < b.bit.size())
                x += b.bit[i];

            sum.bit.push_back(x % BASE);
            carry = x / BASE;
        }
        return sum;
    }

    BigInteger operator+= (const BigInteger& b){
        *this = *this + b;
        return *this;
    }

    bool operator < (const BigInteger& b) const {
        if(bit.size() != b.bit.size())
            return bit.size() < b.bit.size();

        for(int i = bit.size()-1; i >= 0; i--){
            if(bit[i] != b.bit[i])
                return bit[i] < b.bit[i];
        }
        return false;
    }
};

ostream& operator<< (ostream &out, const BigInteger& x){
    out << x.bit.back();
    for(int i = x.bit.size()-2; i >= 0; i--){
        char buffer[20];
        sprintf(buffer,"%08d",x.bit[i]);
        for(int j = 0; j < strlen(buffer); j++)
            out << buffer[j];
    }
    return out;
}

istream& operator>> (istream &in, BigInteger& x){
    string s;
    if(!(in >> s))
        return in;
    x = s;
    return in;
}

int main(){
    int kase, pid = 0;
    cin >> kase;
    while(kase--){
        BigInteger a,b;
        cin >> a >> b;
        printf("Case %d:\n",++pid);
        cout << a << " + " << b << " = " << a+b << endl;
        if(kase != 0) printf("\n");
    }
}

大整数的加减乘除

BigInt

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
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
//
//  main.cpp
//  week4V7
//
//  Created by zhangmin chen on 2019/5/1.
//  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 BigInt {
    string val;
    bool flag;
    
    inline int cmp(string s1, string s2) {
        if(s1.size() < s2.size()) return -1;
        else if(s1.size() > s2.size()) return 1;
        else return s1.compare(s2);
    }
    
public:
    BigInt() : val("0"), flag(true) {}
    BigInt(string str) {
        val = str;
        flag = true;
    }
    
    friend ostream& operator<< (ostream& os, const BigInt& rhs);
    friend istream& operator>> (istream& is, BigInt& rhs);
    BigInt operator+ (const BigInt& rhs);
    BigInt operator- (const BigInt& rhs);
    BigInt operator* (const BigInt& rhs);
    BigInt operator/ (const BigInt& rhs);
};


ostream& operator<< (ostream& os, const BigInt& rhs) {
    if(!rhs.flag) os << "-";
    os << rhs.val;
    return os;
}

istream& operator>> (istream& is, BigInt& rhs) {
    string str;
    is >> str;
    
    rhs.flag = true;
    rhs.val = str;
    return is;
}

BigInt BigInt::operator+ (const BigInt& rhs) {
    BigInt ret;
    ret.flag = true;
    
    string lval(val), rval(rhs.val);
    
    if(lval == "0") {
        ret.val = rval;
        return ret;
    }
    
    if(rval == "0") {
        ret.val = lval;
        return ret;
    }
    
    int lsize = (int) lval.size();
    int rsize = (int) rval.size();
    
    if(lsize < rsize) {
        //
        for(int i = 0; i < rsize - lsize; i++) {
            lval = "0" + lval;
        }
    }
    else {
        for(int i = 0; i < lsize - rsize; i++) {
            rval = "0" + rval;
        }
    }
    
    // then we finished alignment
    
    int bit, carry = 0;
    string res = "";
    
    reverse(lval.begin(), lval.end());
    reverse(rval.begin(), rval.end());
    
    for(int i = 0; i < lval.size(); i++) {
        //
        bit = (carry + lval[i] - '0' + rval[i] - '0') % 10;
        carry = (carry + lval[i] - '0' + rval[i] - '0') / 10;
        res = res + char(bit + '0');
    }
    
    if(carry == 1) res = res + "1";
    
    reverse(res.begin(), res.end());
    ret.val = res;
    return ret;
}

BigInt BigInt::operator-(const BigInt &rhs) {
    //
    BigInt ret;
    string lval(val), rval(rhs.val);
    
    if(rval == "0") {
        ret.val = lval;
        ret.flag = true;
        return ret;
    }
    
    if(lval == "0") {
        ret.val = rval;
        ret.flag = false;
        return ret;
    }
    
    int lsize = (int) lval.size();
    int rsize = (int) rval.size();
    
    if(lsize < rsize) {
        for(int i = 0; i < rsize - lsize; i++) {
            lval = "0" + lval;
        }
    }
    else {
        for(int i = 0; i < lsize - rsize; i++) {
            rval = "0" + rval;
        }
    }
    
    // then we finished alignment
    
    int t = lval.compare(rval);
    // lval < rval, -1
    // lval > rval, 1
    
    if(t < 0) {
        ret.flag = false;
        string tmp = lval;
        lval = rval;
        rval = tmp;
    }
    else if(t == 0) {
        ret.val = "0";
        ret.flag = true;
        return ret;
    } else {
        ret.flag = true;
    }
    
    // default: lval > rval
    
    reverse(lval.begin(), lval.end());
    reverse(rval.begin(), rval.end());
    
    string res = "";
    int load;
    
    for(int i = 0; i < lval.size(); i++) {
        if(lval[i] < rval[i]) {
            load = 1;
            while (lval[i+load] == '0') {
                lval[i+load] = '9';
                load++;
            }
            
            lval[i+load]--;
            res = res + char(lval[i] - rval[i] + ':');
        }
        else {
            res = res + char(lval[i] - rval[i] + '0');
        }
    }
    reverse(res.begin(), res.end());
    res.erase(0, res.find_first_not_of('0'));
    
    ret.val = res;
    return ret;
}


BigInt BigInt::operator* (const BigInt& rhs) {
    BigInt ret;
    string lval(val), rval(rhs.val);
    
    if(lval == "0" || rval == "0") {
        ret.val = "0";
        ret.flag = true;
        return ret;
    }
    
    int lsize = (int)lval.size();
    int rsize = (int)rval.size();
    // default : lval.size() > rval.size()
    if(lval < rval) {
        string tmp = lval;
        lval = rval;
        rval = tmp;
        
        lsize = (int)lval.size();
        rsize = (int)rval.size();
    }
    
    reverse(lval.begin(), lval.end());
    reverse(rval.begin(), rval.end());
    
    string ans;
    BigInt res, tmp;
    for(int i = 0; i < rval.size(); i++) {
        //
        ans = "";
        int carry = 0, bt = 0, rv = 0;
        
        for(int j = 0; j < i; j++) ans = ans + "0";
        
        rv = rval[i] - '0';
        for(int k = 0; k < lval.size(); k++) {
            int t = (rv * (lval[k] - '0') + carry);
            carry = t / 10;
            bt = t % 10;
            ans = ans + char(bt + '0');
        }
        
        if(carry) ans = ans + char(carry + '0');
        
        reverse(ans.begin(), ans.end());
        tmp.val = ans;
        res = res + tmp;
    }
    ret = res;
    return ret;
}

BigInt BigInt::operator/ (const BigInt &rhs) {
    //
    BigInt ret;
    string lval(val), rval(rhs.val);
    string quat;
    
    if(rval == "0") {
        ret.val = "error";
        ret.flag = true;
        return ret;
    }
    if(lval == "0") {
        ret.val = "0";
        ret.flag = true;
        return ret;
    }
    
    if(cmp(lval, rval) < 0) {
        //
        ret.val = "0";
        ret.flag = true;
        return ret;
    }
    else if(cmp(lval, rval) == 0) {
        ret.val = "1";
        ret.flag = true;
        return ret;
    } else {
        //
        // default: lval > rval
        
        int lsize = (int)lval.size();
        int rsize = (int)rval.size();
        string tmp;
        
        if(rsize > 1) tmp.append(lval, 0, rsize-1);
        
        for(int i = rsize - 1; i < lsize; i++) {
            tmp = tmp + lval[i];
            for(char c = '9'; c >= '0'; c--) {
                //
                BigInt t = (BigInt) rval * (BigInt)string(1, c);
                BigInt mod = (BigInt) tmp - t;
                
                if(mod.flag == true) {
                    quat = quat + c;
                    tmp = mod.val;
                    break;
                }
            }
        }
    }
    quat.erase(0, quat.find_first_not_of('0'));
    ret.val = quat;
    ret.flag = true;
    return ret;
}

int main() {
    // freopen("input.txt", "r", stdin);
    BigInt a, b, result;
    char op;
    cin >> a >> op >> b;
    
    switch(op) {
        case '+': result = a + b; break;
        case '-': result = a - b; break;
        case '*': result = a * b; break;
        case '/': result = a / b; break;
        default: break;
    }
    
    cout << result << endl;
}

map等stl高级用法

Database

LA4592

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
//
//  main.cpp
//  LA4592
//
//  Created by zhangmin chen on 2019/4/24.
//  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>

using namespace std;
typedef long long llong;

#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)

typedef pair<int, int> pii;
int m, n;
map<string, int> idx;

const int maxr = 10000 + 10;
const int maxc = 100 + 10;

int db[maxr][maxc], cnt = 0;

void init() {
    memset(db, 0, sizeof(db));
    idx.clear();
}

int getID(const string& str) {
    if(!idx.count(str)) return idx[str] = ++cnt;
    return idx[str];
}

void solve() {
    for(int c1 = 0; c1 < m; c1++) for(int c2 = c1+1; c2 < m; c2++) {
        map<pii, int> group;
        // group[c1, c2] = ith row
        
        // const pii& pr = make_pair();
        
        for(int i = 0; i < n; i++) {
            // group[(i,c1), (i,c2)] = ith row
            const pii& pr = make_pair(db[i][c1], db[i][c2]);
            
            if(group.count(pr)) {
                //
                printf("NO\n");
                printf("%d %d\n", group[pr]+1, i+1);
                printf("%d %d\n", c1+1, c2+1);
                return;
            }
            group[pr] = i;
        }
    }
    printf("YES\n");
    return;
}


int main() {
    freopen("input.txt", "r", stdin);
    while(cin >> n >> m) {
        init();
        
        
        string str;
        getline(cin, str);
        
        for(int i = 0; i < n; i++) {
            getline(cin, str);
            // cout << str << endl;
            // split by ','
            
            int k = -1;
            for(int j = 0; j < m; j++) {
                int p = (int)str.find(',', k+1);
                if(p == string::npos) p = (int)str.length();
                
                int hashv = getID(str.substr(k+1, p-k-1));
                db[i][j] = hashv;
                k = p;
                // db[i][j] = hash(substr)
            }
            
        }
        
        // get data finished!
        // then we solve the problem
        
        solve();
    }
}

复杂模拟：比赛排名，并列情况

有一类模拟题比较复杂，涉及以下情形
1、比赛成绩有并列情况；2、比赛涉及到奖金发放，业余选手不得奖金

PGA Tour Prize Money

PGA

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
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
//
//  main.cpp
//  PGA
//
//  Created by zhangmin chen on 2019/4/26.
//  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;

#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)

// const int maxn = 145;
const int przn = 70;


class Player {
public:
    string name;
    double prize;
    bool amat;
    bool t;
    
    int rnd[4];
    int dq;
    int rank;
    int pre, tot;
    
    // pre used to decide which one can be in round[3, 4], make the cut
    // tot used to divide money
    // only made the cut plyer can get money
    
    // divide prize:
    // 1 parallel
    // 2 amt don't get prize
    // 3 get prize?    Not amter && rank[1,70]
    
    
    // DQ:
    // 1 DQ > 2, plyer can make the cut
    // 2 but not rank in rnd[3,4]
    
    // make the cut:
    // DQ == 0 || DQ > 2   ---> make the cut
    
    // rank:
    // only DQ == 0 rank
    
    Player() {
        name.clear();
        prize = 0.0;
        amat = t = false;
        
        memset(rnd, 0, sizeof(rnd));
        dq = 4;
        rank = 0;
        pre = tot = 0;
    }
    
    void init() {
        prize = 0.0;
        amat = t = false;
        
        memset(rnd, 0, sizeof(rnd));
        dq = 4;
        rank = 0;
        pre = tot = 0;
    }
};

int n;

vector<Player> plyers;
double priz[przn];
double sum;

int str2num(const string& str) {
    int val = 0;
    for(int i = 0; i < str.length(); i++) {
        val = val * 10 + str[i] - '0';
    }
    //debug(val);
    return val;
}


void init() {
    //
    //for(int i = 0; i < n; i++) plyers[i].init();
    plyers.clear();
    
    memset(priz, 0, sizeof(priz));
    scanf("%lf", &sum);
    
    for(int i = 0; i < 70; i++) {
        scanf("%lf", &priz[i]);
        priz[i] = priz[i] / 100.0 * sum;
    }
}

void initPlyer() {
    //scanf("%d", &n);
    cin >> n;
    plyers.resize(n+1);
    
    string str;
    getline(cin, str);
    
    for(int i = 0; i < n; i++) {
        plyers[i].tot = 0;
        getline(cin, str);
        
        plyers[i].name = str.substr(0, 20);
        str = str.substr(20);
        
        if(plyers[i].name.find('*') != string::npos) {
            plyers[i].amat = true;
        }
        
        
        stringstream ss(str);
        //string data;
        // is >> data
        for(int j = 0; j < 4; j++) {
            string data;
            ss >> data;
            
            if(data == "DQ") {
                plyers[i].dq = j;
                break;
            }
            else {
                plyers[i].rnd[j] = str2num(data);
            }
            
            if(j < 2) {
                plyers[i].pre += str2num(data);
            }
            plyers[i].tot += str2num(data);
        }
        // debug("----");
    }
}


bool cmp1(const Player& lhs, const Player& rhs) {
    if(lhs.dq > 1 && rhs.dq > 1) return lhs.pre < rhs.pre;
    return lhs.dq > rhs.dq;
}


int makeCut() {
    sort(plyers.begin(), plyers.begin() + n, cmp1);
    int pos = 0;
    
    while (pos < min(70, n) && plyers[pos].dq > 1) {
        pos++;
    }
    // [0, 69] --> 70
    
    while (plyers[pos].dq > 1 && plyers[pos].pre == plyers[pos-1].pre) {
        pos++;
    }
    
    return pos;
}

// usage: int pos = makeCut
// getRank(pos)


bool cmp2(const Player& lhs, const Player& rhs) {
    if(lhs.dq != rhs.dq) return lhs.dq > rhs.dq;
    if(lhs.tot != rhs.tot) return lhs.tot < rhs.tot;
    return lhs.name < rhs.name;
}

// important!
// difficult: parallel situation
void getRank(int num) {
    //
    sort(plyers.begin(), plyers.begin() + num, cmp2);
    
    // divide money
    // 1. parallel
    // 2. amte cannot get money
    // no amte and rank from [0, 70]
    
    // now: plyers[0...num-1]
    
    
    int k = 0, rkp = 0;
    int rk = 0;
    while(k < num) {
        if(plyers[k].dq < 4) break;
        
        // parallel: [k, p) rank: rk
        
        int p = k, cnt = 0;
        double sum = 0.0;
        
        int prll = 0;
        while(plyers[p].dq == 4 && plyers[p].tot == plyers[k].tot) {
            //
            if(!plyers[p].amat) {
                //
                sum += priz[rkp + cnt];
                cnt++;
                //
            }
            p++;
            prll++;
        }
        
        sum /= cnt;
        
        // assign prize:
        for(int i = k; i < p; i++) {
            plyers[i].rank = rk + 1;
            
            // prize is not enough
            if(rkp > 69) {
                plyers[i].amat = true;
                plyers[i].t = false;
            }
            
            if(!plyers[i].amat) {
                plyers[i].prize = sum;
                plyers[i].t = cnt > 1;
            }
        }
        
        
        
        // [k, p) rank: rk
        // rk [0, 70)
        // [p, ...) rank: rk += cnt
        // plyers[].rank = rk + 1;
        
        k = p;
        rkp += cnt;
        rk += prll;
    }
    
}


void printAns(int num) {
    //
    printf("Player Name          Place     RD1  RD2  RD3  RD4  TOTAL     Money Won\n");
    printf("-----------------------------------------------------------------------\n");
    
    for(int i = 0; i < num; i++) {
        printf("%-21s", plyers[i].name.c_str());
        
        if(plyers[i].dq < 4) printf("          ");
        else {
            char t[5];
            sprintf(t, "%d%c", plyers[i].rank, plyers[i].t ? 'T' : ' ');
            printf("%-10s", t);
        }
        
        for(int j = 0; j < plyers[i].dq; j++) printf("%-5d", plyers[i].rnd[j]);
        for(int j = plyers[i].dq; j < 4; j++) printf("     ");
        
        if(plyers[i].dq < 4) printf("DQ");
        else if(!plyers[i].amat) printf("%-10d", plyers[i].tot);
        else printf("%d", plyers[i].tot);
        
        if(plyers[i].dq < 4 || plyers[i].amat) {
            printf("\n");
            continue;
        }
        
        printf("$%9.2lf\n", plyers[i].prize);
        //int ans = floor((plyers[i].prize + 0.0050001) * 100);
        //plyers[i].prize = ans / 100.0;
        //cout.setf(ios::right);
        //cout << "$" << setw(9) << fixed << setprecision(2) << plyers[i].prize << endl;
        
        //int ans = (int)((plyers[i].prize + 0.0005) * 10000);
        //printf("$%9.2lf\n", ans / 1000.0);
    }
    
}

// attend rnd[3,4], we need plyer.dq > 2


int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int kase;
    scanf("%d", &kase);
    
    while(kase--) {
        
        init();
        // get prize data
        initPlyer();
        
        int num = makeCut();
        getRank(num);
        printAns(num);
        if(kase) printf("\n");
        
    }
}

map和vector联用：邮件接收系统

The Letter Carrier’s Rounds

scanf之后把回车“吃掉”的几种方法
推荐方法：

1
2
3
4
scanf("%d%*c", &kase);
while(kase--) {
    getline(cin, line);
}

MTA

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
//
//  main.cpp
//  MTA
//
//  Created by zhangmin chen on 2019/4/30.
//  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;

void getAddr(const string& str, string& user, string& mta) {
    int k = (int)str.find('@');
    user = str.substr(0, k);
    mta = str.substr(k+1);
}


int main() {
    freopen("input.txt", "r", stdin);
    string str;
    string mta;
    int k;
    string to;
    
    string mtaF, mtaT, userF, userT;
    
    set<string> emails;
    
    while(cin >> str && str[0] != '*') {
        cin >> mta >> k;
        // string to;
        while (k--) {
            // add all address
            cin >> to;
            emails.insert(to + "@" + mta);
        }
    }
    
    // then get all mta
    // for(auto& i : emails) cout << i << endl;
    // for(ssii i = emails.begin(); i != emails.end(); i++) cout << *i << endl;
    
    // we finished all mta input
    
    while(cin >> str && str != "*") {
        getAddr(str, userF, mtaF);
        
        set<string> vis;
        map<string, vector<string> > clents;
        // clents: clients[mtaT] = {usr1, usr2,...}
        
        vector<string> mtaWt;
        
        while(cin >> to && to != "*") {
            // get All mta
            // cout << "dbg: " << to << endl;
            
            //debugS(to);
            
            getAddr(to, userT, mtaT);
            if(vis.count(to)) continue;
            vis.insert(to);
            
            if(!clents.count(mtaT)) {
                mtaWt.push_back(mtaT);
                clents[mtaT] = vector<string>();
            }
            clents[mtaT].push_back(to);
        }
        
        // get all clients
        
        // connection between mtaF --> {mtaWt[0], mtaWt[1]...}
        
        getline(cin, to);
        
        string data;
        while (getline(cin, to) && to[0] != '*') {
            data += "     " + to + "\n";
            // cout << data << endl;
        }
        // cout << data;
        
        // msg finished!
        
        // send msg: mails from str
        // send to:
        // for all mtaWt
        //     vector<stirng> usr = clents[mtaWt[i]]
        //     str -> { usr[0], usr[1]...}
        
        for(int i = 0; i < mtaWt.size(); i++) {
            string mta2 = mtaWt[i];
            vector<string> usrs = clents[mta2];
            
            cout << "Connection between " << mtaF << " and " << mta2 << endl;
            cout << "     HELO " << mtaF << endl;
            cout << "     250\n";
            cout << "     MAIL FROM:<" << str << ">\n";
            cout << "     250\n";
            
            bool canSend = false;
            for(int j = 0; j < usrs.size(); j++) {
                cout << "     RCPT TO:<" << usrs[j] << ">\n";
                if(emails.count(usrs[j])) {
                    canSend = true;
                    cout << "     250\n";
                }
                else cout << "     550\n";
            }
            
            if(canSend) {
                //
                cout << "     DATA\n";
                cout << "     354\n";
                cout << data;
                cout << "     .\n";
                cout << "     250\n";
                
            }
            cout << "     QUIT\n";
            cout << "     221\n";
        }
        
        
        
    
        
        // we get all msg, then close connection
    }
}

坐标的离散化

Urban Elevations

UrbanElevations

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
//
//  main.cpp
//  UrbanElevations
//
//  Created by zhangmin chen on 2019/4/19.
//  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>

using namespace std;
typedef long long llong;

#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)

const int maxn = 100 + 5;
int n;

class Building {
public:
    int id;
    double x, y, w, d, h;
    
    bool operator < (const Building& rhs) const {
        //
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
};

Building blds[maxn];
double xv[maxn*2+1];

bool buiding_exist(int i, double pos) {
    if(blds[i].x <= pos && blds[i].x + blds[i].w >= pos) return true;
    else return false;
}

bool visible(int i, double pos) {
    if(!buiding_exist(i, pos)) return false;
    
    for(int k = 0; k < n; k++) {
        // check other buidings
        if(!buiding_exist(k, pos)) continue;
        
        if(blds[k].y < blds[i].y && blds[k].h >= blds[i].h) return false;
        
    }
    return true;
}

int main() {
    //freopen("input.txt", "r", stdin);
    int kase = 0;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf%lf", &blds[i].x, &blds[i].y, &blds[i].w, &blds[i].d, &blds[i].h);
            xv[i*2] = blds[i].x;
            xv[i*2+1] = blds[i].x + blds[i].w;
            blds[i].id = i+1;
        }
        
        // finished all building data
        sort(blds, blds+n);
        sort(xv, xv+n*2);
        
        int mx = (int)(unique(xv, xv+n*2) - xv);
        // check xv[0...mx]
        
        if(kase++) printf("\n");
        printf("For map #%d, the visible buildings are numbered as follows:\n", kase);
        printf("%d", blds[0].id);
        
        for(int i = 1; i < n; i++) {
            bool ok = false;
            
            for(int k = 0; k < mx-1; k++) {
                // xv[k]
                int avg = (xv[k] + xv[k+1]) / 2;
                if(visible(i, avg)) {
                    ok = true;
                    break;
                }
            }
            
            if(ok) printf(" %d", blds[i].id);
        }
        
        printf("\n");
    }
}