第一周的分治章节oj，里面很多“找规律”题，只能说递推这块勉强能算得上分治，评价为放水。另外里面足足有四道题来自于HDUoj，后面由于亚运会进入重保，这四道题均无法提交。当然即便如此，同学们依然可以靠其余6道题拿到作业满分。难道这也在你的计算之中吗，助教！

A 究极快排

给出一个无序正整数组，你需要不断交换其中相邻的两个直至数组有序。

求最小交换次数。

题解

根据题意，本题只能使用归并排序，在合并操作中，我们可以直接通过交换操作合并，替代原有的新开数组+双指针。

合并时如何计算交换次数？左侧每个数分别与右侧数比较，插入位置即为需要交换的次数。

我们如何证明归并排序下这样计算交换次数为最小交换次数？我们使用归纳法证明。最小子问题合并显然时最小次数；当第n次合并时，n-1次交换后分块均为有序的，易得左侧数从右往左依次交换到合适位置交换次数最少（只有这样才能避免左侧分块内部的冗余交换）。

同样地，由于有有序数组的冗余交换，我们可以证明其他排序无法得到最小交换数。

开始做的时候一直没有注意到交换必须相邻。

B 不用递归的汉诺塔

现有一新汉诺塔：圆盘按放的顺序标序号，每个柱子上相邻的圆盘序号和为平方数。给出汉诺塔的柱子数。

求最多能放几个圆盘。

题解

找出递推规律后一行完事。

设柱子数为n，公式为n2−ceil((n−1)2/2))n^2-ceil((n-1)^2/2))。

首先我们发现每个柱子最多放平方个圆盘，但其中有一些因为搁在其他的圆盘底下，无法和剩下圆盘凑出平方数。我们减去的就是这些圆盘。

C 不用递归的斐波那契数列

给出数列第0、1项的斐波那契数列。

求数列第n项能否被3整除。

题解

递推式两侧同余，找规律完事。

D 交叉线平分点问题

平面上给出4n个整数数组表示点坐标，两条交叉的直线平分这些点为4份。

分别求穿过两条线的两个点，如果没有则输出-1。

题解

计算几何。首先我们容易想到可以沿x轴或者y轴平分这些点，然后再来一条分别平分剩下的点。

剩下一条线我们可以通过分治找到：

  • 定义一个最小的移动单位ϵ\epsilon。每次直线至少旋转这么多，否则视为同一条直线。

  • 定义一个下限。容易想到先沿x轴平分方面进行分治，我们将顺时针旋转π−ϵ\pi-\epsilon定义为斜率下界

  • 开始divide，平分上下限的直线l计算两侧在l上下的分部。当左侧先超过n/4个点在上部时在斜率需要增大，否则减小。

由于我们求投影的时候需要求过该点与l平行的直线和第一条直线的交点的纵坐标作为投影，第一条直线不能垂直，否则求不到交点。我们设斜率为π−ϵ\pi-\epsilon。

  • 最终我们能找到一条直线满足题意，或者发现上下限比ϵ\epsilon还小时还找不到，返回-1。

E 防火网

在一个小于4×4大小的方形网格上，布置着一些墙和防御工事，两者均占一个格子。防御工事不能在同一行或同一列。输入网格的大小和墙的布置情况。

输出最多可以布置的防御工事数量。

题解

第一种想法：深度搜索。扫描整个网格，每次可以设置该网格是否能布置防御工事，经过check以后可以则设置为可以并且深度搜索下一个网格，否则设置为不可设置并深度搜索下一个网格。

check时只用看前面和上面的网格。

布置防御工事情况后需要设置不布置网格并再次进行深度搜索。

第二种想法：匈牙利匹配 to

F 格力兰岛

在一个m×n的方形网格中，每个网格四个顶点互相连接。连接的地方边长度为1，对角线的地方为2\sqrt{2}。给出m和n。

求经过所有点并回到起点的最短路径长度。

题解

本来以为要用分治方法求旅行商问题，但其实可以证明该长度有通解。m×n为偶数时，mn即为最短路径；否则为mn−1+2mn-1+\sqrt{2}。

由于以上路径更改任意一条长度都会变大，易得均为最短路径。

G 最大子数组和

给出一个含整数的数组，找出最大的连续子数组，使得它们的和最大。

给出最大子数组和。

题解

经典动态规划（所以为什么放到分治章节）。

我们令dp[i]为保存第i个数结尾的最大子数组和，递推式为：

dp[i]={array[i]if dp[i−1]<0dp[i−1]+array[i]if dp[i−1]≥0dp[i]=\left\{\begin{array}{lrl}array[i] && if\ dp[i-1]<0\\dp[i-1]+array[i] && if\ dp[i-1]\ge 0\\\end{array} \right.

dp[i]的定义比较反直觉，需要将原问题转化为每个数字结尾的子数组和的最大值。

可以在循环中获得最大值。

H 高维空间分割问题

给出一个整数m。

计算m维空间下，n个m-1维的关于n的多项表达式的系数，从大到小输出，用假分数表示，分子分母已化简。

题解

又是计算几何。本次最麻烦的一道。

这道题可以分为两个部分，一个是需要找到计算多项式的通项表达式，根据表达式计算系数。 to

另外则是需要构造假分数的四则运算。

  • 分数结构体需要在构造函数中加入约分操作，调用gcd。
  • 重载加法，注意优化运算 to

由于计算过程中会有大数乘法，所以不仅需要考虑到最大分母18!的位数，我们可以直接设置为可以设置的最大整型数__int128。

需要输出最大次项后系数为0的系数，输出为0/1。

我们用正常四则运算计算整数部分（分子），并记录每一个m组合数的分母，等做加法前使用分数构造函数。这样可以避免使用分数的乘法和除法运算，直接利用构造函数的约分解决。

I 套圈问题

给出二维平面整数点坐标。

求能够至少套中其中两个点的最小的圆的半径。

题解

即最小距离点对的距离的一半。算法详见课件。

如果发现两个点重合，可以提前返回。

J 计算得分数

给出两个整数非负整数，前者是两个数的和，后者是两个数差的绝对值。

求这两个数，如果不是非负整数则输出impossible。

题解

水题不解释。

注意考虑可能不为整数的情况。