题解：UVA10705 The Fun Number System

He_Jie · 2025-06-07 20:12:42 · 题解

The Fun Number System

做法的核心是把负数位如果不选的话变为增加，如果选的话不减少。

这样的做法就是减小"0"的标准，让这个数字系统能达到的最小值作为"0"。这样可以让所有能达到的数都是正数，权值变为正数，只是选与不选的方式改变。从高位到低位遍历，就能得到答案。

如果是"Impossible"的话，这种方式下的 n 的值超出了所能表达的范围(0 \sim 2^k - 1)，也就是负数全选的情况到负数位全不选正数位全选。

代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

void solve() {
    ull k, n;
    string s;
    cin >> k >> s >> n;

    vector<ull> cnt(k);
    for (int i = 0; i < k; i ++) {
        if (s[i] == 'p') {
            cnt[i] = (ull)1 << k - i - 1;
        } else {
            cnt[i] = (ull)1 << k - 1 - i;
            n += cnt[i];
        }
    }

    if (n < 0 || ((ull)1 << k) <= n) {
        cout << "Impossible\n";
        return;
    }

    ull res = 0;
    vector<int> ans(k);
    for (int i = 0; i < k; i ++) {
        if (s[i] == 'p') {
            if (res + cnt[i] <= n) {
                res += cnt[i];
                ans[i] = 1;
            }
        } else {
            if (res + cnt[i] <= n) {
                res += cnt[i];
            } else {
                ans[i] = 1;
            }
        }
    }

    for (int i = 0; i < k; i ++) {
        cout << ans[i];
    }
    cout << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t --) {
        solve();
    }

    return 0;
}