2016-C04-team1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题解 ==
EIJK 略去不表
=== A. Assigning Workstations [sfiction] ===
贪心将每个到达时间“连接”到离开时间上。O(nlogn)。
=== B. Better Productivity [sfiction] ===
如果a能覆盖b，那在最后加入a总能改进一个忽略a的方案。因此先处理出所有这些区间，对于剩下的区间求dp(i,j)为j个区间分成i段的最优解。枚举这些区间占多少个生产线，将之前忽略的区间中最大的单独放置于空闲生产线即可。注意相同区间需保留一个。O(pn^2^)。
=== C. Cleaning Pipes [sfiction] ===
每个管道为点，每个交点为一条边，当且仅当为二分图时有解。O(p^2^)。
=== D. Debugging [sfiction] ===
枚举运行次数，求最少的printf数，显然尽可能平均分配所得乘积最大，因此可以二分printf数，然后快速幂计算乘积。O(log^3^n)。
另一种做法：普通DP方程为O(n^1.5^)，记忆化搜索即可，有很多无用状态，似乎为O(nlogn)。
=== F. Flight Plan Evaluation [sfiction] ===
对于每条航线，求出所有交点排序后计算长度即可。O(cnm)。
=== G. Guessing Camels [sfiction] ===
如果(x,y)在ab中顺序不同，称为一个inverse pair。如果(x,y)在三个序列中顺序都相同，则没有inverse pair，否则必然有两个inverse pair。因此只需计算三个序列两两之间inverse的数量。计算ab的inverse可以通过将其中一个视为新定义的顺序，计算另一个在这种意义顺序下的逆序对数。O(nlogn)。
暴力的做法：将一个值在每个序列中出现的位置视为一维坐标，相当于给定三维空间中n个点，求完全小于的点对数。将其中一维视为时间后，即可以用二维数据结构解决。这个做法可以继续推广到更高维。O(nlog^2^n)。
=== H. Hole in One [sfiction] ===
枚举排列后用镜像法计算路线，然后判定合法性。O(n^2^n!)。

题解

EIJK 略去不表

A. Assigning Workstations [sfiction]

贪心将每个到达时间“连接”到离开时间上。O(nlogn)。

B. Better Productivity [sfiction]

如果a能覆盖b，那在最后加入a总能改进一个忽略a的方案。因此先处理出所有这些区间，对于剩下的区间求dp(i,j)为j个区间分成i段的最优解。枚举这些区间占多少个生产线，将之前忽略的区间中最大的单独放置于空闲生产线即可。注意相同区间需保留一个。O(pn²)。

C. Cleaning Pipes [sfiction]

每个管道为点，每个交点为一条边，当且仅当为二分图时有解。O(p²)。

D. Debugging [sfiction]

枚举运行次数，求最少的printf数，显然尽可能平均分配所得乘积最大，因此可以二分printf数，然后快速幂计算乘积。O(log³n)。

另一种做法：普通DP方程为O(n^1.5)，记忆化搜索即可，有很多无用状态，似乎为O(nlogn)。

F. Flight Plan Evaluation [sfiction]

对于每条航线，求出所有交点排序后计算长度即可。O(cnm)。

G. Guessing Camels [sfiction]

如果(x,y)在ab中顺序不同，称为一个inverse pair。如果(x,y)在三个序列中顺序都相同，则没有inverse pair，否则必然有两个inverse pair。因此只需计算三个序列两两之间inverse的数量。计算ab的inverse可以通过将其中一个视为新定义的顺序，计算另一个在这种意义顺序下的逆序对数。O(nlogn)。

暴力的做法：将一个值在每个序列中出现的位置视为一维坐标，相当于给定三维空间中n个点，求完全小于的点对数。将其中一维视为时间后，即可以用二维数据结构解决。这个做法可以继续推广到更高维。O(nlog²n)。

H. Hole in One [sfiction]

枚举排列后用镜像法计算路线，然后判定合法性。O(n²n!)。