2008

Qualification Round

A. Saving the Universe

贪心，每次扩展极长的一段使得 search engine 不全在一段里面。

B. Train Timetable

按出发时间排序，扫一遍。

C. Fly Swatter

问题转换为有多少个空白位置可以放一个球，把绳子和球拍框的半径/厚度都加上 f，求空白的面积。考虑一个象限，然后分类讨论即可。

Round 1A

A. Minimum Scalar Product

排序不等式

B. Milkshakes

题目大意：给出一个 SAT 问题，求一组取得 \(1\) 最少的解。保证每个 clause 最多有一个 negated variable。

题解：假设所有变量取 \(0\)，然后对不满足的 clause，将它的对应变量变为 \(0\)，重复上述步骤。\(\mathcal{O}(n)\)。

C. Numbers

题目大意：求 \((3+\sqrt5)^n(n\leq 2\times 10^9)\) 的整数部分末三位。

题解：令 \((3+\sqrt5)^n=a_n+b_n\sqrt5\)，那么 \((3+\sqrt5)^n+(3-\sqrt5)^n=2*a_n\)。