【題解】ZeroJudge c462: apcs 交錯字串 (Alternating Strings)

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c462
【解題想法】

  • 讀入字串後,把每個小寫字母紀錄為0,把每個大寫字母紀錄為1 (Line-12)。
  • b[ ]:計數連續的 0 或 1 的個數 (Line 15~24)。
  • ans[ ]:掃描 b[ ],判斷可能的連續交錯字串的長度。
    • 遇到 b[ ] 的數字等於 k,cnt++ (Line-29)。
    • 數字不等於 k時,要結算連續交錯字串的長度,如果前一次前一次結算的位置(index = i – cnt – 1)的b[i – cnt – 1] > k,長度加一 (Line-31)。
    • 數字不等於 k,但大於 k 的話,長度加一 (Line-32)。
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int k;
    string s;
    
    cin >> k >> s;
    int a[(int)s.size()];
    for (int i=0; i<s.size(); i++){
        a[i] = ('A' <= s[i] && s[i] <= 'Z');
    }

    int cnt = 1;
    vector<int> b;
    for (int i=1; i<s.size(); i++){
        if (a[i] == a[i-1]) cnt++;
        else{
            b.push_back(cnt);
            cnt = 1;
        }
    }
    b.push_back(cnt);

    cnt = 0;
    vector<int> ans;
    for (int i=0; i<b.size(); i++){
        if (b[i] == k) cnt++;
        else{
            if ((i - cnt - 1) >= 0 && b[i - cnt - 1] > k) cnt++;
            if (b[i] > k) cnt++;
            ans.push_back(cnt);
            cnt = 0;
        }
    }
    if (cnt > 0){
        if (b[b.size() - cnt - 1] > k) cnt++;
        ans.push_back(cnt);
    }
    int mx = 0;
    for (auto i: ans){
        if (i > mx) mx = i;
    }
    cout << mx * k << '\n';

    return 0;
}

while True:
    try:
        k = int(input())
        s = input()
        lst = [1 if c.isupper() else 0 for c in s]
        count = 1
        lst2 = []
        for i in range(1, len(lst)):
            if lst[i] == lst[i-1]:
                count += 1
            else:
                lst2.append(count)
                count = 1
        lst2.append(count)
        lst3 = []
        count = 0
        for i in range(0, len(lst2)):
            if lst2[i] == k:
                count += 1
            else:
                if i-count-1 >= 0:
                    if lst2[i-count-1] > k:
                        count += 1
                if lst2[i] > k:
                    count += 1
                lst3.append(count)
                count = 0
        if count > 0:
            if lst2[i-count] > k:
                count += 1
            lst3.append(count)
        print(max(lst3)*k)
    except:
        break
分享本文 Share with friends