题解 | 小红的双生数

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> find(const string& s) {
    int n = s.length();
    vector<int> ans;

    if (n % 2 == 1) { // 奇数长度
        ans.resize(n + 1, 0);
        for (int i = 1; i <= n; i += 2) {
            int val = ((i / 2) & 1) ^ 1;
            ans[i] = ans[i - 1] = val;
        }
    } else { // 偶数长度
        ans.resize(n, 0);
        for (int i = 1; i < n; i += 2) {
            int a = s[i - 1] - '0';
            int b = s[i] - '0';
            if (a == b) {
                ans[i] = ans[i - 1] = a;
            } else {
                int target = a * 10 + b;
                for (int j = 0; j < 10; j++) {
                    if (j * 11 >= target) {
                        ans[i] = ans[i - 1] = j;
                        break;
                    }
                }
                int k = 0;
                for (int j = i + 2; j < n; j += 2) {
                    ans[j] = ans[j - 1] = k;
                    k ^= 1;
                }
                break;
            }
        }

        for (int i = 2; i < n; i += 2) {
            if (ans[i] == ans[i - 1]) {
                bool found = false;
                for (int j = i + 1; j >= 0; j -= 2) {
                    ans[j] += 1;
                    ans[j - 1] += 1;
                    if (j > 2 && ans[j] == ans[j - 2]) {
                        ans[j] += 1;
                        ans[j - 1] += 1;
                    }
                    if (ans[j] < 10) {
                        found = true;
                        int k = 0;
                        for (int p = j + 2; p < n; p += 2) {
                            ans[p] = ans[p - 1] = k;
                            k ^= 1;
                        }
                        break;
                    }
                }
                if (!found) {
                    ans.resize(n + 2, 0);
                    for (int j = 1; j <= n + 1; j += 2) {
                        int val = ((j / 2) & 1) ^ 1;
                        ans[j] = ans[j - 1] = val;
                    }
                    return ans;
                }
            }
        }
    }
    return ans;
}

int main() {
    string x;
    cin >> x;
    vector<int> result = find(x);
    for (int num : result) {
        cout << num;
    }
    cout << endl;
    return 0;
}