蓝桥杯2022年第十三届决赛真题-最大数字

蓝桥杯2022年第十三届决赛真题-最大数字
时间限制: 2s 内存限制: 320MB 提交: 5703 解决: 1321
题目描述
给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操作：

1. 将该位数字加 1。如果该位数字已经是 9，加 1 之后变成 0。

2. 将该位数字减 1。如果该位数字已经是 0，减 1 之后变成 9。

你现在总共可以执行 1 号操作不超过 A 次，2 号操作不超过 B 次。

请问你最大可以将 N 变成多少？

输入格式
第一行包含 3 个整数：N, A, B。
输出格式
一个整数代表答案。
样例输入复制
123 1 2
样例输出复制
933
提示
对百位数字执行 2 次 2 号操作，对十位数字执行 1 次 1 号操作。

对于 30% 的数据，1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10

对于 100% 的数据，1 ≤ N ≤ 1017; 0 ≤ A, B ≤ 100

1.分析

        1.预处理出所有位数所需加和减的次数。

        2.dfs找出最大的数。

        3.如果加法和减法都无法到9，那么只有加法是可用的。

2.代码

        

#include<iostream>
using namespace std;
typedef long long LL;
const int MAX = 1110;
string s,t;
int a, b;
int add[MAX], del[MAX];
string re="";
void check(int d,int x) {       //预处理add[d] = 9 - x;del[d] = x - 0 + 1;
}
void dfs(int d,int x,int y) {      //dfsif (x==0&&y==0) {            //判断if (re<s||re=="") {re = s;}return;}for (int i = d; i < s.size(); i++) {   //遍历if (s[i] == '9') continue;if (x >0) {if (x > add[i]) {            //可以加到9s[i] = '9';dfs(i + 1, x - add[i], y);s[i] = t[i];}else {                //可以加，但是不能加到9s[i] = t[i] - '0' + x + '0';dfs(i + 1, 0, y);s[i] = t[i];}}if (y >= del[i]){s[i] = '9';dfs(i + 1, x, y - del[i]);s[i] = t[i];}}if (s > re) {         //判断re = s;}
}
int main() {cin >> s >> a >> b;t = s;for (int i = 0; i < s.size(); i++) {check(i, s[i] - '0');}dfs(0,a,b);cout << re << endl;return 0;
}