程序员进阶之算法练习（十八）
前言
最近在接触新知识，也是选择2017年的方向。 其他文集更新会放缓，没有学习就没有心得，肚中无墨就无从下笔。 但是算法练习还是挺好玩的，欢迎关注algorithm文集。
正文
A. Bus to Udayland 题目链接 题目大意： 输入n行字符，每行5个字符； 表示公交车上n排位置，X表示有人，O表示空位，|是过道。 问是否能找到两个连续的空位； 如果可以，输出"YES"，并且空位改为++后输出； 如果没有输出"NO"; n (1 ≤ n ≤ 1000)
Example
input
5 XX|XX XX|XX XO|OX XO|OO OX|XO
output
YES XX|XX XX|XX XO|OX XO|++ OX|XO
** 题目解析：** 只有两种情况，前两个或者最后两个。 分情况讨论即可。
B. Chris and Magic Square 题目链接：http://codeforces.com/contest/711/problem/B 题目大意： 输入一个n*n的数组矩阵，在数字为0的位置填入一个正数（只有一个位置为0），让矩阵的行列对角线和相同。 如果没有答案输出-1； 如果答案，输出完整的矩形。 n (1 ≤ n ≤ 500)
Example
input
3 4 0 2 3 5 7 8 1 6
output
9
input
4 1 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1
output
-1
** 题目解析：** 看似很难，但是因为只有一个位置为0，题目简化许多。 我们假设存在答案，那么可以： 根据上一行和当前行的差值，可以计算出0应该填的数字。 再判断一下结果是否符合即可。
C. Coloring Trees 题目链接 题目大意： 有n棵树排成一行，m种颜料（数字1~m）； 输入n个数字，表示n棵树当前的颜色（0为uncolor，其他为当前的颜色）； 树的排列顺序有一个魅力值， 连续的相同颜色值算1点魅力值，例如： 树的颜色排列为 [2, 1, 1, 1, 3, 2, 2, 3, 1, 3]，其魅力值为7，分别如下： {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}
如果树的颜色是uncolor，代表可以染色； 输入n*m个数字，表示第i颗树染色成第j种颜色的代价cost[i][j];
问，如果要把树的魅力值变为k，需要的最小代价是多少？（如果无解，输出-1）
n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100)
Example
input
3 2 2 0 0 0 1 2 3 4 5 6
output
10
input
3 2 2 2 1 2 1 3 2 4 3 5
output
-1
** 题目解析：** 从给出的数据范围来看，容许时间复杂度比较大的做法。 从给出的选择来看，每次的抉择只有uncolor的树，假设要染色的树是i，大概的类别有： 1、color[i-1] != color[i+1]，这时color[i]可以等于color[i-1]或者color[i+1]，或者都不相同； 2、color[i-1] == color[i+1]，这时color[i]可以等于color[i-1]和color[i+1]，或者都不相同； 因为题目要求的是特定的魅力值，故而不能用贪心的做法。 考虑用动态规划来做， dp[i][j[k] 表示前i个，color为j，最后一个为颜色k的最小代价； 对于第i颗树，color为j的状态，考虑以下的状态： 1、color[i] != 0，不能染色，那么j=color[i]的状态，可以通过dp[i-1]的状态中获得最小代价； 1、color[i] != 0，不能染色，那么j!=color[i]的状态，不合法，忽略； 1、color[i] == 0，能染色，那么枚举j的状态，从dp[i-1]转移即可。 具体的转移方程较多，可以见代码。
** 思考?： 如果把k去掉，改成最大值，是一道不错的面试题。**
** D. Directed Roads** 题目链接 ** 题目大意：** 给出n个点，每个点有一条从其出发的有向边； 现在选择一个边的集合，对集合的每条边进行一个翻转的操作； 要求：让n个点没有形成环。 问有多少种集合可能，结果对MOD取余。 n (2 ≤ n ≤ 2·1e5) MOD = 1e9 + 7.
Example
input
3 2 3 1
output
6
input
4 2 1 1 1
output
8
题目解析： 注意重点：每个点初始状态只有一条有向边，那么每个环都是简单的环（没有重叠的环）。 那么把所有的点分成两种，环上的点，环外的点。 不在环上的点有k个，那么有2^k个选择。 第i个环的数量为num[i]，有2^num[i] - 2个选择。（全选和全不选是不行的） 结果之乘积就是答案。
总结
不知道你们有没有这样一种感觉，当你换到一个新的环境，接触到很多新的知识之后，本能地开始排斥这些新的内容。 表现出来的行为就是焦虑，觉得很多事情未完成，但是仍然注意力不集中。 明知道这些知识很重要，但是就不愿意去学，觉得这个东西很难且以后也很少用到。 这种焦虑就是人与人的价值观区别，甚至有的人会抱着好奇心的态度去接受这种新知识。 不去评判价值观的好坏，但如果能怀着好奇的心态迎接新的生活，总归会过的轻松点。