梦熊解析：202505基础算法
T1 - 最小数码
解法：
第一问答案为 2n，因为从 n 变成 2n 的过程中，若进位会使数码和减少（逢十进一），因此不进位时数码和最大。不进位的充要条件是每一位权值在 4 以内。
第二问需找到每一位均为 4 或更小，且数码和为 n 的最小值。为使位数最少，贪心策略是尽可能多填 4，小数放前。
示例：
- 若 n=5，答案为 14
- 若 n=8，答案为 44
Code:
#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d", &x)
vector<int> v;
int main() {
int n;
sc(n);
cout << 2 * n << endl;
while (n != 0) {
if (n >= 4) v.push_back(4), n -= 4;
else v.push_back(n), n = 0;
}
for (int i = v.size() - 1; i >= 0; i--)
printf("%d", v[i]);
return 0;
}
T2 - 数
解法：
枚举 b 的大小（上界为 log2n），确定 b 后，a=⌊2bn⌋，c=n−a⋅2b，取 a+b+c 的最小值。复杂度为 O(logn)。
Code:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll n;
cin >> n;
ll B = log2(n);
ll ans = n;
for (int b = 1; b <= B; b++) {
ll t = pow(2ll, b);
ll a = n / t;
ll c = n - a * t;
ans = min(ans, a + b + c);
}
cout << ans;
return 0;
}
T3 - 相等
解法：
令 d=b−a，问题等价于通过 k 轮操作（每轮可将当前数加 k 或 k+1）使 a 变为 b。
- 若 a 和 b 奇偶性不同，无解。
- 否则，通过二分或暴力枚举找到最小 k，满足 k(k+1)/2≥d 且 (d−k(k+1)/2) 为偶数。
Code:cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
int ans = 0;
while (a < b || (b - a) % 2) {
ans++;
a += ans; // 每轮默认选k（加ans）
}
cout << ans << endl;
}
return 0;
}
T4 - 一和二
解法：
将 1 视为 −1，2 视为 1，问题转化为寻找跨过中间间隙的区间，使剩余部分和为 0。
- 预处理前缀和，左半部分（前 n 项）和右半部分（后 n 项）分别计算。
- 利用哈希表存储右半部分前缀和，枚举左半部分前缀和，查找是否存在互补值，计算最小区间长度。
Code:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 84;
int T, n, a[maxn], ans;
map<int, int> mp; // 存储右半部分前缀和对应的位置
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
mp.clear();
for (int i = 1; i <= n * 2; i++) {
scanf("%d", &a[i]);
a[i] = (a[i] == 1 ? -1 : 1); // 1→-1，2→1
}
ans = n * 2; // 初始化为最大可能长度
// 计算左半部分前缀和（前n项）
for (int i = 1; i <= n; i++) {
a[i] += a[i-1];
if (a[i] == 0) ans = min(ans, 2*n - i); // 左半部分和为0，剩余右半部分长度
}
// 计算右半部分前缀和（后n项，逆序处理）
a[2*n+1] = 0; // 右半部分起点为n+1，终点为2n
for (int i = 2*n; i >= n+1; i--) {
a[i] += a[i+1];
mp[a[i]] = i - (n+1); // 记录前缀和对应的位置偏移（相对于右半部分起点）
if (a[i] == 0) ans = min(ans, i - 1); // 右半部分和为0，剩余左半部分长度
}
// 枚举左半部分前缀和，查找右半部分是否有互补值
for (int i = n; i >= 1; i--) {
if (mp.find(-a[i]) != mp.end()) {
// 计算总长度：左半部分剩余i项，右半部分剩余mp[-a[i]]项
ans = min(ans, mp[-a[i]] + (n - i));
}
}
printf("%d\n", ans);
}
return 0;
}