接上一篇文章

sgu126. 每次都从大盒子移向小盒子即可，可以证明移动次数是logn级别的。

sgu127. 简单题，直接做即可。

sgu128. 经典的线段树题。根据，其实蛇的形状一开始就是固定的，宽搜可以确定是否全部连通，再通过离散扫描的方法可以判断其是否有相交的情况。

sgu129. 计算几何

sgu130. k条线切成k+1块明显是最优解。只要求方案数f[k]即可。考虑用和点1相连的另一个点编号来划分，可以得到f[k] = sigma(f[j]*f[k-1-j], 0<=j<=k-1)。用long long存放结果即可。

sgu131. 状态压缩DP， Topcoder最喜欢的风格之一。可以Topcoder上找到各种写得非常巧妙的类似程序。

sgu132. 状态压缩DP， 和上题思路差不多

sgu133. 按左端点排序，再维护右端点升序，看有多少不满足条件的点即可。复杂度为排序O(nlogn) + 扫描O(n)

sgu134. 建树，然后计算出每个子树t的结点数size[t]，则删去点t的结果就是max(n – size[t], size[child{t}])， 找出其中最小的， 将对应的点输出即可。

sgu135. 推导， 找规律， 归纳法都行， 答案为n*(n+1)/2 + 1， int64 留意

sgu136. x y可以分开算。现只考虑x怎么算

假如知道x0， 则容易得到x1，同理易得x2…… 这样就可以计算出xn，x0==xn即有解。

n为偶数的时候可以任意指定x0， n为奇数的时候因为全部中点x的总和正好就等于全部顶点x的总和。用这个和减去适当的项(全部中点坐标偶数项的2倍)也就可以计算出x0了。

sgu137. 非常nb的构造题， 一般问题很容易转化为构造k < n，由0, 1构成的序列。 需要经过一些推导，最后枚举公式中的参数，这样来得到可行的解。鉴于这是较早所做，所以详细的记录没有找到，有点可惜。 强烈推荐

sgu138. 因为总场数是一定的，我们只确定每一场赢的是谁即可，一路贪心下来，最后再把输的那些地方填满即可。超可爱的构造方法。

sgu139. 如果该状态可达，当且仅当该局面的逆序数+0的位置和起点奇偶[lrj]。

sgu140. 宽搜即可。初始状态为0， 每次转移为s –> s+a[i] % p。注意状态只有0~p-1这p种

sgu141. 又是一道线性同余方程。

sgu142.  长度为19的串就>=50万种了，所以答案不超过19，而且可以二分。 然后扫描统计即可。我统计时使用了1<<k大小的hash表。

sgu143.  朴素的树形DP。

sgu144.  概率题 令 t = (y - x) * 60， u = (t - z) / t ， ans = 1-u*u

sgu145.  求第K优的方案的问题。可以用经典的Dijkstra变种来解决。

sgu146.  简单题，细节问题郁闷了好久。

sgu147.  数学题， 尚不会。

sgu148.  枚举 + 堆栈维护决策。 细节待补充，忘了当时怎么过的来着了。

sgu149.  找树中最长链，简单的分治。 先选根建树，求出每个点的深度。经过根的最长链就是两个最深的子树深度和+1。不经过根的在格子树中同样求即可。

sgu150. 未读遗留。