经典题/模型比较多
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
简单题。