前言
最近在接觸新知識，也是選擇2017年的方向。
其他文集更新會放緩，沒有學習就沒有心得，肚中無墨就無從下筆。
但是算法練習還是挺好玩的，歡迎關注algorithm文集。
正文
A. Bus to Udayland
題目鏈接
題目大意：
輸入n行字符，每行5個字符；
表示公交車上n排位置，X表示有人，O表示空位，|是過道。
問是否能找到兩個連續(xù)的空位；
如果可以，輸出"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的數(shù)組矩陣，在數(shù)字為0的位置填入一個正數(shù)（只有一個位置為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，題目簡化許多。
我們假設存在答案，那么可以：
根據(jù)上一行和當前行的差值，可以計算出0應該填的數(shù)字。
再判斷一下結果是否符合即可。
C. Coloring Trees
題目鏈接
題目大意：
有n棵樹排成一行，m種顏料（數(shù)字1~m）；
輸入n個數(shù)字，表示n棵樹當前的顏色（0為uncolor，其他為當前的顏色）；
樹的排列順序有一個魅力值， 連續(xù)的相同顏色值算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個數(shù)字，表示第i顆樹染色成第j種顏色的代價cost[i][j];
問，如果要把樹的魅力值變?yōu)閗，需要的最小代價是多少？（如果無解，輸出-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
** 題目解析：**
從給出的數(shù)據(jù)范圍來看，容許時間復雜度比較大的做法。
從給出的選擇來看，每次的抉擇只有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]，或者都不相同；
因為題目要求的是特定的魅力值，故而不能用貪心的做法。
考慮用動態(tài)規(guī)劃來做，
dp[i][j[k] 表示前i個，color為j，最后一個為顏色k的最小代價；
對于第i顆樹，color為j的狀態(tài)，考慮以下的狀態(tài)：
1、color[i] != 0，不能染色，那么j=color[i]的狀態(tài)，可以通過dp[i-1]的狀態(tài)中獲得最小代價；
1、color[i] != 0，不能染色，那么j!=color[i]的狀態(tài)，不合法，忽略；
1、color[i] == 0，能染色，那么枚舉j的狀態(tài)，從dp[i-1]轉移即可。
具體的轉移方程較多，可以見代碼。
** 思考??：
如果把k去掉，改成最大值，是一道不錯的面試題。**
** D. Directed Roads**
題目鏈接
** 題目大意：**
給出n個點，每個點有一條從其出發(fā)的有向邊；
現(xiàn)在選擇一個邊的集合，對集合的每條邊進行一個翻轉的操作；
要求：讓n個點沒有形成環(huá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
題目解析：
注意重點：每個點初始狀態(tài)只有一條有向邊，那么每個環(huán)都是簡單的環(huán)（沒有重疊的環(huán)）。
那么把所有的點分成兩種，環(huán)上的點，環(huán)外的點。
不在環(huán)上的點有k個，那么有2^k個選擇。
第i個環(huán)的數(shù)量為num[i]，有2^num[i] - 2個選擇。（全選和全不選是不行的）
結果之乘積就是答案。
總結
不知道你們有沒有這樣一種感覺，當你換到一個新的環(huán)境，接觸到很多新的知識之后，本能地開始排斥這些新的內(nèi)容。
表現(xiàn)出來的行為就是焦慮，覺得很多事情未完成，但是仍然注意力不集中。
明知道這些知識很重要，但是就不愿意去學，覺得這個東西很難且以后也很少用到。
這種焦慮就是人與人的價值觀區(qū)別，甚至有的人會抱著好奇心的態(tài)度去接受這種新知識。
不去評判價值觀的好壞，但如果能懷著好奇的心態(tài)迎接新的生活，總歸會過的輕松點。
