2024年第七届传智杯程序设计挑战赛第一场初赛题解

除了最后一题以外其他都比较简单

签到题

排序从小到大拿即可

#include <bits/stdc++.h>
using namespace std;int main()
{int n, k;cin >> n >> k;vector<int> a(n);for (int i = 0; i < n; i ++) cin >> a[i];sort(a.begin(), a.end());for (int i = 0; i < n; i ++){if (k >= a[i]) k -= a[i];else return cout << i << '\n', 0;}cout << n << '\n';return 0;
}

签到题

直接输出 $b-a$ 和 $b$ 即可

#include <bits/stdc++.h>
using namespace std;int main()
{int a, b;cin >> a >> b;cout << b - a << ' ' << b << '\n';return 0;
}

签到题

对于每一个数字，从后往前开始找，如果找到偶数位，则和最后一位交换即可

#include <bits/stdc++.h>
using namespace std;void solve()
{string s;cin >> s;for (int i = s.size() - 1; i >= 0; i --)if ((s[i] - '0') % 2 == 0){swap(s[i], s.back());return cout << s << '\n', void();}cout << -1 << '\n';
}int main()
{int t;cin >> t;while (t --) solve();return 0;
}

签到题

遍历一遍字符串，数出 :-) 和 :-( 的个数即可

#include <bits/stdc++.h>
using namespace std;int main()
{string s;getline(cin, s);int a = 0, b = 0;for (int i = 0; i + 2 < s.size(); i ++){string t = s.substr(i, 3);if (t == ":-)") a ++;else if (t == ":-(") b ++;}if (a == 0 && b == 0) cout << "None" << '\n';else if (a > b) cout << "Happy" << '\n';else if (a < b) cout << "Sad" << '\n';else cout << "Just so so" << '\n';return 0;
}

思维题

先对每个点按照象限分类计数，显然一象限和三象限的点相连必然经过两条坐标轴，二象限和四象限的点相连必然经过两条坐标轴，最后在计算配对后剩下的点即可，只能经过一条坐标轴

#include <bits/stdc++.h>
#define int long long
using namespace std;signed main()
{int n;cin >> n;int p1 = 0, p2 = 0, p3 = 0, p4 = 0;for (int i = 0; i < n; i ++){int x, y;cin >> x >> y;if (x > 0 && y > 0) p1 ++;if (x < 0 && y > 0) p2 ++;if (x < 0 && y < 0) p3 ++;if (x > 0 && y < 0) p4 ++;}int min13 = min(p1, p3), min24 = min(p2, p4);int ans = (min13 + min24) * 2;p1 -= min13, p3 -= min13;p2 -= min24, p4 -= min24;ans += min(max(p1, p3), max(p2, p4));cout << ans << '\n';return 0;
}

枚举题

枚举每一个棋子，判断是否能为四子棋，注意，只需要以当前点为起点，往右，往下，往右下，往坐下这四种情况。

#include <bits/stdc++.h>
using namespace std;int main()
{int n, m;cin >> n >> m;vector<string> g(n);auto check = [&](int x, int y) -> bool{char c = g[x][y];if (y + 3 < m){if (g[x][y + 1] == c && g[x][y + 2] == c && g[x][y + 3] == c)return true;}if (x + 3 < n){if (g[x + 1][y] == c && g[x + 2][y] == c && g[x + 3][y] == c)return true;}if (x + 3 < n && y + 3 < m){if (g[x + 1][y + 1] == c && g[x + 2][y + 2] == c && g[x + 3][y + 3] == c)return true;}if (x + 3 < n && y - 3 >= 0){if (g[x + 1][y - 1] == c && g[x + 2][y - 2] == c && g[x + 3][y - 3] == c)return true;}return false;};for (int i = 0; i < n; i ++) cin >> g[i];for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++)if (g[i][j] != '.' && check(i, j))return cout << (g[i][j] == 'r'? "kou" : "yukari") << '\n', 0;cout << "to be continued" << '\n';return 0;
}

二分答案题

二分最大值，判断是否能够在 $k$ 次操作内完成。需要注意的是答案的范围，极限情况是 $n=1,k=10^9,x=10^9,a[1]=1$ 的情况，此时最小的可能答案为 $-10^{18}+1$ ，而最大值则为 $a$ 数组的最大值。所以需要用到 __int128_t 。（实测数据没有那么极限，最小值开到 $-10^{15}$ 也可以过）

#include <bits/stdc++.h>
#define int long long
using namespace std;signed main()
{int n, k, x;cin >> n >> k >> x;vector<int> a(n);for (int &i : a) cin >> i;int l = -1e18, r = *max_element(a.begin(), a.end());auto check = [&](__int128_t mid) -> bool{__int128_t cnt = 0;for (int &i : a)if (i > mid) cnt += (i - mid + x - 1) / x;return cnt <= k;};while (l < r){__int128_t mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << l << '\n';return 0;
}

动态规划题

简单数学知识，乘积末尾的 $0$ 的个数只和相乘的每一个数的因子 $2$ 和因子 $5$ 的个数有关。

考虑动态规划，定义状态表示为

• 考虑前 $i$ 个数，选择第 $i$ 个数，有 $j$ 个因子 $2$ 的情况下，因子 $5$ 的个数为 $dp[i][1][j]$

• 考虑前 $i$ 个数，不选择第 $i$ 个数，有 $j$ 个因子 $2$ 的情况下，因子 $5$ 的个数为 $dp[i][0][j]$

状态转移方程为：

$dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j])$

$dp[i][1][j]=max(dp[i][1][j],dp[i-1][0][j-a[i].first]+a[i].second)$

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin >> n;vector<pair<int, int>> a(n + 1);int cnt2 = 0;for (int i = 1; i <= n; i ++){int x;cin >> x;while (x % 2 == 0){x /= 2;a[i].first ++;}while (x % 5 == 0){x /= 5;a[i].second ++;}cnt2 += a[i].first;}vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(cnt2 + 1, -1)));dp[0][0][0] = 0;for (int i = 1; i <= n; i ++){for (int j = 0; j <= cnt2; j ++){if (dp[i - 1][0][j] != -1){dp[i][0][j] = max(dp[i][0][j], dp[i - 1][0][j]);if (j + a[i].first <= cnt2){dp[i][1][j + a[i].first] = max(dp[i][1][j + a[i].first], dp[i - 1][0][j] + a[i].second);}}if (dp[i - 1][1][j] != -1)dp[i][0][j] = max(dp[i][0][j], dp[i - 1][1][j]);}}int ans = 0;for (int i = 1; i <= cnt2; i ++){if (dp[n][0][i] != -1) ans = max(ans, min(dp[n][0][i], i));if (dp[n][1][i] != -1) ans = max(ans, min(dp[n][1][i], i));}cout << ans << '\n';return 0;
}