不骗你，没读这一篇，你不可能懂二分

女爷i 2022-11-12 02:34 142阅读 0赞

> 上篇文章讲动态规划获得了80k浏览，这次的二分也值得你们一看，这个系列是特别用心写的，准备出书的哦

[动态规划][Link 1]

# 3.0 引子 #

图书馆自习的时候,一女生背着一堆书进阅览室,结果警报响了,大妈让女生看是哪本书把警报弄响了，女生把书倒出来，一本一本的测。大妈见状急了，把书分成两份,第一份过了一下,响了。又把这一份分成两份接着测，三回就找到了，大妈用鄙视的眼神看着女生，仿佛在说 O(N)和 O(logN）都分不清。

这就是二分法。（欲知故事后续，请继续往下看）

# 3.1 经典二分问题 #

经典二分问题：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target 。

写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。  
**示例 1:**

输入: nums = \[-1,0,3,5,9,12\], target = 9。输出: 4  
解释: 9 出现在 nums 中并且下标为 4  
**示例 2:**

输入: nums = \[-1,0,3,5,9,12\], target = 2。输出: -1  
解释: 2 不存在 nums 中因此返回 -1

**思路1：**我们当然可以一个数一个数的遍历，但是毫无疑问要被大妈鄙视，这可怎么办呢？

**思路2：**二分查找  
二分查找是一种基于比较目标值和数组中间元素的教科书式算法。

如果目标值等于中间元素，则找到目标值。  
如果目标值较小，证明目标值小于中间元素及右边的元素，继续在左侧搜索。  
如果目标值较大，证明目标值大于中间元素及左边的元素，继续在右侧搜索。

**算法代码描述：**

初始化指针 left = 0, right = n - 1。  
当 left <= right：  
比较**中间元素** nums\[pivot\] 和目标值 target 。  
如果 target = nums\[pivot\]，返回 pivot。  
如果 target < nums\[pivot\]，则在左侧继续搜索 right = pivot - 1。  
如果 target > nums\[pivot\]，则在右侧继续搜索 left = pivot + 1。

算法实现：照例贴出三种语言的实现，在Java实现中给出了详细注释

class Solution {
      public int search(int[] nums, int target) {
    	//分别准备好左右端点
        int left = 0, right = nums.length - 1;
    	//循环二分
        while (left <= right) {
    	//取中点
          int pivot = left + (right - left) / 2;
    	  //找到答案并返回
          if (nums[pivot] == target) return pivot;
    	  //向左继续找
          if (target < nums[pivot]) right = pivot - 1;
    	  //向右继续找
          else left = pivot + 1;
        }
    	//未找到，返回-1
        return -1;
      }
    }

class Solution:
        def search(self, nums: List[int], target: int) -> int:
            left, right = 0, len(nums) - 1
            while left <= right:
                pivot = left + (right - left) // 2
                if nums[pivot] == target:
                    return pivot
                if target < nums[pivot]:
                    right = pivot - 1
                else:
                    left = pivot + 1
            return -1

class Solution {
      public:
      int search(vector<int>& nums, int target) {
        int pivot, left = 0, right = nums.size() - 1;
        while (left <= right) {
          pivot = left + (right - left) / 2;
          if (nums[pivot] == target) return pivot;
          if (target < nums[pivot]) right = pivot - 1;
          else left = pivot + 1;
        }
        return -1;
      }
    };

请记住这个代码，因为整篇文章，整个二分思想，都和这段代码息息相关，这也是最基础的二分问题。

# 3.2 基础二分小变形1 #

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

思路：我们注意，这一题和上一题的区别在于，这一题并不存在**‘没找到’**这种情况，因为要插入到**”第一个比目标值大的数“**的左边，返回这样一个插入位置，你不可能**”找不到“，**不可返回-1。

事实上，我们的目标也再不是找到一个**相同的数字**，而是找到第一个比目标值大的数，也就是插入位置。

![20200419165149902.png][]

而我们第一段代码的返回答案也可以省略了，代码的内部逻辑是**”一路找到最后，返回的一定是答案“，**而上段代码的逻辑是**”边找边判断，找到最后还没有找到，就返回-1“。**

下面是代码：

public class Solution {
        public int searchInsert(int[] nums, int target) {
            int len = nums.length;
            int left = 0;
            int right = len - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return left;
        }
    }

**提醒：所以，如果你是一个想注重细节，做到写二分代码不出错，那么你就需要关心最后返回值，while结束条件，while内部是否加判断等等这些细节了。**

# 3.3基础二分小变形2 #

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 \[-1, -1\]。

示例 1:输入: nums = \[5,7,7,8,8,10\], target = 8输出: \[3,4\]  
示例 2:输入: nums = \[5,7,7,8,8,10\], target = 6输出: \[-1,-1\]

思路：两个二分，稍微改一下，就可以找到第一个target或最后一个target；

本元素和前面一个元素不相等，才代表找到了最左边的目标元素。

本元素和后面一个元素不相等，才代表找到了最右边的目标元素。

class Solution {
        public int[] searchRange(int[] nums, int target) {
            int[] ans=new int[2];
            ans[0]=searchRangeLeft(nums,target);
            ans[1]=searchRangeRight(nums,target);
            return ans;
        }
        public int searchRangeLeft(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(nums[mid]>target){
                    right=mid-1;
                }else if(nums[mid]<target){
                    left=mid+1;
                }else if(mid==0 || nums[mid-1]!=target){
                    return mid;
                }else{
                    right=mid-1;
                }
            }
            return -1;
        }
        public int searchRangeRight(int[] nums, int target) {
            int left=0;
            int right=nums.length-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(nums[mid]>target){
                    right=mid-1;
                }else if(nums[mid]<target){
                    left=mid+1;
                }else if(mid==nums.length-1 || nums[mid+1]!=target){
                    return mid;
                }else{
                    left=mid+1;
                }
            }
            return -1;
        }
    }

