个人主页:Guiat
归属专栏:每日一题
文章目录
- 1. 【2.10】P8707 [蓝桥杯 2020 省 AB1] 走方格
- 2. 【2.11】P8742 [蓝桥杯 2021 省 AB] 砝码称重
- 3. 【2.12】P8786 [蓝桥杯 2022 省 B] 李白打酒加强版
- 4. 【2.13】P8725 [蓝桥杯 2020 省 AB3] 画中漂流
- 5. 【2.14】P8667 [蓝桥杯 2018 省 B] 递增三元组
- 6. 【2.15】P8806 [蓝桥杯 2022 国 B] 搬砖
- 7. 【2.16】P8699 [蓝桥杯 2019 国 B] 排列数
正文
1. 【2.10】P8707 [蓝桥杯 2020 省 AB1] 走方格
题目链接:https://www.luogu.com.cn/problem/P8707
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;int n, m, dp[35][35]; // 元素默认初始化为 0 int main()
{IOS; cin >> n >> m; dp[1][1] = 1;for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++){if ((i != 1 || j != 1) && (i %2 != 0 || j %2 != 0)){// dp[x][y] = dp[x - 1][y] + dp[x][y - 1]dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}cout << dp[n][m] << "\n";return 0;
}
2. 【2.11】P8742 [蓝桥杯 2021 省 AB] 砝码称重
题目链接:https://www.luogu.com.cn/problem/P8742
【AC_Code】
#include <iostream>
#include <cmath>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;int N, W[110], sum, dp[110][100010], ans;int main()
{IOS; cin >> N; for (int i = 1; i <= N; i ++) cin >> W[i], sum += W[i];for (int i = 1; i <= N; i ++) for (int j = sum; j >= 0; j --){if (j == W[i]) dp[i][j] = 1;else if (dp[i - 1][j]) dp[i][j] = 1;else if (dp[i - 1][j + W[i]]) dp[i][j] = 1;else if (dp[i - 1][abs(j - W[i])]) dp[i][j] = 1;}for (int i = 1; i <= sum; i ++) if (dp[N][i]) ans++;cout << ans << "\n";return 0;
}
3. 【2.12】P8786 [蓝桥杯 2022 省 B] 李白打酒加强版
题目链接:https://www.luogu.com.cn/problem/P8786
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;const int mod = 1e9 + 7;
int N, M, dp[205][105][105];int main()
{IOS; cin >> N >> M; dp[0][0][2] = 1;for (int i = 0; i < N + M; i ++) for (int j = 0; j < M; j ++) for (int k = 0; k < M; k ++){if (dp[i][j][k]){if (k > 0) dp[i + 1][j + 1][k - 1] += dp[i][j][k] % mod;if (k <= 50) dp[i + 1][j][2 * k] += dp[i][j][k] % mod;}}cout << dp[N + M][M][0] << "\n"; return 0;
}
4. 【2.13】P8725 [蓝桥杯 2020 省 AB3] 画中漂流
题目链接:https://www.luogu.com.cn/problem/P8725
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;const int mod = 1e9 + 7;
int D, T, M, f[3010][1510];int main()
{IOS; cin >> D >> T >> M; f[0][M] = 1;for (int i = 1; i <= T; i ++) for (int j = 0; j <= M; j ++){int len = D + (M - j) - (i - (M - j));if (len > 0) f[i][j] = (f[i - 1][j] + f[i - 1][j + 1]) % mod;}cout << f[T][0] << "\n";return 0;
}
5. 【2.14】P8667 [蓝桥杯 2018 省 B] 递增三元组
题目链接:https://www.luogu.com.cn/problem/P8667
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long longusing namespace std;const int maxn = 1e5 + 10;
int N, a[maxn], b[maxn], c[maxn], cnt;signed main()
{IOS; cin >> N;for (int i = 1; i <= N; i ++) cin >> a[i];for (int i = 1; i <= N; i ++) cin >> b[i];for (int i = 1; i <= N; i ++) cin >> c[i];sort(a + 1, a + N + 1), sort(c + 1, c + N + 1);for (int i = 1; i <= N; i ++){int cnta = lower_bound(a + 1, a + N + 1, b[i]) - a - 1;int cntc = upper_bound(c + 1, c + N + 1, b[i]) - c;cntc = N - cntc + 1;cnt += cnta * cntc;}cout << cnt << "\n";return 0;
}
6. 【2.15】P8806 [蓝桥杯 2022 国 B] 搬砖
题目链接:https://www.luogu.com.cn/problem/P8806
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std;int n, dp[20010], ans;
struct str { int w, v; } a[1010];bool cmp(str pre, str next) { return pre.w + pre.v <= next.w + next.v; }int main()
{IOS; cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i].w >> a[i].v;sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; i ++) for (int j = a[i].w + a[i].v; j >= a[i].w; j --){dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v);ans = max(ans, dp[j]);}cout << ans << "\n";return 0;
}
7. 【2.16】P8699 [蓝桥杯 2019 国 B] 排列数
题目链接:https://www.luogu.com.cn/problem/P8699
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std;const int mod = 123456;
int n, k, dp[510][510];int main()
{IOS; cin >> n >> k; dp[1][0] = 1; for (int i = 2; i <= n; i ++){dp[i][0] = 2;for (int j = 0; j <= i; j ++){dp[i +1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * 2 % mod) % mod;dp[i + 1][j + 2] = (dp[i + 1][j + 2] + dp[i][j] * (i - j - 2) % mod) % mod;dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (j + 1) % mod) % mod;}}cout << dp[n][k - 1] << "\n";return 0;}
结语
感谢您的阅读!期待您的一键三连!欢迎指正!