梦熊联盟：202505基础语法-题解
202505基础语法-题解
T1 - 九的倍数
解法：
对于 9 的倍数，只需要判定其各位的数码和是否为 9 的倍数即可。
例如判断一个数是不是 9 的倍数，只要判断其各位数字之和是不是 9 的倍数，因为一个数能被 9 整除当且仅当它的各位数字之和能被 9 整除。
因此将输入的数当作字符串读入，把每一位的数码和相加，判断是否为 9 的倍数即可。
Code：
#include <bits/stdc++.h>
using namespace std;
long long ans;
int main() {int t;cin >> t;while (t--) {string s;cin >> s;int ans = 0;for (int i = 0; i < s.length(); i++)ans += s[i] - '0';if (ans % 9)cout << "No\n";elsecout << "Yes\n";}
return 0;
}
T2 - 直线
解法：
容易发现两个点的斜率为某特定值时，当且仅当它们的横纵坐标相加的值相同。
因为（此处应有公式推导，但原始题解未给出），所以可以利用这一性质解题。
利用桶计算每个横纵坐标之和的值出现了多少次，由于值域范围较大，可以利用map等 STL 工具进行优化，时间复杂度为 O (n)。
Code：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
char a[5005];
int n;
int main() {scanf("%s", a + 1);n = strlen(a + 1);string s;int l = 1, r = n, t = 0;while (l <= r) {if (a[l] < a[r]) {cout << a[l];l++;} else {if (a[l] > a[r]) {cout << a[r];r--;} else {int ll = l, rr = r;while (ll <= rr && a[ll] == a[rr]) {ll++;rr--;}if (a[ll] <= a[rr]) {cout << a[l];l++;} else {cout << a[r];r--;}}}}
return 0;
}
T3 - 最小的串
解法：
我们很容易想出一个贪心思路，就是每次从头和尾中取较小的字符。但问题来了，如何处理头尾相等的情况呢？
可以选择不断往里找，直到找到两个不相同的位置，比较这两个数，取小的那一边的头或尾即可。时间复杂度为 O (n²)，如果实现得更精细可以做到 O (n)。
Code：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
char a[5005];
int n;
int main() {scanf("%s", a + 1);n = strlen(a + 1);string s;int l = 1, r = n, t = 0;while (l <= r) {if (a[l] < a[r]) {cout << a[l];l++;} else {if (a[l] > a[r]) {cout << a[r];r--;} else {int ll = l, rr = r;while (ll <= rr && a[ll] == a[rr]) {ll++;rr--;}if (a[ll] <= a[rr]) {cout << a[l];l++;} else {cout << a[r];r--;}}}}
return 0;
}
T4 - 砝码
解法：
如何用最少的砝码表示出尽量多的重量？
从二进制的角度，砝码重量一定是形如 2⁰, 2¹, 2², ... 以此类推。
从这个角度，为了能表示出 1 到 n 中的所有重量，最终答案前若干个砝码一定形如 2⁰, 2¹, ..., 2^k，之后的每个数都在某个范围内（例如样例中的数值可以表示成特定组合）。
我们可以枚举 k 的大小，那么剩下所有的数最大的值最小可以是某个值，注意 k 的取值范围且答案为某个表达式，因为（此处应有公式推导，但原始题解未给出），所以单次复杂度为 O (log n)。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
void work() {long long n, m;cin >> n >> m;long long ans = 1e18;for (int i = 0; i <= 30; i++) {if (i + 1 > m)continue;long long D = (1ll << i);long long C = (1ll << (i + 1)) - 1;if (C >= n) {ans = min(ans, D);continue;}long long E = m - (i + 1);if (E == 0)continue;long long F = (n - C) / E + ((n - C) % E > 0);if (F > C)continue;ans = min(ans, max(F, D));}if (ans == 1e18)cout << "-1\n";elsecout << ans << '\n';}
int main() {std::ios::sync_with_stdio(0);std::cin.tie(0);int T;std::cin >> T;for (; T--;)work();
return 0;
}
练习：
https://our.oj.fmcraft.top/contest.php?cid=1003