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

出题人题解

主要知识点

【3】贪心法

解法

显然暴力枚举

b

会超时（只能过前

13

个点），考虑优化。

题目等价于要找到一个最小的

x

，满足

x\ge a

且

x

是一个超级奇数（然后只需输出

b=x-a

）。我们充分发扬人类智慧：

找到 $a$ 中 最高的偶数位，例如对 $a=11\red{4}514$ ，最高的偶数位是 $4$ （已标红）。当然也有可能找不到偶数位，那么这种情况下 $a$ 本身就是一个超级奇数，直接输出 0 即可。
接下来讨论其他情况（ $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$ 。

代码

CPP

#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;
}

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

文章操作

出题人题解

主要知识点

解法

代码

相关推荐

评论

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