【每日一题 | 2025】2.17 ~ 2.23

个人主页：Guiat
归属专栏：每日一题

正文

1. 【2.17】P1203 [USACO1.1] 坏掉的项链 Broken Necklace

题目链接：https://www.luogu.com.cn/problem/P1203

【AC_Code】

#include <iostream>
#include <algorithm>
#include <cstring>
#define IOS ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);using namespace std;int n, a, b, w, ans; char s[700], c;int main()
{IOS; cin >> n >> s;memcpy(s + n, s, n);for (int i = 0; i < 2 * n; i ++){if (s[i] == 'w') b ++, w ++;else if (s[i] == c) b ++, w = 0;else ans = max(ans, a + b), a = b - w, b = w + 1, w = 0, c = s[i];}ans = max(ans, a + b);cout << min(ans, n) << "\n";return 0;
}

2. 【2.18】P8614 [蓝桥杯 2014 省 A] 波动数列

题目链接：https://www.luogu.com.cn/problem/P8614

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0),  cin.tie(0), cout.tie(0);using namespace std;const int mod = 1e8 + 7;
int n, s, a, b, f[1010][1010];int into(int x) { return (x % n + n) % n; }int main()
{IOS; cin >> n >> s >> a >> b; f[0][0] = 1;for (int i = 1; i < n; i ++) for (int j = 0; j < n; j ++){f[i][j] = (f[i - 1][into(j - a * i)] + f[i - 1][into(j + b * i)]) % mod;}cout << f[n - 1][into(s)] << "\n";return 0;
}

3. 【2.19】P11044 [蓝桥杯 2024 省 Java B] 食堂

题目链接：https://www.luogu.com.cn/problem/P11044

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int q, a2, a3, a4, b4, b6;int main()
{IOS; cin >> q;while (q --){int res = 0; cin >> a2 >> a3 >> a4 >> b4 >> b6;// 贪心算法：注意先后顺序 // 3 + 3while (b6 && a3 > 1) b6 --, a3 -= 2, res += 6;// 4 + 2while (b6 && a4 && a2) b6 --, a4 --, a2 --, res += 6;// 2 + 2 + 2while (b6 && a2 > 2) b6 --, a2 -= 3, res += 6;// 3 + 2while (b6 && a3 && a2) b6 --, a3--, a2 --, res += 5;// 4while (b6 && a4) b6 --, a4 --, res += 4;// 2 + 2while (b6 && a2 > 1) b6 --, a2 -= 2, res += 4;// 4while (b4 && a4) b4 --, a4 --, res += 4;// 2 + 2while (b4 && a2 > 1) b4 --, a2 -= 2, res += 4;// 3while (b6 && a3) b6 --, a3 --, res += 3;// 3while (b4 && a3) b4 --, a3 --, res += 3;// 2while (b6 && a2) b6 --, a2 --, res += 2;// 2while (b4 && a2) b4 --, a2 --, res += 2;cout << res << '\n';}return 0;
}

4. 【2.20】P10987 [蓝桥杯 2023 国 Python A] 火车运输

题目链接：https://www.luogu.com.cn/problem/P10987

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int n, a, b, w[210], dp[1010][1010], ans;int main()
{IOS; 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]) dp[j][k] = max(dp[j][k], dp[j - w[i]][k] + w[i]);if (k >= w[i]) dp[j][k] = max(dp[j][k], dp[j][k - w[i]] + w[i]);ans = max(ans, dp[j][k]);}cout << ans << '\n';return 0;
}

5. 【2.21】P8736 [蓝桥杯 2020 国 B] 游园安排

题目链接：https://www.luogu.com.cn/problem/P8736

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1e6 + 10;
string s, str[N], dp[N], ans[N];int main()
{IOS; cin >> s; int len = 0, cnt = 1;for (int i = 0; i < s.length(); i ++){if (isupper(s[i])) str[++ cnt] = s[i];else str[cnt] += s[i];}for (int i = 1; i <= cnt; i ++){int pos = int(lower_bound(dp + 1, dp + len + 1, str[i]) - dp);len = max(len, pos); dp[pos] = str[i];ans[pos] = ans[pos - 1] + str[i];}cout << ans[len] << '\n';return 0;
}

6. 【2.22】P8810 [蓝桥杯 2022 国 C] 数组个数

题目链接：https://www.luogu.com.cn/problem/P8810

【AC_Code】

#include <iostream>
#include <algorithm>
#include <cstring>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 1010, M = 11, mod = 1e9 + 7;
int n, b[N], dp[N][M][M], ans;void solve(int x, int y)
{memset(dp, 0, sizeof dp); dp[2][x][y] = 1;for (int i = 3; i <= n; ++i) for (int j = 0; j <= b[i - 1]; ++j) for (int k = 0; k <= b[i - 1]; ++k) for (int f = 0; f <= b[i - 1]; ++f){if (max(max(j, k), f) != b[i - 1]) continue;dp[i][j][k] += dp[i - 1][f][j]; dp[i][j][k] %= mod;}for (int i = 0; i <= 10; ++ i) for (int j = 0; j <= 10; ++ j){if (max(max(i, j), x) == b[n] && max(max(j, x), y) == b[1]) ans = (ans + dp[n][i][j]) % mod;}
}int main()
{IOS; cin >> n; for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 0; i <= 10; ++i) for (int j = 0; j <= 10; ++j) { solve(i, j); }cout << ans << '\n';return 0;
}

7. 【2.23】P8803 [蓝桥杯 2022 国 B] 费用报销

题目链接：https://www.luogu.com.cn/problem/P8803

【AC_Code】

#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int n, m, k, f[1010][5010], s[1010], last[1010], k1, sum, ans;
int dx[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
struct str { int m, d, v, t; } d[1010];
bool cmp(str a, str b) { return a.t < b.t; }int main()
{IOS; cin >> n >> m >> k1;for (int i = 2; i <= 12; i ++) s[i] = s[i - 1] + dx[i - 1];for (int i = 1; i <= n; i ++){cin >> d[i].m >> d[i].d >> d[i].v; d[i].t = s[d[i].m] + d[i].d;}sort(d + 1, d + 1 + n, cmp);for (int i = 1; i <= n; i ++) for (int j = 0; j < i; j ++){if (d[i].t - d[j].t >= k1) last[i] = j;}for (int i = 1; i <= n; i ++) for (int j = m; j >= d[i].v; j --){f[i][j] = f[i - 1][j],f[i][j] = max(f[i][j], f[last[i]][j - d[i].v] + d[i].v);}cout << f[n][m] << '\n';return 0;
}

结语
感谢您的阅读！期待您的一键三连！欢迎指正！