解題區/解題區 - 其他題目

2016 Google Code Jam Round 1A

contents

  1. 1. A. The Last Word
  2. 2. B. Rank and File
  3. 3. C. BFFs
  4. 4. Solution
    1. 4.1. A
    2. 4.2. B
    3. 4.3. C

A. The Last Word

每一字串 $S$，可視為一串操作，依序讀入一個字元 $C$，可以選擇把字元 $C$ 插入字串首或尾，請問字典順序最大為何？

類似 ZJ. 一串數字 之類的貪心方式，優先考慮最大字元在哪一個位置，抓取之後拆分兩串分開貪心合併，每一次由後往前找到第一個最大字典順序字元 $T$，$T$ 移到最前方，此時會將字串分成前半 $A$ 和後半 $B$，然而後半 $B$ 要排在 $T$ 字元之後，勢必只能按照順序丟入隊尾。因此 $\textit{MAXEXPR}(F) = T + \textit{MAXEXPR}(A) + B$。

B. Rank and File

給定一個 $N \times N$ 方格，每一行或列都是嚴格遞增，現在給定數個行、數個列的排列情況，請問缺漏的那一行或列的序列為何？

明顯地每一個數字都恰好出現偶數次，按照大小順序印出奇數次數字即可。

C. BFFs

給同學都有一位摯友，給定 $N$ 個人的好友資訊，現在要求盡可能多的人圍成一圈，並且每一個人其中一側是他們自己的摯友，請問圈最多幾個人。

明顯地，若不看方向性，每一個連通圖至多一個環。若一個連通圖式一個環，保證無法與其他方案合併在一起，因此用 $\mathcal{O}(N^2)$ 優先排除是環的解，在其中找最大圈即可。

接著考慮有觸手的水母圖，當水母大小恰好由兩個點構成時才會有解，因為三個點以上不符合題目要求的環。最後找到經過兩端點的最長觸手，這些點可以自我滿足，把所有最長觸手合併在一起可以構成一組特殊解。兩種方案取最大。

Solution

A

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 <bits/stdc++.h>
using namespace std;
string dfs(int n, string s) {
    if (n == 0)	return "";
    char mx = s[0];
    for (int i = 0; i < n; i++)
        mx = max(mx, s[i]);
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == mx) {
            string mm = string(1, mx);
            return mm + dfs(i, s.substr(0, i)) + s.substr(i+1) ;
        }
    }
    return "";
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        char cs[1024];
        scanf("%s", cs);
        int n = strlen(cs);
        string v = dfs(n, cs);
        printf("Case #%d: %s\n", ++cases, v.c_str());
    }
    return 0;
}

B

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, m, x;
        map<int, int> R;
        scanf("%d", &n);
        m = 2*n-1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &x);
                R[x]++;
            }
        }
        printf("Case #%d:", ++cases);
        for (auto e : R) {
            if (e.second % 2 == 1)
                printf(" %d", e.first);
        }
        puts("");
    }
    return 0;
}

C

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
#include <bits/stdc++.h>
using namespace std;
int g[1024][1024];
vector<int> gg[1024];
int cc[1024];
int dfs(int u, int dep) {
    int ret = dep;
    for (auto v : gg[u]) {
        if (cc[v])	continue;
        int tmp = dfs(v, dep+1);
        ret = max(ret, tmp);
    }
    return ret;
}
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int n, A[1024];
        
        memset(g, 0, sizeof(g));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            gg[i].clear();
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), g[i][A[i]] = 1, gg[A[i]].push_back(i);
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            int used[1024] = {};
            int u = i, cnt = 0;
            for (; used[u] == 0; u = A[u]) {
                used[u] = 1, cnt++;
            }
            if (u == i) 
                ret = max(ret, cnt);
        }
        memset(cc, 0, sizeof(cc));
        int cctot = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)	continue;
                if (cc[i] || cc[j])	continue;
                if (g[i][j] == 0 || g[j][i] == 0)
                    continue;
                cc[i] = 1, cc[j] = 1;
                cctot += 2;
                cctot += dfs(i, 0) + dfs(j, 0);
            }
        }
        ret = max(ret, cctot);
        printf("Case #%d: %d\n", ++cases, ret);
    }
    return 0;
}