HDU7101 Time-division Multiplexing（尺取）

目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

有 \(n\) 个字符串，第 \(i\) 次操作，可以将这 \(n\) 个字符串的第 \(i\%|s|\) 个字符依次发送形成一个新的无限长字符串，在这个新字符串上找到最短区间包含这 \(n\) 个字符串上出现的字符，输出这个区间长度

State

\(1<=n<=100\)

\(1<=T<=100\)

\(1<=|s|<=12\)

Input

2
2
abc
bd
2
bab
bbc

Output

4
4

Solution

题意劝退

就像第一组样例一样，可以构造一个字符串 \(ans=ab\ bd\ cb\ ad\ bb\ cd\ (ab)\) ，最小长度的区间为 \(cbad\) ，构造出这个字符串来尺取一下就可以了

\(hint:\) 构造出一个字符串是不够的，\(ans +ans\) 才是正解

Code

    ll n, m, _;
    int i, j, k;
    //ll a[N];
    string s[105];
    int sz[105], p[105];

bool judge()
{
    int ok = 1;
    for(int i = 1; i <= n && ok; i ++){
        if(p[i] >= sz[i]) continue;
        ok = 0;
    }
    for(int i = 1; i < n && ok; i ++){
        if(p[i] % sz[i] == p[i + 1] % sz[i + 1]) continue;
        ok = 0;
    }
    return ok;
}

string go()
{
    string ans = "";
    while(true){
        if(judge()) break;
        for(int i = 1; i <= n; i ++){
            ans += s[i][(p[i] ++) % sz[i]];
        }
    }
    return ans;
}

char vis[30];
signed main()
{
    IOS;
    rush(){
        cin >> n;
        fill(vis, 0);
        rep(i, 1, n){
            cin >> s[i];
            sz[i] = s[i].size();
            p[i] = 0;
            for(int j = 0; s[i][j]; j ++){
                vis[s[i][j] - ‘a‘] = 1;
            }
        }
        string ans = go();
        //dbg(ans);
        ans = ans + ans;
        int len = ans.size();
        int l = 0, r = 0, now = 0, cur = 0, res = 2e9;
        for(int i = 0; i < 26; i ++){
            if(vis[i]) cur ++;
            vis[i] = 0;
        }
        while(true){
            while(r < len && now < cur){
                if(vis[ans[r] - ‘a‘] == 0) now ++;
                vis[ans[r] - ‘a‘] ++;
                r ++;
            }
            if(now < cur) break;
            res = min(res, (r - l));
            if(vis[ans[l] - ‘a‘] == 1) now --;
            vis[ans[l] - ‘a‘] --;
            l ++;
        }
        pd(res);
    }
    //PAUSE;
    return 0;
}