企业官网建设流程全解析

1. 赛题整体设计与出题思路拆解

1.1 三题并置的考察意图

这套初赛题一共三道，题面分别叫 Drink、GPA、Dec，从命名就能看出出题人刻意把难度梯度拉开：一道偏模拟与贪心，一道偏动态规划与精度处理，一道偏数论与状态压缩。三题放在同一场次，本质上是想用最短的题面覆盖最广的能力面，让不同水平的选手都能找到自己的得分点，同时又能把真正的高手筛出来。

我个人的判断是，这种"三题制"的初赛设计非常聪明。它不像某些比赛一上来就给你一道需要复杂数据结构的大题，把新手直接劝退；也不像纯签到题那样毫无区分度。Drink 负责让大部分人拿到基础分，GPA 负责考察你对边界和精度的敏感度，Dec 则是那道"看起来简单、写起来要命"的压轴。这种结构在当年的赛制下是很典型的，也值得后来想办比赛的人参考。

1.2 为什么是这三个方向

如果把三道题抽象一下，它们分别对应了竞赛中最常见的三类思维模式：

• Drink：资源分配类问题，核心是"在约束下最大化收益"，典型的贪心或枚举思路。
• GPA：多阶段决策问题，核心是"每一步选择影响最终结果"，典型的动态规划或搜索。
• Dec：数值与状态的关系问题，核心是"两个数之间的某种变换关系"，典型的数论或位运算。

这三个方向几乎覆盖了算法竞赛入门到进阶的主干。出题人没有选择图论、字符串这些同样重要的方向，我猜是因为初赛时间有限，想在最短时间内考察最通用的能力。这个取舍本身就很值得玩味——比赛设计从来不是"考得越多越好"，而是"用最少的题考出最真实的水平"。

1.3 难度曲线的隐藏设计

三道题的难度并不是简单递增的。Drink 的难点在于想清楚贪心策略是否成立，GPA 的难点在于状态设计和精度控制，Dec 的难点在于数学推导。它们各自卡人的点完全不同，这意味着一个选手可能卡在 Drink 的贪心上，却轻松做出 Dec 的数学题。这种"交叉难度"设计能有效避免"一刀切"的排名，让排名更能反映选手的综合能力而非单一方向的能力。

提示：如果你在复盘这类比赛，不要只按题目顺序做。先快速扫一遍三题的题面，判断哪道题的"卡点"正好是你擅长的方向，优先拿下，再回头啃硬骨头。这个策略在限时比赛中往往能多拿几十分。

2. Drink 题核心细节与贪心策略解析

2.1 题面还原与核心约束

Drink 这道题的经典设定是这样的：你有若干种饮料，每种饮料提供一定的"快乐值"和一定的"体积"，你有一个容量有限的胃，问怎么喝能让总快乐值最大。听起来像背包问题，但关键在于每种饮料可以喝多杯，而且可能有额外的限制条件（比如某种饮料喝多了会降低单位快乐值，或者有每日上限）。

这类题最容易被误判成完全背包。我见过太多选手一看到"容量有限、物品可重复选、求最大价值"就直接套完全背包模板，结果发现样例过不了。问题出在题目往往藏了一个"边际递减"或者"组合限制"的条件，让贪心或背包的简单形式失效。

2.2 贪心还是背包：判断依据

判断这类题该用贪心还是背包，我的经验是看两个点：

1. 单位价值是否固定。如果每种饮料每杯的快乐值/体积比是固定的，那直接按单位价值排序贪心即可，因为喝哪杯都一样，先喝性价比高的。
2. 是否存在组合约束。如果题目说"喝满三杯某饮料送一杯"或者"某两种饮料不能同时喝"，那就必须上动态规划，因为局部最优不再导向全局最优。

当年这道 Drink 的题面，从网络上的讨论来看，核心是一个带容量上限的贪心，但需要处理"最后一杯喝不完"的边界。这个边界恰恰是最容易丢分的地方。

2.3 贪心策略的完整推导

假设题目简化为：有 n 种饮料，第 i 种每杯体积为 v[i]，快乐值为 h[i]，胃容量为 V，每种饮料可以喝任意多杯（整数杯），求最大快乐值。

如果所有饮料的单位快乐值 h[i]/v[i] 都不同，贪心策略是：按 h[i]/v[i] 从大到小排序，依次尽量多喝，直到胃满。这个策略成立的前提是"每杯饮料的性价比固定"，也就是没有边际递减。

