2017 ICPC Beijing

Posted on | In

达成成就： 铁牌首名。

E - Cats and Fish(00:29)

签到题， 模拟， 一顿瞎搞就好。

Code:

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

int c[105], cnt[105], eating[105];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int m, n, x;
    while (cin >> m >> n >> x) {
        for (int i = 0; i < n; i++) {
            cin >> c[i];
            cnt[i] = 0; eating[i] = 0;
        }
        sort(c, c + n);
        for (int i = 1; i <= x; i++) {
            for (int j = 0; j < n; j++) {
                if (eating[j]) {
                    cnt[j]++;
                }
                else if (m > 0) {
                    cnt[j] = 1, eating[j] = 1, m--;
                }
            }
            for (int j = 0; j < n; j++) {
                if (cnt[j] == c[j]) {
                    cnt[j] = 0;
                    eating[j] = 0;
                }
            }
        }
        int ing = 0;
        for (int j = 0; j < n; j++) {
            ing += eating[j];
        }
        cout << m << " " << ing << endl;
    }
}

F - Secret Poems(00:52)

签到题 * 2， 模拟 * 2， 瞎搞就好 * 2, WA了两发导致罚时boom。

Code:

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

const int Move[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

char s[105][105], str[10005], ans[105][105];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                for (int j = 0, k = i; k >= 0; j++, k--) {
                    str[cnt++] = s[k][j];
                }
            }
            else {
                for (int j = i, k = 0; k <= i; j--, k++) {
                    str[cnt++] = s[k][j];
                }
            }
        }
        for (int i = 1; i < n; i++) {
            bool flag = (n & 1) ^ (i % 2 == 0) ^ 1;
            if (flag) {
                for (int j = i, k = n - 1; j < n; j++, k--) {
                    str[cnt++] = s[k][j];
                }
            }
            else {
                for (int j = n - 1, k = i; k < n; j--, k++) {
                    str[cnt++] = s[k][j];
                }
            }
        }
        str[cnt] = 0;
        memset(ans, 0, sizeof ans);
        for (int pos = 0, i = 0, j = -1; ; ) {
            do {
                ++j;
                if (pos == cnt) break;
                ans[i][j] = str[pos++];
            } while (j < n - 1 && ans[i][j + 1] == 0);
            if (pos == cnt) break;

            do {
                ++i;
                if (pos == cnt) break;
                ans[i][j] = str[pos++];
            } while (i < n - 1 && ans[i + 1][j] == 0);
            if (pos == cnt) break;

            do {
                --j;
                if (pos == cnt) break;
                ans[i][j] = str[pos++];
            } while (j > 0 && ans[i][j - 1] == 0);
            if (pos == cnt) break;

            do {
                --i;
                if (pos == cnt) break;
                ans[i][j] = str[pos++];
            } while (i > 0 && ans[i - 1][j] == 0);
            if (pos == cnt) break;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << ans[i][j];
            }
            cout << endl;
        }
    }
}

J - Pangu and Stones(Upsolved)

题意： 需要将所有石子合并成一堆，每次只能合并连续的[L, R]堆，求最小合并费用or不能。

Solution:

区间DP，大概就是模版题的升级版。然而我并不会区间DP= =
转移方程大概为:
$dp[i][j][k] = \min ( dp[i][t][1] + dp[t + 1][j][k - 1] ), i \leq t < j, k != 1$
$dp[i][j][1] = \min ( dp[i][j][t] ), l \leq t \leq r$
$dp[i][i][0] = 0$

Code:

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, L, R;
long long a[105], sum[105], dp[105][105][105];

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (cin >> n >> L >> R) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i <= n; i++) {
            dp[i][i][1] = 0;
            sum[i] = sum[i - 1] + a[i];
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i <= n; i++) {
                int j = i + len - 1;
                if (j > n) break;
                for (int k = len; k >= 2; k--) {
                    for (int t = i; t < j; t++) {
                        dp[i][j][k] = min(dp[i][j][k], dp[i][t][1] + dp[t + 1][j][k - 1]);
                    }
                }
                for (int t = L; t <= R; t++) {
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j][t] + sum[j] - sum[i - 1]);
                }
            }
        }
        if (dp[1][n][1] != INF) cout << dp[1][n][1] << endl;
        else cout << 0 << endl;
    }
}