注意：如果你找到一个target，然后向左向右线性查找是不对的，这样时间会退化为O(N)，和二分的本意违背了。

# 3.4泛化二分的概念 #

看到第一节，可能大部分人都没有问题；

看到第二节，可能对有些写二分总有bug的同学有一些帮助，会觉得”细节确实需要注意“，二分查找从此要一次就bug free；

至此，我们看一下百度百科对二分的定义：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

简单来说，我们介绍的就是在顺序存储结构（数组）有序的情况下进行二分查找。

从第四节开始，我们介绍的就不是传统意义上的二分查找了，不局限于”有序“，甚至不局限于线性结构，while循环里判断向左还是向右搜索的条件也不会这么单一，而更可能是这样：

while (范围没有缩小为0) \{  
if (满足某种条件) \{  
排除一半答案  
\} else \{  
排除另一半答案  
\}  
\}

我们的思想是：只要可以通过正确逻辑，用二分思想正确的缩小查找范围，都称之为二分。

下面就来体会一下什么是二分思想：

我们正在玩一个猜数字游戏。 游戏规则如下：  
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。  
每次你猜错了，我会告诉你这个数字是大了还是小了。  
**你调用一个预先定义好的接口 guess(int num)**，它会返回 3 个可能的结果（-1，1 或 0）：

\-1 : 我的数字比较小  
1 : 我的数字比较大  
0 : 恭喜！你猜对了！  
示例 :

输入: n = 10, pick = 6输出: 6

/* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    
    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int low = 1;
            int high = n;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                int res = guess(mid);
                if (res == 0)
                    return mid;
                else if (res < 0)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            return -1;
        }
    }

你看，这就是把条件抽象成一个接口，完全脱离了线性数据结构，更和有序无序没关系，只是二分的思想。

# **3.5在线性结构上二分的题目积累** #

**例1**

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums\[i\] ≠ nums\[i+1\]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums\[-1\] = nums\[n\] = -∞。

示例 1:输入: nums = \[1,2,3,1\]输出: 2  
解释: 3 是峰值元素，你的函数应该返回其索引 2。  
示例 2:输入: nums = \[1,2,1,3,5,6,4\]输出: 1 或 5  
解释: 你的函数可以返回索引 1，其峰值元素为 2；  
或者返回索引 5， 其峰值元素为 6。  
**说明:你的解法应该是 O(logN) 时间复杂度的**。

思路：

**可以用二分的要求：线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果即可，不一定非要有序**

具体到本题来说，我们如何做到搜索到任何一个“峰值”呢？请看图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

要先有上升的趋势，后有下降的趋势。更通俗一点就是说，要保证前一个数字比峰值小，后一个数字比峰值大，我们只要每次搜索都满足这个条件，搜到最后就一定可以找到某个峰值，**因为从递增到递减，肯定是因为中间有峰值的存在所导致的**。

![20200419173411749.png][]

我们看中点，如果中点向右有递增趋势，我们就继续搜索右边：

![20200419173858555.png][]

反之，有向左递增的趋势，我们就搜左边：

![20200419174316860.png][]

下面给出代码：

public class Solution {
        public int findPeakElement(int[] nums) {
            int l = 0, r = nums.length - 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (nums[mid] > nums[mid + 1])
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        }
    }

我们发现，这个题目的代码逻辑就是第二节的**”一路找到最后，返回的一定是答案“，**不同于最基础的二分**”边找边判断，找到最后还没有找到，就返回-1“。**我们是缩小范围到最后，找到了答案l。

**例2：**

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: \[3,4,5,1,2\]输出: 1  
示例 2:

输入: \[4,5,6,7,0,1,2\]输出: 0

**分析：**

如果数组没有翻转，即 nums\[left\] <= nums\[right\]，则 nums\[left\] 就是最小值，直接返回。

如果数组翻转，需要找到数组中第二部分的第一个元素：

![20200419212807259.png][]。

下面讨论数组翻转的情况下，如何收缩区间以找到这个元素：

若 nums\[left\] <= nums\[mid\]，说明区间 \[left,mid\] 连续递增，则最小元素一定不在这个区间里，可以直接排除。因此，令 left = mid+1，在 \[mid+1,right\] 继续查找。

![20200419212839979.png][]

否则，说明区间 \[left,mid\] 不连续，则最小元素一定在这个区间里。因此，令 right = mid，在 \[left,mid\] 继续查找  
\[left,right\] 表示当前搜索的区间。

**注意 right 更新时会被设为 mid 而不是 mid-1，因为 mid 无法被排除。**

class Solution {
        public int findMin(int[] nums) {
            if(nums.length==1)return nums[0];
            if(nums[0]<nums[nums.length-1])return nums[0];
            int left=0;
            int right=nums.length-1;
            int mid=0;
            while(left<right){
                mid=(left+right)/2;
                if(nums[mid]>=nums[0]){
                    left=mid+1;
                }else{
                    right=mid;
                }
            }
            return nums[right];
        }
    }

**例3：**其它条件和例2一样，例3要搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

思路：（请先自行思考）

先通过例2的方法找到分割点，再对左右某一边进行二分即可，代码请自行书写。

# 3.6二维数组的二分查找 #

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。  
每行的第一个整数大于前一行的最后一个整数。  
**示例 1:**  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 3  
输出: true  
**示例 2:**  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 13  
输出: false

仔细观察我们发现，其实这个二维数组整体就是有序的，所以当成一维数组二分查找即可，但是要注意二维数组的操作，需要一点功底。

class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return false;
            }
            int row = matrix.length;
            int col = matrix[0].length;
            int start = 0;
            int end = row * col - 1;
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (matrix[mid / col][mid % col] == target)return true;
                else if (matrix[mid / col][mid % col] > target)end = mid - 1;
                else start = mid + 1;
            }
            return false;
        }
    }

注意：这里有个细节：![2020041921384666.png][]正规的二分其实都应该这么写，之前的写法可能会溢出。

# 3.7二叉树上二分的题目积累 #

我们刚才学会了一些一维二维数组的二分操作，下面我们再去其它数据结构试试看，继续养成二分的思想。

**例1：先看一道简单的在二叉树上查找值。**

给定一个不为空的二叉搜索树和一个目标值 target，请在该二叉搜索树中找到最接近目标值 target 的数值。

注意：

给定的目标值 target 是一个浮点数，题目保证在该二叉搜索树中只会存在一个最接近目标值的数。  
示例：

输入: root = \[4,2,5,1,3\]，目标值 target = 3.714286

4  
/ \\  
2 5  
/ \\  
1 3

输出: 4

思路：二分，当前节点比target大就往左边搜（因为右边的差距更大），当前节点比target小就往右搜（因为左边的差距更大）。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
      public int closestValue(TreeNode root, double target) {
        int val, closest = root.val;
        while (root != null) {
          val = root.val;
          closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
          root =  target < root.val ? root.left : root.right;
        }
        return closest;
      }
    }

**例2**

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入:  
1  
/ \\  
2 3  
/ \\ /  
4 5 6

输出: 6

思路：如果不考虑最后一层，节点数完全可以算出来，每一层分别为1，2，4，8....你会发现是2的n次方，那么总和也很好求，所以问题就在于如何知道最后一层有多少节点，换句话说，最后一层的最右边的那个节点在哪里？我们需要二分搜索。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

**目标：找箭头指向的结点。**

我们采用二分法：

1）找到右子树的最左结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3][]

我们知道总深度为4，如果右子树深度为3（4-1），说明![20181120104136749.png][]图中最后的1是存在的（说明最后一行最右结点一定来自右子树），否则，如果我们修改一下如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 4][]

右子树深度为2！=4-1，不存在最后一行的结点。（说明最后一行最右结点一定来自左子树）.

**2）判断之后，如果是这种情况，我们排除了左子树，计算排除的结点个数，并对右子树（如图2）做相同的处理。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 5][]

更新结点数（未被框起的部分，满二叉树公式+1）+1是根结点

3）对方框内重复此过程。

![20181120105036702.png][]

我们继续看右子树，发现右子树深度为1！=3-1.

说明最深层最右结点来自于左子树。所以对左子树重复上述过程

![20181120105141501.png][]

我们发现，右子树深度=1=2（整棵树深度）-1，说明最深层最右结点来自于右子树，所以对右子树重复此过程。

![20181120105302551.png][]最终找到它。

public class Demo {
    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    //返回结点个数
    	public static int nodeNum(Node head) {
    		if (head == null) {
    			return 0;
    		}
    		return bs(head, 1, mostLeftLevel(head, 1));
    	}
    //返回根为node，当前层数为l，总深度为h的结点个数
    	public static int bs(Node node, int l, int h) {
    		if (l == h) {
    			return 1;
    		}
    		if (mostLeftLevel(node.right, l + 1) == h) {             //右子树最深一行最左为空
    			return (1 << (h - l)) + bs(node.right, l + 1, h);    //右bs+左子树结点个数
    		} else {                                                 //右子树最深一行最左不为空
    			return (1 << (h - l - 1)) + bs(node.left, l + 1, h);//左bs+右子树结点个数
    		}
    	}
    //计算树的高度
    	public static int mostLeftLevel(Node node, int level) {
    		while (node != null) {
    			level++;
    			node = node.left;
    		}
    		return level - 1;
    	}
    
    	public static void main(String[] args) {
    		Node head = new Node(1);
    		head.left = new Node(2);
    		head.right = new Node(3);
    		head.left.left = new Node(4);
    		head.left.right = new Node(5);
    		head.right.left = new Node(6);
    		System.out.println(nodeNum(head));
    	}
    }

我们再回忆第4节泛化概念时给的伪代码：

while (范围没有缩小为0) \{  
if (满足某种条件) \{  
排除一半答案  
\} else \{  
排除另一半答案  
\}  
\}

其实真的就是这样的，一个终止条件（本题就是l==h），一个if判断条件（本题就是mostLeftLevel(node.right, l + 1) == h），注意细节，就可以进行各种广义的二分啦。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 6][]

# 3.8数学中的二分 #

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4输出: 2  
示例 2:

输入: 8输出: 2  
说明: 8 的平方根是 2.82842...,  
由于返回类型是整数，小数部分将被舍去。  
思路依旧是二分，格式和上文都一样。

public class Solution {
     
        public int mySqrt(int x) {
            long left = 0;
            long right = Integer.MAX_VALUE;
            while (left < right) {
                long mid = (left + right + 1) >>> 1;
                long square = mid * mid;
                if (square > x) {
                    right = mid - 1;
                } else {
                    left = mid;
                }
            }
            return (int) left;
        }
    }

# **3.9最大化或最小化问题** #

**如果在求解最大最小问题中，能比较简单的判断某个解是否满足条件（这里的简单一般指的是o(n)及以下，视具体数据范围而定），使用二分搜索答案就能很好的解决问题。**

**举个例子，POJ1064**

题目链接：[http://poj.org/problem?id=1064][http_poj.org_problem_id_1064]

题目大意：有n条绳子，长度分别为L\[i\]。如果从他们中切割出k条长度相同的绳子的话，这k条绳子每条最长能有多长？（答案保留小数点后两位，规定1单位长度的绳子最多可以切割成100份）。

思路：二分搜索答案，每条最短0，最大设置一个较大的数，然后开始二分答案并依次判断，判断也很简单，判断每个绳子的长度整除答案的累加和是不是大于k就好了。

#include <cstdio>
    #include <cmath>
    using namespace std;
    const int M=10005;
    const double inf=200005.0;
    double L[M];
    int n,k;
    bool judge(double x)//判断解是否可行
    {
        int num=0;
        for(int i=0;i<n;i++)num+=(int)(L[i]/x);
        return num>=k;
    }
    void solve()//二分答案
    {
        double left=0,right=inf;
        for(int i=0;i<100;i++) //代替while(r>l) 避免了精度问题
        { //1次循环可以把区间缩小一半，100次可以达到10^(-30)的精度
            double mid=(left+right)/2;
            if(judge(mid)) left=mid;
            else right=mid;
        }
        printf("%.2f\n",floor(right*100)/100);
    }
    int main()
    {
        while(scanf("%d%d",&n,&k)!=-1)
        {
            for(int i=0;i<n;i++)scanf("%lf",&L[i]);
            solve();
        }
    }

**POJ2456**

题意：

有n个牛栏，选m个放进牛，相当于一条线段上有 n 个点，选取 m 个点，

使得相邻点之间的最小距离值最大

思路：和上一道题类似，二分答案，判断答案也很简单，贪心即可，遍历，遇到大于枚举的距离就放一只牛，看最后能不能放得下。

# 3.10总结 #

其实还有一些用到二分的，比如最大化平均值问题，但是由于篇幅和大部分读者水平和时间有限，暂时不写了，如果有时间还是会持续更新，

[Link 1]: https://fantianzuo.blog.csdn.net/article/details/100585136
[20200419165149902.png]: /images/20221022/feb8396f899d48d5bd587e7a26aa9aa6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200419170244820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200419172812242.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[20200419173411749.png]: https://img-blog.csdnimg.cn/20200419173411749.png
[20200419173858555.png]: https://img-blog.csdnimg.cn/20200419173858555.png
[20200419174316860.png]: https://img-blog.csdnimg.cn/20200419174316860.png
[20200419212807259.png]: https://img-blog.csdnimg.cn/20200419212807259.png
[20200419212839979.png]: https://img-blog.csdnimg.cn/20200419212839979.png
[2020041921384666.png]: https://img-blog.csdnimg.cn/2020041921384666.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20181120103833247.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20181120103947802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[20181120104136749.png]: https://img-blog.csdnimg.cn/20181120104136749.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20181120104221689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20181120104729409.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[20181120105036702.png]: https://img-blog.csdnimg.cn/20181120105036702.png
[20181120105141501.png]: https://img-blog.csdnimg.cn/20181120105141501.png
[20181120105302551.png]: https://img-blog.csdnimg.cn/20181120105302551.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200419220758201.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[http_poj.org_problem_id_1064]: http://poj.org/problem?id=1064