但实际题目里往往有一个陷阱：最后可能剩下一点容量，装不下任何一整杯饮料。这时候你有两个选择——要么浪费这点容量，要么用一杯体积更小但性价比更低的饮料来填。正确的做法是：在贪心选完高性价比饮料后，枚举所有饮料，看哪一杯能塞进剩余容量且快乐值最高，取这个最优解。

# Drink 贪心核心逻辑示意 def solve(drinks, capacity): # drinks: [(volume, happiness), ...] # 按单位快乐值降序排序 drinks.sort(key=lambda x: x[1] / x[0], reverse=True) total_happiness = 0 remaining = capacity for v, h in drinks: if v <= remaining: count = remaining // v total_happiness += count * h remaining -= count * v # 处理剩余容量：枚举所有饮料找最优填充 best_fill = 0 for v, h in drinks: if v <= remaining: best_fill = max(best_fill, h) return total_happiness + best_fill

这段代码的关键在最后那个best_fill循环。很多人贪心完就直接返回了，忽略了剩余容量还能塞一杯小饮料。这个细节在样例里可能看不出来，但在系统测试里一定会被卡。

2.4 实操中的三个坑

坑一：整数除法与浮点比较。排序时如果用浮点数比较 h[i]/v[i]，可能因为精度问题导致顺序错误。稳妥的做法是用交叉相乘比较：h[a]*v[b] > h[b]*v[a]。这个技巧在竞赛里非常常用，能避免大量精度问题。

坑二：容量为 0 或饮料体积为 0 的边界。如果某杯饮料体积为 0 但快乐值大于 0，那理论上可以喝无限杯，答案就是无穷大。出题人一般会避免这种情况，但你必须处理，否则会死循环。

坑三：贪心后剩余容量的处理。上面说了，必须枚举所有饮料找最优填充，不能想当然地认为"剩下的容量就浪费了"。

注意：贪心题最怕的就是"想当然"。每次写完贪心策略，一定要问自己一句——"有没有一种情况，我放弃一个高性价比的选择，反而能得到更好的结果？"如果答案是"有"，那你的贪心就是错的，得换动态规划。

3. GPA 题的状态设计与精度控制

3.1 题面核心：多阶段决策

GPA 这道题的经典设定是：你有一堆课程，每门课有学分和可能的成绩等级，你需要决定每门课投入多少精力，从而在总精力有限的情况下最大化加权平均分（GPA）。每门课的成绩和投入精力的关系通常是一个分段函数或者一个递减的收益函数。

这道题的本质是"资源分配 + 多阶段决策"，标准的解法是动态规划。但它的难点不在 DP 本身，而在两个地方：一是状态怎么设计才能既准确又高效，二是 GPA 的计算涉及除法，精度怎么控制。

3.2 状态设计的取舍

最直观的状态设计是：dp[i][j]表示前 i 门课，总共投入 j 点精力时能得到的最大"总绩点加权和"。最后答案就是dp[n][J] / 总学分。

但这个设计有个问题：如果精力是连续值或者范围很大，二维数组会爆内存。这时候有两种优化方向：

1. 精力离散化。如果题目给的精力是整数且范围不大（比如几千），直接用二维数组没问题。
2. 滚动数组。如果课程数很多，可以用一维数组滚动更新，把空间从 O(n*J) 降到 O(J)。

我当年做这类题时，第一反应总是先写最直观的二维 DP，跑通样例后再考虑优化。这个顺序很重要——先保证正确性，再考虑效率。很多选手一上来就想最优解，结果状态设计错了，debug 半天。

3.3 精度问题的处理

GPA 涉及除法，浮点数误差是绕不开的。假设总学分是 100，总加权和是 385.5，那 GPA 就是 3.855。如果你用 double 存储，最后输出时可能变成 3.8549999999，四舍五入后变成 3.85，和正确答案 3.86 差了一位。

处理这个问题有两个思路：

• 全程用整数。把成绩乘以一个固定倍数（比如 100），所有计算都在整数域完成，最后再除以倍数。这样能完全避免浮点误差。
• 用高精度或定点数。如果题目允许，用 Python 的 Decimal 或者自己实现定点运算。

