TIOJ 2070

Solution of TIOJ 2070 - Special Judge。

Description

給你由小寫英文字母組成的字串$X$，請判斷是不是每一個前$K$個英文字母的子集都是$X$的子序列。

Observation 1

「前$k$個英文字母的『子集』的排列」都是子序列，其實就相當於要你判斷「是否前$k$個英文字母的的排列」都是子序列
（abc的所有排列都是，那a, b, c, ab, ac, bc, abc也當然都會是）。

Observation 2

範圍：$K \le 20$ $\rightarrow$位元DP！

Solution

定義dp[S] = 當狀態為S時，字串所需的最短長度能夠使得滿足題目的要求，當dp[S]為n+1時，表示狀態S無法滿足。
另外定義pos[i][j]表示在位置j往右出現字元i最近的位置，-1表示右邊找不到i。
轉移式：$dp[i + (1 << j)] = max(dp[i + (1 << j)], pos[j][dp[i]]);$
轉移過程中只要有出現了任何一個pos = -1就輸出$No$，否則就輸出$Yes$。

Code

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fastio cin.tie(0); ios_base::sync_with_stdio(false);
#define INF 1e15+9
using namespace std;
const int maxn = 2e5+5;
const int MOD = 1e9+7; // 998244353;
typedef pair<int,int> P;

void solve(){
    int k;
    string s;
    cin >> k >> s;
    char myChar[1005] = {};
    for(int i=1;i<=s.size();i++)
        myChar[i] = s[i-1];
    int pos[50][1001];
    for(int i=0;i<k;i++){
        int curPos = -1;
        for(int j=s.size();j>=0;j--){
            pos[i][j] = curPos;
            if(myChar[j] - 'a' == i)
                curPos = j;
        }
    }
    int S = (1 << k);
    int dp[S+5] = {}; // dp[s] = 狀態s時, 會往右延伸到哪裡, INF表沒辦法
    for(int i=0;i<S;i++){
        for(int j=0;j<k;j++){ // 看看哪些沒在狀態i裡面
            if((i >> j) % 2 == 0){
                int nearest = pos[j][dp[i]];
                if(nearest == -1){
                    cout << "No" << '\n';
                    return;
                }   
                dp[i + (1 << j)] = max(dp[i + (1 << j)], pos[j][dp[i]]);
            }
        }
    }
    cout << "Yes" << '\n';
}

signed main(){fastio
    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }
}

Bonus

這一題的前身是「構造一個最短字串滿足此性質」，此題是一個co-NP-complete的問題
目前能找到的最短且有系統的構造方法如下：

for(int i=1;i<=k * k - 2 * k + 4;i++){
    if(i <= k)
        cout << (char)('a' + i - 1);
    else if(i > k && (i - 2) % (k - 1) == 0)
        cout << 'a';
    else       
        cout << (char)((int)floor((i - 1) * (k - 2) / (k - 1)) % (k - 1) + 2 + 'a' - 1);
}

長度：$k^2 - 2k + 4$