ProblemG Game Design

題目大意：

請設計塔防遊戲的地圖，這個地圖為一棵樹但可以超過 2 個 leaf。怪物只會從 leaf 往 root 走(即走到樹的根節點就再也不會走動)，我們將他簡單設計化，我們假設每個塔都可以完美殺死怪物，但建造塔則需要花費，請設計一張地圖 (那張地圖需要有節點與節點上的成本)，給你一數值 k，請生成一張地圖總共有 k 種最少成本的建造塔的解法 (任意一種即可)。

分析：

這題的想法非常有趣，我原本快要想對，但最後還是想錯方向了…
P.S. 如果我的分析不好，可以看此 st1vdy的 BLOG，我是從他那邊得到靈感的。
下方說明文的 root，為整棵樹的 root。
x 為任意變數
left node 為 x 的右邊節點
right node 為 x 的左邊節點

由於我們要設計一張地圖(樹)，為了方便我們簡單設計地圖，我們就定義為他是一顆二元樹。那我們接下來就是要來找一個規律來設計 k！

初步思考

我們先來思考哪種方式設計是最棒的，由於我們簡單設計成二元樹，於是我們先設定一算法，只有 root 為 x，其餘 node 值都為 1，且 \(x \geq 2 \)，這樣子最好算法就會有 \(k = a \cdot b \)。

那如果是質數呢？質數沒辦法符合那方程式阿，那只要把 \( x = 2 \)，就會再多一種算法，即\(k + 1\)，因為最小成本都是 2，如果從 root 放塔，那最小成本也還會是 2(\(因為 x = 2\))，因而多一種算法。

找出問題

我們的初步思考有一個很致命的缺點，因為他是給予我們 k，但如果要從 k 還原 a , b，如果遇到質數還需要 +1，程式碼太複雜不好維護。於是我們想出新的方法，既然可以 \(a \cdot b \)，那一定也有道理 \( a \cdot a \cdot b \)，可以推導成 \(a^{c} * b \)，但由於我們將算法簡化成程式碼好解決，就是將 \(a = 2\)，由於二元樹的特性，可以省下很多程式碼的功夫。

新的想法

所以我們把它從原本只有樹的 root 分兩邊然後 \(a * b \)，那我們就把每一個只要是「有連接到 leaf 的 node 的右子樹」(引號內在之後簡稱為 LN )都加入兩顆為 1 的 node，就可以達到 \( \cdot a \)的功用，剩下我們就是考慮到底要有幾個 LN，就可以湊出 k 種解法，然後如果說數字為一質數時，我們就把那 LN 的成本變成 \(LN = \text{left node} + \text{right node} \)，那如果不是質數就是 \(LN \geq \text{left node} + \text{right node} \)。

然後則必須思考，當 \(k = 1 \) 時我們實際上不需要 \(*2\)，於是我們只需要將那兩個 node 其中 1 節點改為 1，另一點則 \( > 1 \)。但當 \( k = 2 \)時，則兩節點必要為 1。

下方圖片為當 k = x 時所產生的地圖與有多少解方法及選擇的點

設計想法

因為這題是不斷的進行除以 2，來生成地圖，但我們並不確定他需要幾次才能將 \( k / 2 < 1\)，所以用遞迴解決，當用遞迴解決時，這遞迴需要的條件如下:

也就是遞迴可以解決，方程式想法如下:

• \(f(K) = if k > 2 , 呼叫 f(k/2) + f(2) \)
• \(if(k \leq 2) , 在右子樹加入 2 個 node\)
• \(LN = \text{left node} + \text{right node} \)
• \(if (k \% 2 == 0), LN +1 \)

下方則是說明，對應每個方程式的說明

• 當 \(k > 2 \) 時，我們需要做 \( /2\) 這動作，但因為我們是在尋找 \( /2\) 的最好長度，於是需要再後面加入 \(f(2)\)，才能滿足 k 的要求
• 由於 k 的值小於等於 2，我們要加入 2 個 node 以滿足 \( * 2\)的動作
• LN 會等於左節點 + 右節點，這為 K = 質數時的情況
• 如果 k 是偶數，那我們將 LN + 1，才不會多出一種解

觀念小釐清

在新的想法中，圖片最後在最後的 LN 時，左子樹也是右子樹的一種，減少程式碼撰寫麻煩。

Q: 為甚麼在下方的程式碼 function dfs 中是 return temp 而不是 return value[root]?
A: 很簡單的一個邏輯， 5 / 2 = 2 ，但 (2+1) * (2) = 6 ，回推不符合。應該還是要 2 * 2 + 1 = 5。

Q: 這篇講得很爛，文章主人是不是國文不好?
A: 這種想法的東西真的很難用文字表述，我的表達能力不好抱歉…
P.S. 但你可以稍微嘗試將這些用文字表達，真的不太好表達。這需要你去嘗試才知道困難處。

心得

要感謝 Bill and Entroy 先思考這題，等他們想通後，我才根據他們說給予我的指導和想法，幫助我寫出此題，不然要是自己寫應該要花比有他人指導更多的時間吧！希望我跟他們能夠一輩子都是好朋友。

#include <bits/stdc++.h>
#define LOCAL
#define SIZE 100010

using namespace std;
int pa[SIZE] , value[SIZE] , cnt=0 ;

int dfs(int k, int root ){
    cnt++ ;
    int temp ;
    pa[cnt] = root++ ;
    if(k <= 2){
        value[cnt] = 3 - k ;
        pa[cnt+1] = cnt ;
        value[++cnt] = 1 ;
        return 1 ;
    }
    temp = dfs(k/2,root) + dfs(2,root)  ;
    value[root] = temp + (k % 2 == 0);
    return temp ;
}

int main(){
    int k ;
    cin >> k ;
    dfs(k , 0);
    cout << cnt << '\n' ;
    for(int i = 2; i <= cnt ; i++)
        cout << pa[i] << ' ' ;
    cout << '\n' ;
    for(int i = 1 ; i <= cnt ; i++)
        cout << value[i] << ' ' ;


}