Code Jam Kickstart Round C 2018 题解

发表于 分类于 阅读次数：

A. Planet Distance

一轮 dfs 找出环的所有节点，接着从这些节点 bfs，即可求得距离。时间复杂度为 O(n)。

B. Fairies and Witches

最终选出来的每个 stick 占用两个 node，对于小数据，可选方案里只可能有 3 个 stick，因此三层循环枚举 3 个 stick，判断能否组成凸多边形即可（最长边长度小于其余边长度的和）。
对于大数据，最多 15 个点，可选方案里最多 7 个 stick，dfs 暴力搜索即可，记录 node 的占用状态、最长边长度和总边长（其余边长度的和 = 总边长 - 最长边长度）。

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

const int MAXN = 15 + 2;

int T, n, ans;
int a[MAXN][MAXN];
int b[MAXN][MAXN];

void dfs(int from, int cm, int sume, int maxe) {
    if (sume - maxe > maxe)
        ++ans;
    while (from < n) {
        if (!(cm & (1 << from))) {
            for (int i = 1; i <= b[from][0]; ++i) {
                int to = b[from][i];
                if (!(cm & (1 << to)))
                    dfs(from + 1, cm | (1 << from) | (1 << to), sume + a[from][to], max(maxe, a[from][to]));
            }
        }
        ++from;
    }
}

int main() {
    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        cin >> n;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> a[i][j];
        for (int i = 0; i < n; ++i) {
            b[i][0] = 0;
            for (int j = i + 1; j < n; ++j)
                if (a[i][j] > 0)
                    b[i][++b[i][0]] = j;
        }

        ans = 0;
        dfs(0, 0, 0, 0);
        cout << "Case #" << cs << ": " << ans << endl;
    }

    return 0;
}

C. Kickstart Alarm

数学题，通过整理可以得出：

Answer=∑i=1n∑j=1i∑l=1kAi∗(n−i+1)∗jlAnswer = \sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{l=1}^{k} A_i * (n - i + 1) * j^l

整理一下：

pi=∑j=1kij    si=∑j=1ipip_i = \sum_{j=1}^{k} i^j \text{ }\text{ }\text{ }\text{ } s_i = \sum_{j=1}^{i} p_i

Answer=∑i=1nAi∗(n−i+1)∗siAnswer = \sum_{i=1}^{n} A_i * (n - i + 1) * s_i

其中 pip_i 是等比序列和，因为需要取模，我使用二分来实现，sis_i 随着 i 的递推可以求得，因此总时间复杂度 O(n * log(k))。

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
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

#define randomize srand((unsigned)time(NULL))
#define random(x) ((rand() * (rand() + rand())) % (x))
#define ms(x, y) memset(x, y, sizeof(x))
#define mc(x, y) memcpy(x, y, sizeof(x))

const int MAXN = 1000000 + 10;
const int MOD = 1000000007;

int T, n, k;
int a[MAXN];

int pow(int a, int b) { // a^b
    int ret = 1;
    while (b) {
        if (b & 1)
            ret = (long long) ret * a % MOD;
        a = (long long) a * a % MOD;
        b >>= 1;
    }
    return ret;
}

int sum(int a, int b) { // a^1+a^2+...+a^b
    if (b == 1) return a;
    int ret = (long long) sum(a, b >> 1) * (1 + pow(a, b >> 1)) % MOD;
    if (b & 1) {
        ret += pow(a, b);
        if (ret >= MOD) ret -= MOD;
    }
    return ret;
}

int main() {
    cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        long long x, y, c, d, e1, e2;
        int f;
        cin >> n >> k >> x >> y >> c >> d >> e1 >> e2 >> f;
        a[1] = (x + y) % f;
        for (int i = 2; i <= n; ++i) {
            int _x = (c * x + d * y + e1) % f;
            int _y = (d * x + c * y + e2) % f;
            x = _x;
            y = _y;
            a[i] = (x + y) % f;
        }

        int ans = 0;
        int s = 0; // (1^1+1^2+...+1^k)+(2^1+2^2+...+2^k)+...+(i^1+i^2+...+i^k)
        for (int i = 1; i <= n; ++i) {
            s += sum(i, k);
            if (s >= MOD) s -= MOD;
            ans += ((long long) a[i] * (n - i + 1) % MOD * s) % MOD;
            if (ans >= MOD) ans -= MOD;
        }
        cout << "Case #" << cs << ": " << ans << endl;
    }

    return 0;
}
0%