Google Kickstart C 2018題解

來自專欄 wx演算法筆記

總體來說比Kickstart D 2018要順手些......

Problem A

題目大意：宇宙中有N個行星，安裝了N個真空管。每個真空管連接兩個行星。管是雙向的; 旅行者可以使用兩個行星之間的管子從這些行星中的任何一個行進到另一個行星。沒有兩個真空管連接同一對行星。圖保證聯通，並且只有一個循環。谷歌在這個循環周期的所有星球中隱藏著禮物。現在，谷歌想知道宇宙中的每個行星距離禮物有多遠。

您的任務是找到每個行星與作為循環周期一部分的行星之間的最小距離（就真空管的數量而言）。作為循環一部分的行星被假定為距離0。

Small dataset

3 ≤ N ≤ 30.

Large dataset

3 ≤ N ≤ 1000.

題解：由於圖是聯通的，N個點N條邊，所以只有一個循環。

首先構造一個並查集找到循環周期上的一個點，並以該點為樹的根節點逐漸構造樹，在建樹過程中判斷邊的2個頂點在樹上是否存在，如果頂點都存在，則向上追溯到根節點的路徑的節點ans為0；建樹後更新子節點的ans等父節點的ans+1。

Problem B

題目有點繞...

題目大意：有N個魔法棒，魔法棒之間相連組成一個圖，當取一個魔法棒之後所有相連的魔法棒將會消失，每個魔法棒存在一個高度值；想求出從中取出多少種魔法棒子集，並用於形成具有非零區域的凸多邊形。其中所有的木棍都被認為是不同的。

Small dataset

N = 6.

Large dataset

6 ≤ N ≤ 15.

題解：emmmm..暴力..

直接dfs求解，節點從小到大取魔法棒，當取3個或更多棒時先判斷是否可以構造凸多邊形，再向dfs取棒。

void dfs(int ci,int h,int mx,int sum){ if(h>2&&mx*2<sum) ans++; for(int i=ci+1;i<=n;i++){ if(used[i]) continue; for(int j=i+1;j<=n;j++){ if(used[j]) continue; if(L[i][j]){ used[j]=1; dfs(i,h+1,max(mx,L[i][j]),sum+L[i][j]); used[j]=0; } } }}

Problem C

題目大意：給N個數A1,A2,A3,...,An；The i-th exponential-power of 子序列定義為 Aj× 1^i+Aj+1× 2^i+Aj+2× 3^i+ ... +Ak× (k-j+1)^i。對於一個數組A，power_i=A所有子集的the i-th exponential-power。

例如A=[1,4,2]和i=2：

• 2-nd exponential-power of [1] = 1 × 1^2 = 1
• 2-nd exponential-power of [4] = 4 × 1^2 = 4
• 2-nd exponential-power of [2] = 2 × 1^2 = 2
• 2-nd exponential-power of [1, 4] = 1 × 1^2 + 4 × 2^2 = 17
• 2-nd exponential-power of [4, 2] = 4 × 1^2 + 2 × 2^2 = 12
• 2-nd exponential-power of [1, 4, 2] = 1 × 1^2 + 4 × 2^2 + 2 × 3^2 = 35

totol_sum=71

最後求POWER1+ POWER2+ ... + POWERK

Small dataset

1 ≤ N ≤ 100.

1 ≤ K ≤ 20.

Large dataset

1 ≤ N ≤ 106.

題解：推公式

用快速冪和乘法逆元快速求解。