經典題/模型比較多
John Recommend
經典的Mis`ere Nim問題，參見
Impartial Combinatorial Games.2.5。
非常精巧的一個思路。對于一個至少有2堆都>1的且Nim和非0的狀態，我們按照普通Nim的策略來進行。因為至少有2堆>1，所以一步之內我們仍然至少有1堆>1，又注意到我們留給對手的是一個平衡態，所以我們留給對手的是一個至少2堆>1的平衡態。
這樣進行下去，直到某一步對手給我們的狀態中只有1堆>1（他不可能一口氣把兩個>1的堆都干掉）……
Double Queue簡單題，我用set的。
‘JBC’高精度
Loan Scheduling Recommend一個比較經典的貪心。
對Applications按照deaadline先后來處理。維護當前準備接受的applications列表，如果能完成當前的application則將該application加入列表中。否則和列表中profit最低的比較一下，如果當前application的profit比它高就把它踢掉～。這需要一個heap來維護～。
CODE
1
// Southeastern Europe 2007, Loan Scheduling
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <queue>
8#include <functional>
9#include <algorithm>
10
11using namespace std;
12
13const int MaxN = 10000 + 100000;
14struct Application 
{
15
int profit, deadline;
16
}app[MaxN];
17int n, l;
18
19void init();
20void work();
21bool operator<(const Application& a, const Application& b);
22
23int main() {
24
for (; scanf("%d%d", &n, &l) == 2; ) {
25 init();
26 work();
27
}
28 return 0;
29}
30
31void init() {
32 for (int i = 0; i < n; ++i)
33 scanf("%d%d", &app[i].profit, &app[i].deadline);
34}
35
36void work() {
37 sort(app, app + n);
38 priority_queue<int, vector<int>, greater<int> > q;
39
40 int ans = 0, app_left = 0, pre = -1;
41 for (int i = 0; i < n; ++i) {
42 app_left += (app[i].deadline - pre) * l;
43 if (app_left == 0) {
44 if (q.empty()) continue;
45 int delta = app[i].profit - q.top();
46 if (delta > 0) {
47 ans += delta; q.pop();
48 q.push(app[i].profit);
49 }
50 }
51 else {
52 ans += app[i].profit;
53 q.push(app[i].profit); --app_left;
54 }
55
56 pre = app[i].deadline;
57 }
58 cout << ans << endl;
59}
60
61bool operator<(const Application& a, const Application& b) {
62 return a.deadline < b.deadline;
63}
64
很有意思的一道題……其實說穿了非常簡單……二分出錯的區間，然后計算總count數。由于保證了至多只有一個錯誤，所以根據奇偶性可以判斷是哪半邊錯誤。
CODE
1// Southeastern Europe 2007, Showstopper
2// Written By FreePeter
3
4#include <cstdio>
5#include <cstring>
6#include <iostream>
7#include <algorithm>
8#include <cassert>
9
10using namespace std;
11
12const int MaxN = 10000000;
13struct SeqNode {
14 int x, y, z;
15 int count(int left, int right) {
16 if (left > y) return 0;
17 if (right < x) return 0;
18
19 left >?= x; right <?= y;
20
21 assert(z != 0);
22
23 int p1 = (left - x + z - 1) / z, p2 = (right - x) / z;
24 return p2 - p1 + 1;
25 }
26}seq[MaxN];
27int n;
28
29bool init();
30void work();
31int count_all(int left, int right);
32
33int main() {
34 for (; init(); ) work();
35 return 0;
36}
37
38bool init() {
39 n = 0;
40 char tmp[100];
41 for (; ;) {
42 if (gets(tmp) == NULL) return false;
43 if (sscanf(tmp, "%d%d%d", &seq[n].x, &seq[n].y, &seq[n].z) == 3) break;
44
45 }
46
47 ++n;
48 for (; ;) {
49 if (gets(tmp) == NULL) break;
50 if (strlen(tmp) == 0) break;
51 if (sscanf(tmp, "%d%d%d", &seq[n].x, &seq[n].y, &seq[n].z) != 3) break;
52 ++n;
53 }
54
55 return n > 0;
56}
57
58void work() {
59 int h = seq[0].x, t = seq[0].y;
60 for (int i = 1; i < n; ++i) {
61 h <?= seq[i].x;
62 t >?= seq[i].y;
63 }
64
65 int cc = count_all(h, t);
66
67 if (cc % 2 == 0) {
68 cout << "no corruption" << endl;
69 return;
70 }
71
72 int mid = (h + t) / 2;
73 for (; h < t; mid = (static_cast<long long>(h) + t) / 2) {
74 int cc = count_all(h, mid);
75 if (cc % 2 == 1) t = mid;
76 else h = mid + 1;
77
78 }
79 cout << mid << " " << count_all(mid, mid) << endl;
80}
81
82int count_all(int left, int right) {
83 int ans = 0;
84 for (int i = 0; i < n; ++i)
85 ans += seq[i].count(left, right);
86 return ans;
87}
88
Highway
經典的貪心題，預處理出每個villiage對應的區間，排序，貪心。
Computers
簡單DP, 題目描述有問題，m(y,z)應該指第y年買電腦用到第z年的總maintain費用。
The Stable Marriage Problem Recommended
經典的穩定婚姻問題，參考組合數學書。
Arne Saknussemm
簡單題。