洛谷P1323 删数问题2

题目传送门：https://www.luogu.com.cn/problem/P1323

丑数问题 + P1106 删数问题

时间复杂度：$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
mt19937_64 rng(random_device{}());
void solve() {
    int k, m;
    cin >> k >> m;
    string str;
    {
        vector<int> dp(N, INT_MAX);
        dp[1] = 1;
        str.push_back('1');
        int a = 1, b = 1;
        for (int i = 2; i <= k; ++i) {
            int f1 = dp[a] * 2 + 1;
            int f2 = dp[b] * 4 + 5;
            dp[i] = min(f1, f2);
            if (dp[i] == f1) ++a;
            if (dp[i] == f2) ++b;
            str.append(to_string(dp[i]));
        }
    }
    int n = str.size();
    vector<vector<int>> dp(10);
    vector<int> nxt(n, INT_MAX);
    for (int i = 0; i < n; ++i) {
        dp[str[i] - '0'].push_back(i);
    }
    for (int i = 0; i < 10; ++i)
        reverse(dp[i].begin(), dp[i].end());
    for (int i = 0; i < n; ++i) {
        for (int j = str[i]-'0'+1; j <= 9; ++j){
            auto &vec = dp[j];
            while (vec.size() && vec.back() <= i) vec.pop_back();
            if (vec.size()) nxt[i] = min(nxt[i], vec.back());
        }
    }
    int i = 0;
    vector<bool> del(n);
    while (m && i < n) {
        int cur = nxt[i] - i;
        if (cur <= m) {
            m -= cur;
            for (int j = 0; j < cur; ++j) del[i+j] = 1;
            i = nxt[i];
        } else {
            ++i;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!m) break;
        if (del[i]) continue;
        del[i] = 1;
        --m;
    }
    string ans;
    for (int i = 0; i < n; ++i) {
        if (!del[i]) ans.push_back(str[i]);
    }
    cout << str << '\n';
    cout << ans << '\n';
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}