官方試題本

第一題為基本字串題，第二三題基本上都算是實作偏重的題目，第四題是經典binary search題目。

c290: APCS 2017-0304-1秘密差

題目連結

字串的基本操作題

AC 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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    char inp[1111];
    scanf("%s", inp);

    int len = strlen(inp);

    int odd = 0, even = 0;
    for (int i = 0; i < len; i++) {
        if (i % 2 == 0)
            odd += inp[i] - '0';
        else
            even += inp[i] - '0';
    }

    printf("%d\n", abs(odd - even));

    return 0;
}

c291: APCS 2017-0304-2小群體

題目連結

基本上就是找圖上有幾個環，做法非常多種！(我直接DFS)

AC 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

#include <bits/stdc++.h>

using namespace std;

bool seen[55555];
int inp[55555];
void dfs(int i)
{
    if (seen[i])
        return;
    seen[i] = true;

    dfs(inp[i]);
}
int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);

    memset(seen, false, sizeof(seen));
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (seen[i] == false) {
            dfs(i);
            ans++;
        }
    }
    printf("%d\n", ans);

    return 0;
}

c292: APCS2017-0304-3數字龍捲風

題目連結

實作難度不低！

先推出他的步數增加規律，加上發現他只會往右轉的特性，就可以打code啦！

AC 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

#include <bits/stdc++.h>

using namespace std;

const int dx[4] = {0, -1, 0, 1}; // up right down left
const int dy[4] = {-1, 0, 1, 0};

int main()
{
    int n;
    scanf("%d", &n);
    int dir;
    scanf("%d", &dir); // left, up, right, down

    int inp[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &inp[i][j]);

    int step = 1, stepCnt = 0;
    int cnt = 1;
    int x = n / 2, y = n / 2;
    printf("%d", inp[x][y]);
    while (cnt < n * n) {
        for (int i = 0; i < step; i++) {
            x += dx[dir];
            y += dy[dir];
            printf("%d", inp[x][y]);
            cnt++;
            if (i == step)
                break;
            if (cnt == n * n)
                break;
        }

        if (cnt == n * n)
            break;

        stepCnt++;
        if (stepCnt % 2 == 0)
            step++;

        dir++;
        dir %= 4;
    }

    return 0;
}

基地台

(Zerojudge 上沒有)

有個觀察：直徑大於一個數值的話，我們一定可以用 $\leq k$ 的基地台完成覆蓋。

所以說對於 直徑 進行 binary search，我們可以得到最小的直徑使得 $\leq k$ 個基地台下可以完整個覆蓋所有住戶。

結論： Binary search 經典題

AC 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

#include <bits/stdc++.h>

using namespace std;

int n, k;
bool check(int inp[], int mid)
{
    int cnt = 1;
    int right = inp[0] + mid;
    for (int i = 1; i < n; i++) {
        if (inp[i] <= right) {
            continue;
        }
        right = inp[i] + mid;
        cnt++;
    }

    // printf("%d %d\n", mid, cnt);
    return cnt <= k;
}

int main()
{
    scanf("%d %d", &n, &k);

    int inp[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &inp[i]);
    sort(inp, inp + n);

    int l = 0, r = 0x3f3f3f3f;
    while (r - l > 1) {
        int mid = (l + r) / 2;

        // printf("%d %d %d\n", l, mid, r);
        // 0 0 0 0 0 0 1 1 1 1 1 1
        if (check(inp, mid))
            r = mid;
        else
            l = mid;
    }
    printf("%d\n", r);

    return 0;
}