题意：给出平面上的n个点，找到一个矩形，使得边界上包含尽量多的点 思路：如果单纯的枚举四条边再计数的话显然时间是不够的，，所以我们可以只枚举上下边界，用on[i],on2[i]表示竖线上位于上下边界之间的点数（区别在on[i]不统计位于上下边界上的点），这样，给定左右边界i,j的时候，矩形边界上的点数为left[j]-left[i]+on[i]+on2[j]，当右边界确定的时候，on[i]-le

【题目描述】 给定 MM 条边， NN 个点的带权无向图。求 11到 NN 的最短路。   【输入】 第一行：N,M(N≤100000，M≤500000)N,M(N≤100000，M≤500000)； 接下来MM行33个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。   【输出】

由于这两道题思路极其类似，在此统一记录： 108题.将有序数组转换为平衡二叉搜索树 思路：给定的数组已经升序排列，而二叉搜索树中序遍历的结果就是升序，但是仅凭中序遍历不能确定一颗二叉树，但是题目只是说将升序序列转换为平衡二叉搜索树，且答案不唯一，所以不要求确定，如何平衡呢？我们尽量保证左右子树一样多的节点不就可以吗？那么我们就能通过每次取数组最中间的元素作为二叉树节点最终就能构建整个平衡二叉搜

车 Description 在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。 Input 第一行为棋盘的大小n 第二行为障碍的数量m 第三行到第m+3为m个障碍 Output 总数 Sample Input 421 12 2 Sample Output 14 解题思路 这是一道 状态压缩动态规划

算是BST经典问题。另外一个相关的是面橘色打车软件时被问过：判断一个BST是不是平衡的。回到问题，这题我用了笨办法，把全部节点的value拿出啦，sort之后，每次用最中间的值。以此思路递归。 # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, righ