题山采玉：Day3
嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记 闲言碎语小记坊 题山采玉 领略算法真谛
今天的题全来自蓝桥杯国赛的题
2022P8803 [蓝桥杯 2022 国 B] 费用报销 - 洛谷
P8801 [蓝桥杯 2022 国 B] 最大数字 - 洛谷
出差
2022
签到题
#include <iostream>
using namespace std;
int main()
{cout << "A C" << endl;cout << "A D" << endl;cout << "B D" << endl;return 0;
}
这道题就是一道01背包题，本次2022国赛有几道01背包的题目。
我们将2022看成1到2022个数，在里面选10个数，题目问加起来等于2022的方案数有多少个，我们来定义状态表示：
f[i][j][k]表示，从前i个数里面挑j个数其中和恰好等于k的个数
状态转移方程
选i位置 f[i][j][k] += f[i-1][j -1][k - i];
不选i位置 f[i][j][k] += f[i-1][j][k];
初始化将f[0][0][0] = 1；
填表顺序从上到下，从左到右。
最后结果：f[2022][10][2022]
#include <iostream>using namespace std;
typedef long long LL;
LL f[2023][11][2023];
int main()
{f[0][0][0] = 1;for (int i = 1; i <= 2022; i++){for (int j = 0; j <= 10; j++){for (int k = 0; k <= 2022; k++){f[i][j][k] += f[i - 1][j][k];if (j >= 1 && k >= i) f[i][j][k] += f[i - 1][j - 1][k - i];}}}cout << f[2022][10][2022] << endl;return 0;
}我们进行一下空间优化
#include <iostream>using namespace std;
typedef long long LL;
LL f[11][2023];
int main()
{f[0][0] = 1;for (int i = 1; i <= 2022; i++)for (int j = 0; j <= 10; j++)for (int k = 0; k <= 2022; k++)if (j >= 1 && k >= i) f[j][k] += f[j - 1][k - i];cout << f[10][2022] << endl;return 0;
}
我们设最多能凑出y套卡牌
能使用最多m张空白卡牌
当我们使用的空白卡牌数越多，我们能凑出的卡牌套数就越多
明显的二段性
当y = mid时，算出的ret > m 时 r = mid - 1
当ret <= m时里面可以存在答案所以l = mid
就直接上代码了
#include <iostream>using namespace std;
const int N = 2e5 + 10;
typedef long long LL;
LL a[N], b[N];
LL n, m;
bool check(LL x)
{LL cnt = 0;for (int i = 1; i <= n; i++){if (a[i] + b[i] < x) return false;if (a[i] < x)cnt += (x - a[i]);if (cnt > m) return false;}return true;
}
int main()
{cin >> n >> m;LL l = 0, r = 0;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++){cin >> b[i];r = max(r, b[i] + a[i]);}while (l < r){LL mid = (l + r + 1) / 2;if (check(mid)) l = mid;else r = mid - 1;}cout << l << endl;return 0;
}
我们一个小贪心是首先处理最高位，让最高位最大。
可以对每位数字进行加一或者减一的操作分别a，b次
我们先来分析一下减法操作：
对x做减法，要么就减到9要么就不减，比如将4减到9要先减四次减到0然后还得减一次
所以有要减：x + 1次操作。
那么加法呢
我们将x最好能加到9要进行几次操作，比如将5加到9要进行4次操作
所以加到9要用x次加法。
我们可以采用深搜来解决这个问题
#include <iostream>using namespace std;
typedef long long LL;
string s, ret;
LL n;
void dfs(LL pos, LL a, LL b, string s)
{if (pos == n){if (ret < s) ret = s;return;}LL up = '9' - s[pos], down = s[pos] - '0' + 1;if (up <= a || down <= b){s[pos] = '9';if(up <= a)dfs(pos + 1, a - up, b, s);if(down <= b)dfs(pos + 1, a, b - down, s);}else{s[pos] += a;dfs(pos + 1, 0, b, s);}}
int main()
{LL a, b;cin >> s >> a >> b;n = s.size();dfs(0, a, b, s);cout << ret << endl;return 0;
}