TIOJ 2070：Special Judge

TIOJ 2070：Special Judge

題目大意：給一個字串 $X$，問由 $`a'\sim `a'+k-1$ 組成長度為 $k$ 字串的所有子集是否皆為 $X$ 的子序列。子集就是刪任意個字元，任意排列出來，子序列就是可以刪任意個字元，保持相對位置。

解法：$O(26\times |X|+k\times 2^k)$ 的作法。可以用一個陣列 $suf[26][|X|+2]$，$suf[j][i]$ 代表現在的字母為 $j$，在字串中的位置為 $i$，在 $i$ 以後第一個出現 $j$ 的位置。之後由 $0$ 枚舉到 $2^k-1$，假設現在數字為 $i$，$i$ 的二進制裡有 $1$ 的位元，則代表此字串可以找出這些位元所有排列，$last[i]$ 代表這些排列裡最後一個字元出現位置的最大值，之後要向還沒找到的字母拓展，可以找到這些字母位置大於 $last[i]$，又最接近 $last[i]$ 的位置，也就是 $suf[j][last[i]+1]$，如果找不到，代表找不到這種排列，那就輸出 $\text{No}$，否則將 $last[i+2^j]$ 調為自己與 $suf[j][last[i]+1]$ 的最大值。至於如何拿到 $\text{Topcoder}$，可以知道這題跟 "位元" 很有關係，可以朝 "位元" 的方向去想。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back

const int INF = 1e9;

int last[1 << 20];

void solve() {
    int k, n;
    string s;
    cin >> k >> s;
    n = s.size(), s = " " + s;
    int suf[26][n + 2];
    FOR (i, 0, 25) suf[i][n + 1] = INF;
    for (int i = n; i >= 1; i--) {
        FOR (j, 0, 25) suf[j][i] = suf[j][i + 1];
        suf[s[i] - 'a'][i] = i;
    }
    fill (last, last + (1 << k), 0);
    for (int i = 0, I = 1 << k; i < I; i++) {
        for (int j = 0; j < k; j++) {
            if ( (i >> j) & 1)
                continue;
            int m = i ^ (1 << j), p = suf[j][last[i] + 1];
            if (p == INF) {
                cout << "No\n";
                return;
            }
            last[m] = max (last[m], p);
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！