題目： UVa - 1746 - String Theory

題目說明

給一些整數表示括號的個數，求最大的 k 值。

k-quotation 的定義為:

  • 若 k = 1，表示字串頭尾各有一個 ' 號，而中間沒有任何 ' 號。
  • 若 k >= 2，表示字串頭尾各有 k 個 ' 號，而中間是 k-1-quotation。

如 ''All 'work' and no 'play'''，最外層的 ' 號為 2 個，而中間的字串為 1 個，則 k = 2。

解釋的不是很好，可能看題目原文會比較好理解。

For k > 1, a k-quotation is a string that begins with k quote characters, ends with another k quote characters and contains a nested string in-between. The nested string is a non-empty sequence of (k − 1)-quotations, which may be preceded, separated, and/or succeeded by any number of non-quote characters. For example, ‘’All ‘work’ and no ‘play’’’ is a 2-quotation.

1746.pdf

Input： 每組測資第一個整數 N，表示有 N 個整數，依序為 a1, a2, ..., aN，表示字串的開頭為 a1 個 ' 號，後面接著一些正整數個非 ' 號的字元，接著 a2 個 ' 號，後面接著一些正整數個非 ' 號的字元，…，直到最後為 aN 個 ' 號結尾。

需要注意的是，若 N = 1，表示 a1 就是 aN，應該是只有 ' 號的意思，或是前面可能有一些非 ' 號的字元，後面接 ' 號，不太確定，題目看不是很懂。

Output： 求最大的 k 值為何，若找不到則輸出 "no quotation"，注意 k >= 1。

解題思路

暴力法，找出可能的 k 值，並減去 ' 號的個數，模擬將 ' 號分組，當做到最後一層時，判斷剩下的 ' 號是否是偶數個，若為偶數個才可以一一配對，若不是則不符合。

需要注意的是:

  • k 的最大值為 a1 及 aN 兩者的較小者，因為字串頭尾都必須有 k 個 ' 號。
  • 若 k = 1，則最後剩下的 ' 號個數需為 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
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fqz3Sx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int N;
int quotes[101]; // 題目給的測資
int dummy[101];  // 用來模擬的陣列

void read()
{
    for (int i = 0; i < N; ++i) cin >> quotes[i];
}

void solve()
{
    // 模擬 k，暴力法檢查 k 是否可行
    for (int k = min(quotes[0], quotes[N - 1]); k > 0; --k)
    {
        memcpy(dummy, quotes, N * sizeof(int));
        int l = 0, r = N - 1, tmp = k;

        while (l < N && r >= 0 && dummy[l] >= tmp && dummy[r] >= tmp)
        {
            if ((dummy[l] -= tmp) == 0) ++l;
            if ((dummy[r] -= tmp) == 0) --r;

            if (--tmp > 0) continue;
            
            auto sum = accumulate(dummy, dummy + N, 0);
            if (sum % 2 == 0 && k != 1 || sum == 0 && k == 1) cout << k << '\n';
            else cout << "no quotation\n";
            return;
        }
    }
}

int main()
{
    while (cin >> N)
    {
        read();
        solve();
    }
}

參考資料

1746.pdf
uva1746