Solution Idea

50000. Alternating Sequence

題目概要

找一段連續序列,連續的序列要滿足正負正負的交錯關係,每一段正、負都要恰好 $K$ 個元素,要求序列正開頭、正結尾,同時至少一個負片段,請問符合上述規則的最長序列長度為何?

解法概要

  • 首先,不考慮恰好 $K$ 個元素,先考慮 $K = 1$ 的情況,則長度小於 3 的情況直接輸出 0。
  • 次要,連續 $K$ 的元素的條件考慮進來,則要簡化到 $K = 1$ 的想法解決。
  • 最後,捨棄掉多餘的儲存空間。

30 pt.

只考慮 $K = 1$ 的情況。

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
#include <stdio.h>
 
int main() {
    int res = 0;         // 記錄答案
    int sign = -1;         // 表示上一個數字的正負號 1 表示正數 -1 表示負數
    int length = 0;     // 表示到目前為止找到的 「正負正負」序列有多長
    int x;
    while (scanf("%d", &x)) {
        if (x == 0) break;     // 結束條件
 
        // 計算序列長度
        if (x > 0) {        // 若新加入的元素為正
            if (sign == -1)    // 前一個元素為負,表示序列長度可以增加 +...-+
                length += 1;
            else            // 前一個元素為正,x 為序列的開頭 +
                length = 1;
            sign = 1;        // 更新前一個元素的正負號
        }
        else if (x < 0) {    // 若新加入的元素為負
            if (sign == 1)    // 前一個元素為正,表示序列長度可以增加 +...+-
                length += 1;
            else            // 前一個元素為負,序列長度歸 0
                length = 0;
            sign = -1;        // 更新前一個元素的正負號
        }
 
        // 更新答案,由於正開頭正結尾,保證 length 一定是奇數,並且長度一定大於等於 3。
        if (length > res && length > 1 && length%2==1) {
            res = length;
        }
    }
    printf("%d\n", res);
    return 0;
}

40 pt.

假設想不到完美的解法使用空間複雜度 $O(1)$、時間複雜度 $O(N)$,則還有一個窮舉的解法,空間複雜度 $O(N)$ 且時間複雜度 $O(N^2)$。

  • 先把所有數字讀進陣列中
  • 接著窮舉序列的開頭位置 pos
  • 對於每一個開頭位置,嘗試往後統計連續 $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
#include <stdio.h>
#include <stdlib.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define MAXN 1000005
int A[MAXN];
int main() {
    int N, K;
    while (scanf("%d", &K) == 1) {
        N = 0;
        while (scanf("%d", &A[N]) == 1 && A[N])    // 將所有輸入讀進陣列中
            N++;
        int ret = 0;                            // 紀錄答案
        for (int i = 0; i < N; i++) {            // 窮舉序列的開頭
            if (A[i] > 0) {                        // 一定要正開頭
                int alt = 1, seg = 0, j = i;   
                // alt 表示正負交換的狀態, seg 表示有多少連續的正負,j 為移動的位置
                while (j < N && A[j]) {
                    if (alt == 1) {                // 當前要讀連續 K 個正
                        int cnt = 0;
                        for (; j < N && A[j] > 0; j++)
                            cnt++;
                        if (cnt >= K) {            // 這一段是否連續 K 個以上
                            if (seg+1 >= 3)
                                ret = max(ret, seg+1);
                        } else {                // 少於 K 個,則不必繼續窮舉
                            break;
                        }
                        if (cnt > K)            // 多於 K 個也不能繼續串出更長的,則不必窮舉。
                            break;
                        seg++;                    // 恰好 K 個,則繼續窮舉
                    } else {                    // 當前要讀連續 K 個負
                        int cnt = 0;
                        for (; j < N && A[j] < 0; j++)
                            cnt++;
                        if (cnt != K)            //  只有連續 K 個負才能繼續,反之結束窮舉。
                            break;
                        seg++;       
                    }
                    alt = -alt;                    // 讀連續 K 個正要變成讀連續 K 個負,反之亦然。
                }
            }
        }
        printf("%d\n", ret*K);
    }
    return 0;
}

