【MGVOI R1-A】超级奇数 题解

FruitWasTaken · 2025-07-27 18:04:24 · 题解

出题人题解

主要知识点

• 【3】贪心法

解法

显然暴力枚举 b 会超时（只能过前 13 个点），考虑优化。

题目等价于要找到一个最小的 x，满足 x\ge a 且 x 是一个超级奇数（然后只需输出 b=x-a）。我们充分发扬人类智慧：

1. 找到 a 中 最高的偶数位，例如对 a=11\red{4}514，最高的偶数位是 4（已标红）。当然也有可能找不到偶数位，那么这种情况下 a 本身就是一个超级奇数，直接输出 0 即可。

2. 接下来讨论其他情况（a 不是超级奇数）：实际上最优的构造是把 a 最高的偶数位加上 1（在这之后它变为奇数数码），然后贪心地把所有更低位的数码全部变成 1，就能得到最小的 x，例如 a=11\red{4}\orange{514} \rightarrow x=11\red{5}\orange{111}。

• 显然，这样构造满足 x > a，并且 x 是一个超级奇数。

• 不可能有满足条件的更小的 x 了，因为它至少要将 a 中最高的偶数数码替换成奇数数码，在这之后，将所有低位数码变成 1 显然会最小化 x。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

string a, b;

int turn(string s) //将数字字符串转换为 int 格式
{
    int x = 0;
    for (int i = 0; i < s.length(); i++)
    {
        x *= 10; 
        x += s[i] - '0';
    }

    return x;
}

void solve()
{
    cin >> a;

    bool flag = false;
    b = a;
    for (int i = 0; i < a.length(); i++)
    {
        if (flag) 
        {
            b[i] = '1'; //若已经找到了最高的偶数位，直接将低位置为 1
        }
        else if ((a[i] - '0') % 2 == 0) //找到了最高的偶数位
        {
            b[i]++;
            flag = true; //标记
        }
    }

    cout << turn(b) - turn(a) << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int _;  
    cin >> _;
    while (_--)
    {
        solve();
    }

    return 0;
}