2021中國大學生程式設計競賽（CCPC）- 網絡選拔賽 1002 Time-division Multiplexing

HDU7101 - Time-division Multiplexing

題目連結

題意

給定 n n n​​個字元串 s 1 , s 2 , . . . , s n s_1,s_2,...,s_n s1​,s2​,...,sn​​​，按照一定規則将字元串輸出到 a n s ans ans​中。

一開始所有字元串都按照順序将第 1 1 1​​個字元（即 s [ i ] [ p o s i ] , p o s i = 0 s[i][pos_i],pos_i=0 s[i][posi​],posi​=0​​）輸出到 a n s ans ans​​中：

然後 ∀ i , p o s i = ( p o s i + 1 )   m o d   l e n ( s [ i ] ) \forall i,pos_i = (pos_i+1)\ mod\ len(s[i]) ∀i,posi​=(posi​+1) mod len(s[i])​​​​，将所有字元串的 s [ i ] [ p o s i ] s[i][pos_i] s[i][posi​]​按順序輸出到 a n s ans ans​​​​​，重複這個操作不停止，最後會重複出現同一個字元串 s t r str str（即 a n s = s t r + s t r + . . . + s t r ans=str+str+...+str ans=str+str+...+str）。

動圖好麻煩

思路

這道題題意比較難懂，但是題目并不難。

先将輸出串中的重複串 s t r str str提取出來：

可以記錄一個數組 p o s i pos_i posi​，除了一開始的情況，直到 ∀ i , p o s i = = 0 \forall i, pos_i==0 ∀i,posi​==0​​時就停止記錄，這時候的輸出串就是重複串 s t r str str。

然後去找最小範圍的 [ l , r ] [l,r] [l,r]使得包含 s t r str str​中所有不同的字元，這是一個經典的問題了（雙指針）。

!!

有一點需要注意一下，取得的最小範圍不一定在 s t r str str能，可能在 s t r + s t r str+str str+str上，是以需要将 s t r = s t r + s t r str=str+str str=str+str.

AC的代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 100;

char s[N][20];
int pos[N], n;
bool k = true;

bool check() {
    if (k) {
        k = false;
        return false;
    }

    for (int i = 1; i <= n; i++)
        if (pos[i] != 0) return false;

    return true;
}

int solve(string str) {
    int res = str.size();
    int E[30];
    for (int i = 0; i < 26; i++) E[i] = 0;

    // =========================================
    int all = 0;  // 記錄有多少個不同的字元
    for (int i = 0; i < str.size(); i++) {
        int tmp = str[i] - 'a';
        if (E[tmp] == 0) all++;
        E[tmp]++;
    }
    for (int i = 0; i < 26; i++) E[i] = 0;
    // =========================================
    int l = 0, r = 0;  // 雙指針
    int cnt = 0;
    while (l < str.size() && r < str.size()) {
        while (cnt < all && r < str.size()) {  // 直到所有不同字元都都包含時停下
            int tmp = str[r] - 'a';
            if (E[tmp] == 0) cnt++;

            E[tmp]++;
            r++;
        }
        bool key = false;
        if (cnt >= all)  // 隻有l-r能取到所有不同字元時才記錄答案
            key = true;
        else
            break;

        while (l < r && cnt >= all) {  // 恰好不滿足
            int tmp = str[l] - 'a';
            E[tmp]--;
            if (E[tmp] == 0) cnt--;

            l++;
        }

        if (key) res = min(res, (r - l + 1));
    }

    return res;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        string str = "";
        for (int i = 1; i <= n; i++) cin >> s[i];

        memset(pos, 0, sizeof pos);
        k = true;
        while (!check()) {  // 尋找重複出現的"輸出串"
            for (int i = 1; i <= n; i++) {
                str += s[i][pos[i]];

                pos[i] = (pos[i] + 1) % strlen(s[i]);
            }
        }
        str += str;
        cout << solve(str) << endl;
    }

    return 0;
}