100 pt.

當要使用 $O(1)$ 的空間複雜度,又要滿足 $O(N)$ 的時間複雜度,要引入一點狀態自動機的概念。

首先,題目要求有正和負、連續 K 個以及序列長度 (若將連續 K 個當作一個片段,則可以計算片段數),根據上述三個情況,則可以定義 3 個變數當作一個狀態 state(sign, count, #segment)。

假設當前狀態為 state(sign, count, #segment)

State table

當前狀態\新加入的元素 + - zero
$\text{state}(+, k, 0), \; 0 \le k \lt K$ $\text{state}(+, k+1, 0)$ $\text{state}(-, 0, 0)$ $\text{state}(0, 0, 0)$

表格略為複雜,嘗試用口語把程式的 if else 用人說的話描述意思,想必不難理解。

最早規劃出的題目中序列中帶有 0 的存在,意即要以 0 作為分割區段的依據進行判斷,之後改成序列中只有正和負兩種情況,所以才導致下面過於複雜的判斷。

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
#include <stdio.h>
#include <stdlib.h>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
int now_c, now_f, seg, ret;
int N, K;
void update(int x) {
    if (x > 0) {
        if (now_f == 1) {
            now_c++;
        } else if (now_f == -1) {
            // ----/++++
            //      ^
            if (now_c > K) {
                seg = 0, now_c = 1, now_f = 1;
            } else if (now_c < K) {
                seg = 0, now_c = 1, now_f = 1;
            } else {
                seg++, now_c = 1, now_f = 1;
            }
        } else {
            // 0000/++++
            //      ^
            seg = 0, now_c = 1, now_f = 1;
        }
    } else if (x < 0) {
        if (now_f == -1) {
            now_c++;
        } else if (now_f == 1) {
            // ++++/----
            //      ^
            if (now_c > K) {
                if (seg+1 >= 3)    ret = max(ret, seg+1);
                seg = 1, now_c = 1, now_f = -1;
            } else if (now_c < K) {
                seg = -0x3f3f3f3f, now_c = 1, now_f = -1;
            } else {
                if (seg < 0)    seg = 0;
                if (seg+1 >= 3)    ret = max(ret, seg+1);
                seg++, now_c = 1, now_f = -1;
            }
        } else {
            // 0000/----
            //      ^
            seg = -0x3f3f3f3f, now_c = 1, now_f = -1;
        }
    } else {
        if (now_f == 0) {
            now_c++;
        } else if (now_f == 1) {
            // ++++/0000
            //    ^
            if (now_c >= K) {
                if (seg+1 >= 3)    ret = max(ret, seg+1);
                seg = -0x3f3f3f3f, now_c = 1, now_f = 0;
            } else {
                seg = -0x3f3f3f3f, now_c = 1, now_f = 0;
            }
            seg = -0x3f3f3f3f, now_c = 1, now_f = 0;
        } else {
            // ----/0000
            //    ^
            seg = -0x3f3f3f3f, now_c = 1, now_f = 0;
        }
    }
}
int main() {
    int x;
    while (scanf("%d", &K) == 1) {
        now_c = 0, now_f = 0, seg = 0, ret = 0;
        while (scanf("%d", &x) == 1 && x)
            update(x);
        update(0);
        printf("%d\n", ret*K);
    }
    return 0;
}

點評

Morris 覺得略難,這題牽扯到演算法思路,雖然只用 if else for 可以解決,但對於剛學程式不久的同學會深感害怕與無助。同學若第一次考這種類型的考試,要把握如何騙分,不急著鑽完美 100 分的寫法。

所謂的騙分意即在考試規則中,知道部分給分的條件,嘗試用特別判斷某些情況的程式碼輸出正確答案,但未必是正確作法,由於測資通常無法設計成一個測資可以測試所有情況,也就是說一個測資會經過的判斷數有限,覆蓋程式碼片段率無法達到 100%,因此使用多筆測資來測試程式碼的完整性。了解上述特性,部分得分就可以成立。請不要連輸入都不讀就直接輸出答案,舉止被發現會造成評分上的尷尬。

作者

rilak, Morris

Discussion