斑的家

A. Xenia and Divisors

題意：

給n 個數字，3|n 。 將n 個數字分成n/3 堆，每堆3個數字a,b,c。

a,b,c 要符合以下規定，

a < b < c , a | b , b | c。

數字的範圍是1 - 7。

解法：

稍微推敲一下就能發現可能的組合只有 ( 1,2,4 ) , (1,2,6), (1,3,6)。

先取(1,2,4)，再取(1,2,6)，最後取(1,3,6)。

B. Xenia and Spies

題意：

有n 個人站在一排，現在第s個人想要將紙條傳給第f個人，但是

在ti 秒時在[a,b] 範圍的人會被監督，所以這時不可以將紙條傳給這些人，

或者這些人不能互傳紙條。

在第t秒時，手上握有紙條的人，可以選擇不傳或者往左往右傳。

請問要怎麼傳才可以最快將紙條從第s個人傳到第f個人手上。

解法：

如果f 是在 s 左邊，那就想辦法一直往左傳就好了 。若是在右邊，則

一直往右傳。

C. Cupboard and Balloons

題意：

見圖

給一個底 r ，高h 的長方形，上面還有個半徑r 的半圓形。問裡面可以塞

多少個，半徑0.5r 的小圓。

解法：

先塞小圓到長方形，一共可塞 h/r 個，頂部會留有空隙 d = h%r

接下來看上面的半圓形，

如果d >= 0.5 r 的話表示可以塞2個小圓。

如果 d< 0.5r 只能塞一個。

如果d + r >= sqrt(3)/2*r + r 的話，那麼還可以塞一個

小圓在2個小圓中間。

D. Xenia and Dominoes

不會。

E. Xenia and Tree

有一棵樹，上面有n個點，點的顏色都是藍色。

點的序號從 1 - n 。

一開始點1的顏色是紅色。

有2種操作，

1) 將某個點塗成紅色。

2) 問某個點到最近的紅點有多遠。

點 < 10^5 , 操作 < 10^5

解法：

這題要用到2個演算法，一是BFS，二是LCA。

設 L 存已知的紅點。

BFS 可以 update 所以藍點到紅點的最短距離。

並把 L 清空。

LCA 可以針對某個藍點和 在L裡的紅點最LCA並求

出最短距離。

令 sq = sqrt ( 操作的個數 )。

當 L 的 size < sq 時

用 LCA 的方法求距離。

當 L 的 size > sq 時，用 BFS update 所有的距離，這時可以

順便把L清空。

因此時間是 O(n * sqrt(n) )  + O( LCA preprocess 時間)。