一起挑战pythontip的题目（22）

第106题：LTC-男人八题之一：连通图
题目描述：LTC不知道是谁？百度去！楼天成是也，楼教主当年提出来的男人八题系列，可谓经典中的经典。
言归正传，本题的任务是，请你计算，具有n个节点的无向连通图有多少种不同的形态。n是一个正整数，1 <= n <= 50,请输出结果。
如：
n=3时，输出：4
note：n=3，有如下四种不同的无向连通图
A-------B     A-------B      A       B       A-------B
 .    .        .              .     .               .
   . .           .              . .                .
    C             C              C                C
其中，'.'和'-'画出的线表示无向图的边，A,B,C表示三个顶点。
示例：输入：n = 1
输出：1

============================================================
第107题：LTC-男人八题之二：古老的取石子游戏
题目描述：游戏的开始有n个排成一条线的石子堆，游戏的目标是将这些堆石子合并成一堆，合并的规则如下：
Rule:每一步，游戏玩家只能合并相邻的两堆石子，得分是被合并的两堆石子数目之和。
你的目标是求出合并所有石子能够得到的最小得分之和。
给你一个正整数列表L,L中每个数字表示对应石子堆的石子数目，如L[0]表示第一个石子堆的石子数目，请你输出合并的最小得分之和。
如：
L=[100],则输出0
L=[3, 4, 3], 则输出17.
示例：输入：L = [100]
输出：0

============================================================
第108题：LTC-男人八题之三：旅游线路问题
题目描述：给你一张基于网格的M x N的城镇地图（1≤M, N≤8），有些格子禁止入内，用“#”表示，其余格子用“.”（一个点）表示。
现在你需要求出从左下角走到右下角，并且经过所有可以入内的格子一次且仅一次的路径的总数。
给你一个二维List L，表示城镇地图, L中的每个元素为'#'或'.',表示含义如上所述（注意N和M没给，可以由L得到)。
如：
L = [
      ['.', '.'],
      ['.', '.']
    ]
此时的地图为：
..
..
输出：1
L = [
      ['#', '.', '.'],
      ['.', '.', '.']
    ]
此时的地图为：
#..
...
输出：1
示例：输入：L = [[".", "."], [".", "."]]
输出：1

============================================================
第109题：LTC-男人八题之四：新式取石子游戏
题目描述：小明和小红参加一种新的取石子游戏。游戏开始时有 n （1 <= n <= 10)堆石子，参与游戏的两个选手轮流取走或移动石子。在每一轮中，选手选择一个石子堆
，从该堆石子中拿走至少一个石子。然后，该选手可以多次地从该堆中剩下的石子中把任意多的个石子移动到其它堆中。当然，该选手也可以不移动任何石子。但是，注意
，选手必须从选中的堆中取走至少一块石子。因此，随着游戏的进行，石子越来越少, 最后一个取完石子的人获胜。
现在给你一个正整数list L(L的长度不超过10），每个元素代表相应石子堆石子的数目，如L[0]代表第一堆石子的数目，
小明和小红都极其聪明，总能以最优的策略进行游戏。游戏从小明开始，请你判断小明能否在游戏中获胜？
若能获胜，输出：Yes否则输出：No
如：L = [2, 1, 3], 则输出Yes
    L=[1, 1], 则输出No
示例：输入：L = [2, 1, 3]
输出：Yes

============================================================
第110题：LTC-男人八题之五：树
题目描述：给你一个含有n个顶点的无向树，树上每条边都有一个长度p(p是不超过1001的正整数).
定义dist(u, v)表示节点u到v的最短距离。给你一个k，请你求出树上满足dist(u, v) <= k的点对数目，注意u不能和v相同。
给你一个正整数k和二维List L, 其中L中的每行是一个三元组[u, v, p],表示一条边,其中u和v表示节点，p表示长度，请你求出满足条件的点对数目。
示例：输入：k = 4
L = [[1, 2, 3], [1, 3, 1], [1, 4, 2], [3, 5, 1]]
输出：8

============================================================

来源：

Python 爬取pythontip网站的挑战题目（附全部题目178题）