Codeforces #71

趕paper的關係，加上不知道三天前莫斯科時區改變了，所以沒有註冊。不過挺好的，以後CFBR都提早一小時，省得要兩三時才捨得去睡。

A: 給出長度為 $N$ 的字串 $S$ ，只有當 $N > 10$ 的時候把除首尾字元外移去並寫成其移去的長度，即 $N-2$ 。有做軟件開發的應該聽過 internationalization => i18n 這回事吧。秒殺題。

B: 一個顯示進度的顯示塊，分成 $N$ 等分。 每等份的顏色深度最多為 $K$ 。現在問進度為 $0 \le t \le 100$ 的情況下每個進度顯示塊的顏色深度是多少。設進度塊的顏色深度是 $a_1 \le a_2 \le \cdots \le a_N$ ，則必需滿足

$$\frac{\sum_i a_i}{NK} \le t < \frac{\sum_i a_i + 1}{NK}$$

只需枚舉 $\sum_{i} a_i$ 的值即可。注意別忘記該值最多可以是 $NK$ 。

C: 問在一圓形上均勻分佈 $N$ 點，每點可以是紅色或綠色，問有沒有在一綠色連成正 $K \ge 3$ 邊形。直接想法就是給定一正 $N$ 邊形結構，只能構造正 $k$ 邊形若且僅若 $k | N$ 。因此枚舉 $N$ 的因數然後直接查找有無正 $K$ 邊形即可。一個 $m | N$ 相隔的點連通可以構造成 $\frac{N}{m}$ 邊形。注意不可枚舉 $\frac{N}{m} \le 2$ 的情況(考慮 $N = 4$ )。

D: 給了 $N \times M$ 張樸克牌，當中有至多兩隻鬼牌，你可以把鬼牌任意換成輸入的樸克牌中沒有的牌，但牌沒有重複。問有否存在兩個互不重疊的 $3 \times 3$ 的正方形，每個必須覆蓋其中9張牌，使得每個正方形所覆蓋的牌中，必須保証同花或者數字互不相同。然後按題目描述輸出。

好麻煩的數據處理題。總之寫得小心點即可。留意如果只有一張J2牌不要誤輸出為J1牌，有兩張鬼牌的話需要搞清次序。

E: 題目是給了 $N$ 個整數 $A_1, \cdots A_N$ ，每個不太於100。問能否通過劃分並取和後得出另外給定的 $K$ 個整數 $B_1, \cdots B_K$ ，同樣的，每個不多於100。數據範圍是 $1 \le K \le N \le 17$ 。如果能找到解必須輸出如何劃分，為使題目變得更「有趣」，出題者把數字變成化學元素，取和就是進行核融合(這真是抽了日本一把)。

我的做法是動態規劃。記 $f_{b, k}$ ，當前劃分過的數字以一集合 $b$ 表示，並且它們都可以表達了首 $k$ 個數，而 $f_{b, k}$ 僅表示這個情況能否實現，1代表能夠，0則代表不能。轉移方程則是

$$f_{b, k} = \bigvee_{b': b' \subseteq b\text{ and }s_{b-b'}=B_k} f_{b', k-1}$$
$$f_{\emptyset, 0} = 1,\quad f_{\emptyset, k} = 0 \text{ for }k > 0$$

其中

$$s_b = \sum_{i \in b} A_i$$

可預先用 $O(n2^n)$ 動態規劃計算。
麻煩的是計算 $f_{b, k}$ 的運算量最壞可以是 $O(n2^{2n})$ 。
我用了一點優化的技巧還是過了。首先，對於 $f_{b, k}$ 的計算，只需要預計算所有 $s_{b-b'}=B_k$ 即可，無需所有集合都試一次。另外，計算 $f_{\cdot, k}$ 的時候已有哪些 $b$ 使得 $f_{b, k}$ 是可行的，假設集合 $S'$ 包含這些子集 $b$ 。下次計算 $f_{\cdot, k+1}$ 時則只需從集合 $S$ 內的子集取 $f_{b, k}$ 計算即可。通過這種優化則可以在最遲2.5秒左右跑完數據。