# GPA 整数化处理示意 # 假设成绩是 0-100 的整数，学分是整数 # 我们把总加权和乘以 100 存储，避免浮点 def solve(courses, total_effort): # courses: [(credit, [(effort, score), ...]), ...] # dp[j] = 投入 j 精力时的最大 (加权和 * 100) dp = [-1] * (total_effort + 1) dp[0] = 0 for credit, options in courses: new_dp = [-1] * (total_effort + 1) for j in range(total_effort + 1): if dp[j] < 0: continue for effort, score in options: if j + effort <= total_effort: val = dp[j] + score * credit * 100 if val > new_dp[j + effort]: new_dp[j + effort] = val dp = new_dp best = max(dp) total_credit = sum(c for c, _ in courses) return best / (total_credit * 100)

这段代码里，score * credit * 100就是整数化处理。最后除以total_credit * 100得到真正的 GPA。这样全程没有浮点运算，精度绝对可靠。

3.4 输出格式的坑

GPA 题通常要求输出保留两位小数。这里有个经典陷阱：C++ 的printf("%.2f")用的是四舍五入，但有些题目的标准答案用的是"四舍五入到最近"，有些用的是"截断"。你必须仔细读题，看清楚是哪种。

更坑的是，如果答案是 3.855，printf("%.2f")可能输出 3.85 也可能输出 3.86，取决于底层实现。稳妥的做法是手动加 0.005 再截断，或者用整数运算最后再格式化。

提示：遇到要求保留小数的题，先在本地用几个边界值测试一下你的输出和预期是否一致。特别是 x.xx5 这种值，最容易出问题。

4. Dec 题的数学推导与状态压缩

4.1 题面本质：两个数的变换关系

Dec 这道题从名字看就和"十进制"或"递减"有关。从网络上的讨论来看，它的核心是：给定两个数 a 和 b，每次操作可以把一个数减一或者做某种位运算，问最少多少步能让 a 变成 b。或者反过来，问在某个范围内有多少对 (a, b) 满足某种变换关系。

这类题的关键在于找到变换的"不变量"或者"单调性"。如果每次操作都让某个量单调变化，那就可以用贪心或二分；如果操作是可逆的，那就可以双向搜索。

4.2 从暴力到优化的推导路径

假设题目是：每次可以把 a 减一，或者把 a 的某一位翻转，问最少多少步变成 b。

暴力 BFS 肯定能过小数据，但数据一大就爆。优化的思路是：观察到"减一"操作是单调递减的，而"翻转位"操作可能让数变大也可能变小。这时候可以把问题拆成两段：先用翻转位快速接近目标，再用减一微调。

更一般的做法是数位 DP。把 a 和 b 写成二进制，从高位到低位逐位决策，记录当前是否已经"小于"目标、是否已经"大于"目标等状态。这个思路在竞赛里非常通用，几乎能解决所有"两个数之间的位变换"问题。

4.3 状态压缩的实操要点

如果题目涉及多个数的组合状态，比如"从一堆数里选若干个，使它们的异或和等于某个值"，那就需要状态压缩。核心是把"选了哪些数"压缩成一个二进制掩码，然后用 DP 或 BFS 遍历所有掩码。

# Dec 类问题的状态压缩示意 # 假设有 n 个数，问有多少个子集的异或和等于 target def count_subsets(nums, target): # dp[mask] = 异或和为 mask 的子集数量 # 但异或和范围可能很大，需要先确定上界 max_val = 1 while max_val <= max(max(nums), target): max_val <<= 1 dp = [0] * max_val dp[0] = 1 for num in nums: new_dp = dp[:] for x in range(max_val): if dp[x] > 0: new_dp[x ^ num] += dp[x] dp = new_dp return dp[target]

这段代码的时间复杂度是 O(n * 2^k)，其中 k 是数的二进制位数。如果 k 太大（比如超过 20），这个做法就不可行了，需要换数学方法。

4.4 数学推导的常见套路

Dec 这类题如果数据范围很大，往往需要纯数学推导。常见的套路有：

• 找规律：手算前几项，看答案是否满足某个递推式或闭式公式。
• 二进制分解：把数拆成二进制，逐位独立计算贡献。
• 容斥原理：如果问"满足至少一个条件的数有多少"，用容斥。

我个人的经验是，遇到这种题先别急着写代码，拿纸笔手算 n=1,2,3,4,5 的情况，把答案列出来，往往规律就出来了。竞赛里很多所谓的"数学题"，本质就是"你愿不愿意花五分钟手算"。

5. 常见问题与排查技巧实录

5.1 三题通用的调试清单

5.2 贪心题的反例构造技巧

