C++:蓝桥杯-22真题-最大数字

自我制定规则无法完全贪心遍历只得92分，
使用dfs深度优先搜索进行贪心遍历

---

---

题目

---

1、自我规则,只得92分，随便看看

代码

思路：
1、把N的各位数取出，先高位后低位，先减后加
通过92分，忽略了个别情况

2、应该采用dfs深度优先搜索贪心

/*
蓝桥杯22决赛真题-最大数字思路：
1、把N的各位数取出，先高位后低位，先减后加
通过92分，忽略了个别情况2、应该采用dfs深度优先搜索贪心
*/#include "bits/stdc++.h"
using namespace std;vector<int> num;        //获取N的各位数,num[0]为个位数
long long N, A, B, ans; //A加，B减//A，加
void process1(int &N)
{if (N == 9){N = 0;}else{N += 1;}
}//B,减
void process2(int &N)
{if (N == 0){N = 9;}else{N -= 1;}
}//获取N的各位数
void getNum(const long long N)
{long long x, y; //x为剔除掉y后的新值，y为获取的各位数x = N;for (int i = 0; i < 17; i++) //最大位数有17位{if (i == 0){num.push_back(N % 10);}if (x < 10) //x只有一位时跳出循环ong double x;{break;}y = (x / 10) % 10;num.push_back(y); //先进低位再进高位x = x / 10;}
}void printNum(vector<int> &num)
{// for (vector<int>::iterator it = num.begin(); it != num.end(); it++)// {//     cout << *it << " ";// }// cout << endl//      << "-------------" << endl;for (int i = num.size() - 1; i >= 0; i--){cout << num[i];}cout << endl;
}//并不是全部遍历考虑到，会出现漏的情况，故为92分
void mySolution()
{//先处理高位在处理低位for (int i = num.size() - 1; i >= 0; i--){if (A == 0 && B == 0){break;}if (num[i] <= 8) //0-8,9不动{//当加和减都能变9时,先加if (num[i] > 5 && B >= (num[i] + 1) && A >= (9 - num[i])){int temp;temp = 9 - num[i]; //次数A = A - temp;while (temp--){process1(num[i]);}}if (B >= (num[i] + 1)) //够减{int temp = num[i] + 1;B = B - temp; //减少B次数while (temp--){process2(num[i]);}}else //不够减，用加{int temp;if (A > (9 - num[i])) //A的次数比加到9还多时{temp = 9 - num[i]; //次数A = A - temp;while (temp--){process1(num[i]);}}else //A的次数刚好到9或者加不到9时,直接用完A{temp = A; //次数A = A - temp;while (temp--){process1(num[i]);}}}}}printNum(num);
}int main(int argc, const char **argv)
{cin >> N >> A >> B;//1操作<=A,2操作<=B,求最大getNum(N);// 一般方法mySolution();return 0;
}

2、dfs贪心方法

代码

//思路：
1、以N的位数nums作为退出条件来获取当前的最大值
2、以跟新完的实际值a作为新的值
3、在加和减的规则下进行dfs深度优先搜索找最大的值

• 重点找到退出dfs递归的条件和进行跟新的变量

/*
蓝桥杯-22决赛真题-最大卡牌-dfs方法//思路：
1、以N的位数nums作为退出条件来获取当前的最大值
2、以跟新完的实际值a作为新的值
3、在加和减的规则下进行dfs深度优先搜索找最大的值
*/#include "bits/stdc++.h"
using namespace std;long long N, A, B; //A加，B减
long long ans = 0;//a当前值大小，nums当前位数，A加数，B减数
void dfs(long long a, long long nums, long long A, long long B)
{if (nums == 0) //变量结束，返回结果{ans = max(ans, a);return;}int d = a / nums % 10; //d为当前位数值//加减规则遍历完if (A > 9 - d) //A够加时{int temp = A - (9 - d);dfs(a + (9 - d) * nums, nums / 10, temp, B);}else //A全加满{dfs(a + nums * A, nums / 10, 0, B);}if (B != 0){if (B >= d + 1) //B够减时{int temp = B - (d + 1);dfs(a - nums * d + nums * 9, nums / 10, A, temp); //够减时，减至9,a值跟新应该为先减到原来改位值，再加上改位*9,即123先变103再变193}}
}
int main(int argc, const char **argv)
{cin >> N >> A >> B;long long a, nums;a = N;nums = 1;//获取N的次方数，N=123时，num =10^3 =1000；while (a){a /= 10;nums *= 10;}dfs(N, nums / 10, A, B); //dfs遍历所有位数，N=123时，nums=100,10,1,一共三次所以nums/10cout << ans << endl;return 0;
}

---

总结

熟悉dfs方法， 重点找到退出dfs递归的条件和进行跟新的变量
参考
https://blog.csdn.net/m0_58177653/article/details/125345906?ops_request_misc=&request_id=&biz_id=102&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AF%E5%8D%A1%E7%89%8C&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-8-125345906.142^v73wechat,201^v4add_ask,239^v2insert_chatgpt&spm=1018.2226.3001.4187#t4