当前位置：首页 > news >正文

第十四届蓝桥杯大赛软件赛国赛C/C++大学C组

news 2025/6/28 4:26:22

A

【跑步计划——日期问题】-CSDN博客

B

【残缺的数字】-CSDN博客

C

题目

代码

#include <bits/stdc++.h>
using namespace std;void change(int &x)
{int sum = 0, t = x;while(t){sum += t % 10;t /= 10;}x -= sum;
}
int main()
{int n;cin >> n;int ans = 0;while(n){change(n);ans++;}cout << ans;
}

D

【定时任务——日期问题+字符串格式】-CSDN博客

E

【2023——二项式反演】-CSDN博客

F

题目

分析

01背包变种，多考虑一种选法，多开一个维度。由于内存限制，还得采用滚动数组（一般用滚动要清空，背包特殊）。

代码

#include <bits/stdc++.h>
using namespace std;const int N = 210;
const int M = 1010;int f[2][M][M];
int w[N];int main()
{int n, a, b;cin >> n >> a >> b;for(int i = 1; i <= n; i++)cin >> w[i];for(int i = 1; i <= n; i++)for(int j = 0; j <= a; j++)for(int k = 0; k <= b; k++){f[i&1][j][k] = f[i-1&1][j][k];if(j-w[i] >= 0) f[i&1][j][k] = max(f[i&1][j][k], f[i-1&1][j-w[i]][k] + w[i]);if(k-w[i] >= 0) f[i&1][j][k] = max(f[i&1][j][k], f[i-1&1][j][k-w[i]] + w[i]);}cout << f[n&1][a][b];return 0;
}

注意这里用倒序的空间优化时，不能j >= w[i] k >= w[i]，原因是比如f[w[i]][0]仍有机会参加更新，但是k=0

#include <bits/stdc++.h>
using namespace std;const int N = 210;
const int M = 1010;int f[M][M];
int w[N];int main()
{int n, a, b;cin >> n >> a >> b;for(int i = 1; i <= n; i++)cin >> w[i];for(int i = 1; i <= n; i++)for(int j = a; j >= 0; j--)for(int k = b; k >= 0; k--){if(j-w[i] >= 0) f[j][k] = max(f[j][k], f[j-w[i]][k] + w[i]);if(k-w[i] >= 0) f[j][k] = max(f[j][k], f[j][k-w[i]] + w[i]);}cout << f[a][b];return 0;
}