算法竞赛（Python）-大事化小，小事化了（分治）

前言

  分治思想：将一个大问题分词几个小问题，小问题再分成几个更小的问题。一直这样分割下去，只要问题足够小，就可以很简单地被解决，然后再将小问题合并，就可以简单地解决原本的大问题。
  分治和动态规划的区别：分治是把大问题分解成小问题，再把小问题的答案成为大问题的答案；而动态规划是定义状态与状态的转移过程，从已知状态转移到新的状态。如果把动态规划中状态转移的过程理解为小问题合并为大问题，其实也可以把动态规划当作分治。
  但还是会把动态规划单独拿出来说，一是动态规划状态转移的过程是自底向上的，而分治的过程是自顶向下的；二是因为具体解题中分治和动态规划确实思路上不太一样，分治更多是递归回溯，动态规划更多是循环枚举。

一、数乘型分治

1 疯狂的细胞分裂

  小余最近对生物学产生了浓厚的兴趣，这天，小余获得了一个可以无限分裂的海拉细胞。每个细胞经过一天后会变成两个细胞，细胞不会死亡且可以持续分裂。
  这些细胞是珍贵的研究资源，必须用培养皿保存起来，但实验室有无数个培养皿，小余可以把所有的细胞都放进培养皿里，不过每一个培养皿最短只能放10亿(10⁹）个细胞。由于培养皿很贵，只有把一个培养皿放满了才会用新的。
  现在已经分列到了第n天，小余决定把所有细胞都放进培养皿。现在有一个有趣的问题，有多少细胞处于没有放满的培养皿中？
  输入格式：一个整数n，数据范围1≤n≤10¹³ 。输出格式：一个整数，表示处于没有放满的培养皿中的细胞数量。
样例：输入32；输出147483648
  在第1天，有1个细胞；在第2天变成了1x2个；第3天，它们变成了1x2x2个，…很明显，随着天数增长，细胞数量呈指数增长，即第n天，会有细胞2^n-1个。
  接着把2^n-1 除以1000000000，得到的余数就是处于没有放满的培养皿中的细胞。2^n-1 %1000000000。
  理论上答案就是这么简单，但是，这个值很难计算。请注意题目中的数据范围：1≤n≤10¹³ 。如果直接求2的指数函数，还没有循环几次，就会产生溢出，即使用64位整数也无济于事，这会导致最终得到的结果是错误的；另外n非常大，即使能计算2^n-1，程序也会超时、
  首先，来解决溢出的问题。其实取余数运算有一些数学性质，可以解决这个问题，那就是分配律。

  下面图中式子中2%10⁹ =2.所以省掉了 。

  在每一次乘法结束后，都对结果取余数，就可以保证数值处于[0,10⁹-1]的范围内，永远不会有溢出的问题。

mod=1e9
#计算x^n%mod
def power(x,n):ans=1for i in range(n):ans=(ans*x)%modreturn ans#求解
#power(x,n-1)
print(power(2,32-1)) #输出147483648

  这样就解决问题了？显然没有，还有一个很大的问题，就是超时了。接下来用到分治，来降低时间复杂度。
  power函数的目标是计算2的n次方，可以将这个问题分解成两个小问题，分别是计算2的[n/2]（[x]表示取x的整数部分）次方和计算2的n-[n/2]次方，然后再将这两个小问题的结果合并，两个数相乘得到2的n次方。这个过程可以递归地进行，递归的边界就是问题被分到不能再分的情况，即n=0和n=1.此时答案为2⁰=1,2¹=2。

import sys
sys.setrecursionlimit(100000) #这里设置递归深度为十万mod=1e9
#计算x^n%mod
def power(x,n):#递归的边界x^0=1,x^1=xif n==0:return 1elif n==1:return x#m=n//2取整m=n//2#计算x^ma=power(x,m)#计算x^(n-m)b=power(x,n-m)#x^n=(x^m)*(x^(n-m))return a*b%mod#求解
print(power(2,32-1))

  现在的代码，运行起来依然很慢。因为这样的分治其实没有降低时间复杂度，但新的处理形式会带来新的解决思路。比如，现在把大问题拆成多个小问题，交给多个人来完成，实际上工作量之和并没有变，但如果大家可以交流经验，避免重复劳动，结果就不一样。
  当n是偶数时，[n/2]=n-[n/2],所以两个小问题是完全相同的，只需要计算一次就足够了；当n是奇数时把其中的一个“1”单独留出来，也就是把n拆分成三个小部分——[n/2]、[n/2]、1，前两个又是完全相同的小问题，这样一来，总能把大问题拆分成小问题，且只有一个小问题是需要深入继续计算的。

mod=1e9
#计算x^n%mod
def power(x,n):#递归的边界x^0=1,x^1=xif n==0:return 1elif n==1:return x#m=n//2取整m=n//2a=power(x,m)if (n%2==0):#如果是偶数，那么x^n=(x^m)*(x^m)return a*a%modelse:#如果是奇数，x^n=(x^m)*(x^m)*x^1return a*a%mod*x%mod#求解
print(power(2,32-1))

二 矩阵乘法的分治

1 神秘数字

  在如今使用互联网服务时，通常要使用各种各样的账号和密码，如果注册太多账号，很容易忘记密码。这天，小余忘记了自己的某个账号，只记得密码是一个n位的数字，且这个数字中6出现的次数为偶数，无奈之下，小余只能一个一个地尝试，请你计算有多少种可能。
  输入格式：一个整数n。表示数字的位数。输出格式:一个整数，表示可能的密码数量，由于答案可能很大，需输出其除以10⁹+7的余数。样例输入：2，样例输出：73。

  思路：
  第1步：定义状态。关键的信息是数字的位数以及其中6出现的次数，用f(i,0)表示前i位数字中6出现的次数为偶数时，前i位数字有多少种可能；相应地，用f(i,1)表示前i位数字中6出现的次数为奇数时，前i位数字有多少种可能。
  第2步：确定转移关系。前i位的状态显然要根据前i-1位的状态计算，如果第i位是6，那么6出现的次数从偶数变为奇数，或者从奇数变为偶数；如果第i位是除了6之外的其他9个数字之一，那么6出现次数的奇偶性不变。

  第3步：构造状态转移方程

mod=1e9+7
f=[[0,2] for i in range(30)]
n=2
def main():#初始化f[0][0]=8f[0][1]=1#动态规划for i in range(1,n):f[i][0]=(9*f[i-1][0]+f[i-1][1])%modf[i][1]=(f[i-1][0]+9*f[i-1][1])%mod#输出
main()
print(f[n-1][0])

  完整的操作结束后，复杂度也随之爆炸了。虽然时间复杂度只有O(n),但本题的n达到了10¹⁸。
  要优化这段程序，需要把状态转移方程写成矩阵形式：

  由以上公式可知，只需要在左侧乘以一个矩阵，就能从前i-1位的状态转移到前i位的状态。如果这个矩阵乘两次。就可以转移到前i+1位的状态，如果乘以n次，就可以转移到前i+n-1位的状态。

import numpy as np#计算矩阵的n次方
def power(x,n):""":param x: 矩阵:param n: int:return:"""ans=np.array([[1,0],[0,1]]) #单位矩阵while n>0:if n%2==1:ans=np.dot(ans,x) #dot矩阵乘法n=n//2 #取整x=np.dot(x,x)return ansA=np.array([[9,1],[1,9]])
n=2
mod=1e9+7
power_n=power(A,n-1)
ans=(power_n[0][0]*8+power_n[0][1])%mod
print(ans)

三 、线性结构问题的分治

1 自助餐厅（1）

  小余的朋友新开了一家自助餐厅，恰好他的生日到了，小余一家被邀请前往这家自助餐厅参加朋友的生日宴。这家自助餐厅今晚为客人们准备了n道菜品，按照顺序排放在一条长长额传送带上，但是这家餐厅有一个奇怪的规定：每位客人只能享用相邻的若干道菜品。
  小余对于菜品有一定的偏好，第i道菜品具有a_i 的美味度，小余想要吃到美味度之和最大的菜品。某些菜品是小余不喜欢吃的，所以美味度可能是负数，但是小余认为浪费粮食可耻，所以一旦选好了若干道相邻的菜品，就一定会全吃完。如果没有想吃的菜（所有菜品的美味度都是负数），小余可以选择不吃。
  现在，请你帮助小余选出美味度之和最大的若干道菜品。
  输入格式：n=8代表菜的道数。a=[-1,2,8,-2,4,-2,0,1]。a_i代表第i道菜的美味度。输出12。

分治思路：
  第1步：先把这n道菜品从中间分成两部分。
  第2步：分成左右两部分之和，菜品的选取方式可以分为三种：

   对于第1种方式，实际包含n/2n/2个可行的取法。如果某种取法的美味度最大，那么它的左半部分是美味度最大，右半部分也是美味度最大的。
  所以，不必尝试所以n/2n/2种取法，先在左边的n/2种取法中选出美味度最大的，再在右边的n/2种取法中选出美味度最大的，最后合并起来，就是美味度最大的取法，这个过程的时间复杂度为O(n)。对于第2种和第3种取法，可以递归方式处理。

n=8#代表菜的道数。
a=[-1,2,8,-2,4,-2,0,1]#ai代表第i道菜的美味度。#求区间a[l],a[l+1],...a[R-1]中能够选取到的最大美味度之和
def max_sum(l,R):""":param l: int:param R: int:return:"""#如果区间长度只有1，直接得到答案，结束递归if l==R-1:return max(a[l],0)#以中点为界，切分成左右两部分mid=(l+R)//2#求出横跨左右两部分的取法中的最大美味度l_sum=0;r_sum=0;sum=0for i in range(mid-1,l-1,-1):#[mid-1,l] # 左边sum+=a[i]if sum>l_sum:l_sum=sumsum=0for i in range(mid,R):#[mid,R)#右边sum+=a[i]if sum>r_sum:r_sum=sumans=l_sum+r_sum#求出只在左半部分的取法中最大的美味度ans=max(ans,max_sum(l,mid))#求出只在右半部分的取法中最大的美味度ans=max(ans,max_sum(mid,R))return ansif __name__=="__main__":print(max_sum(0,n))

  本题也可以用动态规划算法解决。用f(i)表示以第i道菜最后一道菜时，可以取到的最大美味度之和，状态转移的方式很简单，如果只取第i道菜，那么f(i)=a；如果取了第i-1道菜之和继续取第i道菜，那么f(i)=f(i-1)+a。状态转移方程f(i)=max(a_i,f(i-1)+a_i)。

n=8#代表菜的道数。
a=[-1,2,8,-2,4,-2,0,1]#ai代表第i道菜的美味度。
f=[0 for i in range(n)] #f[i]表示以第i道菜最后一道菜时，可以取到的最大美味度之和
def main():f[0]=max(a[0],0)ans=0for i in range(1,n):f[i]=max(a[i],f[i-1]+a[i])if f[i]>ans:ans=f[i]return ansif __name__=="__main__":print(main())

2 自助餐厅（2）

  小余的朋友为了提高客人们的用餐体验，决定把餐厅的自助模式改为套餐模式，一份套餐包含三道菜——前菜、正餐、甜点。美味度为a₀,a₁,…a_n-1的n道菜通过传送带依次送出，服务员需要为每位客人选取三道菜组成套餐。每一道菜都可以作为前菜、正餐、甜点，如果选取第i、j、k道菜分别作为前菜、正餐、甜点，那么必须满足以下两个条件。

• (1)三道菜必须按照顺序端给客人，即i<j<k。
• (2)为保证用餐体验三道菜的美味度必须依次递增。即a_i≤a_j≤a_k。
    现在的问题是，有多少种组成套餐的方式。;输入格式：n=8代表菜的道数。a=[3,-2,6,1,-1,0,5,2]。a_i代表第i道菜的美味度。输出9。
    这是一个很经典的三元有序对问题，也就是计算有多少递增的三元组。对于这道题，有一个最朴素的做法就是使用三重循环，分别利用三重循环穷举数字a_i，a_j，a_k。然后比较是否满足条件，统计满足条件的次数。这样做法复杂度太高，不能通过这道题。
    分治思路：
    第1步：归并排序将数字分成左右两部分，递归处理这部分，利用递归分别将这两部分排序完之后，再将这两部分合并。时间复杂度O(nlogn）。
  
    第2步：如果一道菜作为正餐，可以搭配出多少种套餐？就需要计算有多少道菜可以成为它的前菜，以及有多少道菜可以成为它的甜点。即需要计算左边有多少小于或等于它的数值，以及右边有多少大于或等于它的数值，能够搭配出的套餐就是两者的乘积。
  

n=8#代表菜的道数。
a=[3,-2,6,1,-1,0,5,2]#ai代表第i道菜的美味度。
a_temp=[0 for i in range(n)]#临时变量
index=[i for i in range(n)]#菜品原来的编号
index_temp=[0 for i in range(n)]#临时变量
low=[0 for i in range(n)]#low[i]表示有多少菜品可以作为第i道菜的前菜
high=[0 for i in range(n)]#high[i]表示有多少菜品可以作为第i道菜的甜点def mergesort(L,R):""":param L: int:param R: int:return: 归并排序结果"""if R-L<=1:return Nonemid=(L+R)//2mergesort(L,mid)mergesort(mid,R)p1=L;p2=mid;tot=Lwhile(p1<mid or p2<R):#判断接下来对那个数字归并merge_left=0if p2==R:merge_left=1 #左边elif p1==mid:#右边merge_left=0elif a[p1]<=a[p2]:merge_left=1else:merge_left=0if merge_left:#归并左侧数字index_temp[tot]=index[p1] #索引a_temp[tot]=a[p1] #值high[index[p1]]+=R-p2tot+=1p1+=1else:#归并右边的数字index_temp[tot]=index[p2]a_temp[tot]=a[p2]low[index[p2]]+=p1-Ltot += 1p2 += 1#将临时变量数组中的数据放回原数组for i in range(L,R):a[i]=a_temp[i]for i in range(L,R):index[i]=index_temp[i]if __name__ =="__main__":#求解mergesort(0,n)ans=0for i in range(n):ans+=low[i]*high[i]print(ans)

四 、树形结构的分治

1 二叉树的最大深度

class TreeNode(object):def __init__(self,x):self.val=xself.left=Noneself.right=None# 将数组转为完全二叉树
def array_to_bitree(array):if len(array) == 0:return TreeNode(None)root = TreeNode(array[0])node_list = [root]for i in range(1, len(array)):val = array[i]if val != None:node = TreeNode(val)node_list.append(node)if i % 2 == 1:node_list[int((i - 1) / 2)].left = nodeif i % 2 == 0:node_list[int((i - 2) / 2)].right = nodeelse:node_list.append(None)return root#树的最大深度
class Solution(object):def maxDepth(self,root):if root==None:return 0else:return 1+max(self.maxDepth(root.right),self.maxDepth(root.left))if __name__ =="__main__":array = [3, 9, 20, None, None, 15, 7]root = array_to_bitree(array)c = Solution()print(c.maxDepth(root))

解释：完全二叉树。根结点为0。针对任何一个节点i，左孩子为2i+1,右孩子2i+2.