CF 1736D Equal Binary Subsequences 題解

1736D.

題敘

有一個 0-1 字串 $s$，你可以選擇一個子序列 $b$，將 $b$ 中的所有元素往右平移最多一格，問操作後是否有可能將其分為兩個不重疊且元素完全相同的子序列 $p, q$

題解

不合法的情況

由於最後需要分成兩個相同的子序列，因此字串中 0 / 1 的數量都必須是偶數，如果是奇數那麼答案就是 -1

構造解

我們可以將子串分為 $n$ 個 pair，每個 pair 分別是 $s_{2i}, s_{2i+1}$，那麼對於每個 pair 有兩種情況：

• 兩個元素相同：
  將這兩個元素各放入 $p, q$ 的尾端

• 兩個元素不相同：

  1. 根據不合法的條件可推得，不相同的 pair 數有偶數個
  2. 兩個元素不相同，代表其中一個元素要反轉

可以發現，若 $b = \{0, 1, 0, 1, ..., 1\}$，那麼將其往右平移一格就等同於將每個元素反轉。

因此，對於每個元素不相等的 pair，我們可在第奇數個選擇 $0$ 放入 $b$，在第偶數個選擇 $1$ 放入 $b$，最後將 $b$ 平移一格之後就能夠將所有 pair 都變成元素相同的了

Code

int n, m;
string s;

void sol() {
    cin >> n;
    cin >> s;
    int cnt = 0;
    int need = 0;
    vector<int> ans;
    for (int i = 0; i < 2 * n; i += 2) {
        if (s[i] != s[i + 1]) {
            cnt++;
            ans.pb(i + 1 + (s[i] - '0' != need));
            need ^= 1;
        }
    }
  
    if (cnt & 1) {
        cout << -1 << endl;
        return;
    }
  
    cout << ans.size() << ' ';
    for (int it: ans)
        cout << it << ' ';
    cout << endl;
  
    for (int i = 1; i <= 2 * n; i += 2)
        cout << i << ' ';
    cout << endl;
}