算法题解：签到题与看似模拟实则函数最值的题目
1. 数字处理的最优策略
给定一个数 n，每次操作可以减 x 或除以 2，目标是使 n 尽快变为 0。
错误解法：使用 DFS 穷举。
正确思路：贪心比较两种操作的效率，每次选择最小值。
while (n > 0) {
n = min(n / 2, n - x);
res++;
}
2. 数组归零的区间操作
有两种操作：对所有数取模和所有数减去同一个值。
错误思路：误用线段树。
分类讨论：
- 全部为 0：操作数 0。
- 全部为 1：操作数 1。
- 最大公约数不为 1：对整个数组模 gcd，全部归零。
- 最大公约数为 1（互质）：先模 2，再减 1。
3. 贡献计算问题
题目来源：牛客 11227 D
问题：计算所有方案中快乐值的总和。固定前 3 个位置后，其余位置有 2^(n-3) 种方案，因此总和为每个位置贡献乘以 2^(n-3) 的累加和。
for (int i = 1; i <= n; i++) {
ll cur = 0;
if (i * 2 <= n) {
cur += a[i] ^ a[i * 2];
}
if (i * 2 + 1 <= n) {
cur += a[i] ^ a[i * 2 + 1];
cur += a[i] ^ a[i * 2 + 1] ^ a[i * 2];
cur += a[i * 2] ^ a[i * 2 + 1];
ans += cur * mi[n - 3];
} else {
ans += cur * mi[n - 2];
}
ans %= mod;
}
4. 时间分配问题
题目来源：牛客 11227 E
每个工艺品可以自己制作或等待他人提供半成品后完成。
策略：
- 全部自己制作。
- 如果制作速度小于加工速度：先全力加工半成品，剩余时间自己完成。
关键代码：
if (a < c) {
cout << n / a;
} else {
int can_make = min((n - c) / b, (n - b) / c);
cout << can_make + (n - can_make * c) / a;
}
5. 数位 DP 简化版——鸡尾酒数字
对于 n 位数，前 n-1 位确定后，末位只有一个数字能使总和等于目标值（如 10）。核心是维护前 n-1 位的和 dn。
6. 炉石完美击杀问题
题目来源：牛客 34442 C
每次攻击减 1 血，每 7 次对全体造成伤害。判断能否同时击杀。
条件：总数必须是 (n+6) 的倍数，且最小值不小于每次群体伤害量。
if (sum % (n + 6) != 0 || min_val < sum / (n + 6)) {
cout << "NO\n";
} else {
cout << "YES\n";
}
7. 货物运输最小费用问题
从 A、B 向 C、D 运输货物，费用不同，求最小总成本。
设 A→C 运量为 x，则总费用 y 为关于 x 的一次函数：
y = (ac - ad + bd - bc) * x + bc*C + ad*A + bd*B - bd*C
分类讨论系数：
- 系数 ≥ 0：x 越小越好。
- 若 B ≥ C：x = 0
- 否则：x = C - B
- 系数 < 0：x 越大越好。
- 若 A ≥ C：x = C
- 否则：x = A
实现代码：
int A, B, C, D;
cin >> A >> B >> C >> D;
int ac, ad, bc, bd;
cin >> ac >> ad >> bc >> bd;
int coeff = ac - ad + bd - bc;
if (coeff >= 0) {
int x = (B >= C) ? 0 : (C - B);
cout << coeff * x + bc*C + ad*A + bd*B - bd*C << endl;
} else {
int x = (A >= C) ? C : A;
cout << coeff * x + bc*C + ad*A + bd*B - bd*C << endl;
}