验证贪心是否正确，最有效的方法是构造反例。具体做法是：随机生成小规模数据，用暴力搜索求最优解，再用贪心求一个解，比较两者是否相等。如果不等，输出这组数据，你就找到了反例。

这个技巧我在做 Drink 时用过，非常有效。写一个 10 行以内的暴力枚举，跑几千组随机数据，几分钟就能确认贪心策略是否成立。

5.3 DP 题的初始化陷阱

DP 题的初始化是最容易出错的地方。以 GPA 为例，dp[0] = 0表示"投入 0 精力得到 0 加权和"，这是对的。但如果你把dp其他位置初始化为 0 而不是 -1，那就会把"不可达状态"误判为"可达且值为 0"，导致答案错误。

正确的做法是：用 -1 或一个足够小的负数表示不可达，只有dp[0]初始化为 0。转移时先判断当前状态是否可达，再更新。

5.4 精度题的终极方案

如果你实在搞不定浮点精度，最稳妥的方案是：把所有涉及小数的运算都转成整数。具体做法是找到题目中所有小数的最小公倍数，全部乘以这个倍数，最后再除回去。

比如 GPA 题，成绩可能是 3.7、3.3 这种一位小数，那就全部乘以 10，变成 37、33，最后除以 10。这样全程整数运算，精度绝对没问题。

注意：整数化之后要注意溢出。如果数据范围大，C++ 里要用 long long，Python 里不用担心。这也是 Python 在竞赛中的一个优势——大整数运算不用操心溢出。

5.5 时间分配的实战建议

初赛通常 2-3 小时，三道题。我的建议是：

• 前 30 分钟：快速读三题，判断难度，确定做题顺序。
• 接下来 60 分钟：拿下最有把握的两道题，确保样例和边界都过。
• 最后 30 分钟：啃最难的题，能拿多少分拿多少分，同时回头检查前两题有没有低级错误。

这个分配不是死的，但核心原则是"先拿稳的分，再冲难题"。我见过太多选手在一道题上死磕两小时，最后其他题都没时间做，排名很难看。

6. 从这三题看算法竞赛的备赛方法

6.1 贪心、DP、数论的三位一体

Drink、GPA、Dec 这三道题，恰好对应了算法竞赛的三大基础模块：贪心、动态规划、数论与位运算。如果你能把这三类题都吃透，那大部分初赛题对你来说都不成问题。

我的备赛建议是：每个模块至少刷 20 道经典题，从最简单的开始，逐步加难度。刷题时不要只看答案，要自己想清楚"为什么这么做"、"有没有其他做法"、"这个做法在什么情况下会失效"。这种深度思考比刷题数量重要得多。

6.2 复盘比刷题更重要

做完一套题，不管成绩好坏，都要复盘。复盘的内容包括：

1. 每道题的思路是怎么来的，卡在哪一步。
2. 有没有更优的解法，别人的解法好在哪里。
3. 代码里有没有可以优化的地方，比如更简洁的写法、更快的常数。
4. 下次遇到类似题，能不能更快地识别出套路。

我个人的习惯是建一个"错题本"，把每次卡住的题和关键思路记下来，考前翻一遍，效果非常好。

6.3 代码模板的积累

竞赛里时间宝贵，能提前准备的模板一定要准备好。比如：

• 快速排序、二分查找的边界写法。
• 并查集、线段树的简洁实现。
• 大整数运算、精度处理的工具函数。
• 常见 DP 的状态转移框架。

这些模板不需要背，但要熟悉到"看一眼就能改"的程度。比赛时直接复制粘贴，能省下大量时间。

6.4 心态与策略

最后说点虚的但很重要的：竞赛心态。我见过太多选手因为一道题卡住就心态崩了，后面简单的题也做不出来。正确的做法是：卡住超过 20 分钟就果断跳过，先做别的，回头再想。很多时候你换个脑子回来，思路就通了。

还有就是不要追求"全对"。初赛的目标是晋级，不是满分。把能拿的分拿稳，比死磕难题更划算。这个策略在当年的赛制下尤其重要，因为初赛的晋级线往往不需要你做对所有题。

这套 Drink、GPA、Dec 的题，放到今天来看依然是很经典的初赛设计。它不追求偏难怪，而是扎扎实实考察基本功。如果你正在准备类似的比赛，不妨把这三道题找出来做一遍，感受一下出题人的思路，相信会有不少收获。