今天晚上要在电信楼 203 讲 USACO Section 1.5, 解题报告先发到这里吧。

幻灯片在文章的最后提供下载，为了加大文章的篇幅，就……就把代码粘在这里……

译题可以在 http://www.wzoi.org/usaco/ 找到。还有，幻灯片中的 Checker Challenge 题目中的图片引用自 Matrix67 大牛的博客。

Number Triangles

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const size_t N = 1111;
int mat[N][N], res[N][N];
int main() {
    freopen("numtri.in", "r", stdin);
    freopen("numtri.out", "w", stdout);
    memset(mat, 0, sizeof(mat));
    memset(res, 0, sizeof(res));
    size_t n; cin >> n;
    for (size_t i = 1; i <= n; ++i)
        for (size_t j = 1; j <=i; ++j)
            cin >> mat[i][j];
    for (size_t i = 1; i <= n; ++i)
        for (size_t j = 1; j <=i; ++j)
            res[i][j] = max(res[i-1][j], res[i-1][j-1]) + mat[i][j];
    int m = 0;
    for (size_t i = 1; i <= n; ++i)
        m = max(m, res[n][i]);
    cout << m << endl;
    return 0;
}

Prime Palindromes

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
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
inline bool isprime(int a) {
    if (a < 2) return false;
    if (a == 2) return true;
    int t = (int)sqrt(double(a));
    for (int i = 2; i <= t; ++i)
        if (!(a % i)) return false;
    return true;
}
inline void generate_palindromes(vector<int> &vec) {
    vec.push_back(2); vec.push_back(5);
    const int avail[4] = {1, 3, 7, 9};
    for (int i = 0; i < 4; ++i) {
        int a = avail[i];
        vec.push_back(a); // a
        vec.push_back(10*a + a); // aa
        for (int b = 0; b <= 9; ++b) {
            vec.push_back(100*a + 10*b + a); // aba
            vec.push_back(1000*a + 100*b + 10*b + a); // abba
            for (int c = 0; c <= 9; ++c) {
                vec.push_back(10000*a + 1000*b + 100*c + 10*b + a); // abcba
                vec.push_back(100000*a + 10000*b + 1000*c
                        + 100*c + 10*b + a); // abccba
                for (int d = 0; d <= 9; ++d) {
                    vec.push_back(1000000*a + 100000*b + 10000*c
                            + 1000*d + 100*c + 10*b + a); // abcdcba
                    vec.push_back(10000000*a + 1000000*b + 100000*c + 10000*d
                            + 1000*d + 100*c + 10*b + a); // abcddcba
                }
            }
        }
    }
    sort(vec.begin(), vec.end());
}
int main() {
    freopen("pprime.in", "r", stdin);
    freopen("pprime.out", "w", stdout);
    vector<int> arr; arr.reserve(9999);
    generate_palindromes(arr);
    int a, b; cin >> a >> b;
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] < a) continue;
        if (arr[i] > b) break;
        if (isprime(arr[i]))
            cout << arr[i] << endl;
    }
    return 0;
}

Superprime Rib

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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n = 0, x = 0;
inline bool isprime(int a) {
    if (a < 2) return false;
    if (a == 2) return true;
    int t = (int)sqrt(double(a));
    for (int i = 2; i <= t; ++i)
        if (!(a % i)) return false;
    return true;
}
void recursive(int depth) {
    if (depth >= n) {
        cout << x << endl;
        return;
    }
    for (int i = 0; i <= 9; ++i) {
        x = x * 10 + i;
        if (isprime(x))
            recursive(depth + 1);
        x = x / 10;
    }
}
int main() {
    freopen("sprime.in", "r", stdin);
    freopen("sprime.out", "w", stdout);
    cin >> n; recursive(0);
    return 0;
}

Checker Challenge

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 50;
bool hor[N], ver[N], sla[N<<1], bsl[N<<1];
int n, r = 0, c = 0, mask, seq[N];
inline int slai(int r, int c) {
    return r + c - 1;
}
inline int bsli(int r, int c) {
    return r - c + n;
}
inline void printseq() {
    cout << seq[1];
    for (int i = 2; i <= n; ++i)
        cout << ' ' << seq[i];
    cout << endl;
}
bool recursive(int row = 1) {
    if (row > n) {
        if (c++ < 3) printseq();
        else return true;
        return false;
    }
    for (int col = 1; col <= n; ++col) {
        int slain = slai(row, col), bslin = bsli(row, col);
        if (ver[col] || sla[slain] || bsl[bslin])
            continue;
        ver[col] = true; sla[slain] = true; bsl[bslin] = true;
        seq[row] = col; if (recursive(row + 1)) return true;
        ver[col] = false; sla[slain] = false; bsl[bslin] = false;
    }
    return false;
}
void count(int c, int x, int y) {
    int lowbit, available;
    if (c != mask) {
        available = mask & (~(c | x | y));
        while (available) {
            lowbit = available & (-available);
            available -= lowbit;
            count(c + lowbit, (x + lowbit) << 1, (y + lowbit) >> 1);
        }
    } else ++r;
}
int main() {
    freopen("checker.in", "r", stdin);
    freopen("checker.out", "w", stdout);
    cin >> n; recursive();
    mask = (1 << n) - 1; count(0, 0, 0);
    cout << r << endl;
    return 0;
}

幻灯片下载地址：http://uploads.euyuil.com/2011/11/USACO-Section-1.5.ppsx

原创文章，转载请注明来源：http://euyuil.com/2969/usaco-section-1-5-solutions/