PKU 3742 Equivalent Polynomial

POJ月賽八月份的題目。

大意是給出一多項式，轉化成。
設前者為，後者為，則有。因此，把原式expand，用Java的biginteger就可以解決了。

PKU 3741 Number System Converter

POJ月賽八月份的題目。

大意是給出一個整數，經過進制化轉十進制後變成，再轉化成進利後變成，把代入重覆重作直至。因為，可以肯定的是若至少經過一遍循環，答案必然在至之間。

不失一般性，先把寫成進制 (注意本身可能不是進制)


經過進制化後會變成

然後得出, 其中是一多項式。
把上式寫成
然後可以得出
因此就是最終答案。
可以把題目轉化成。
留意的的取值可以在，所以要把加上足夠多的使其在。

另外需要留意若輸入的根本不會完成一次循環的話，將會是答案。
因此在特殊情況下可以取值在。以下的輸入便是一例。
8 10
7

PKU 3740 Easy Finding

POJ八月份月賽的題目。
大意是求一個可以cover所有columns exactly一次的rows subset。

做法是枚舉所有可能性。
設現有列，則任意列的子集可以由 bit 的來表達。
可想而知，對於一個列子集，它的狀態轉移必然從子集判斷，其中。(即只有一bit相差)

這道題本來不難，唯數據數量太大，需要把300行的數據壓縮成50個64位元整數，而且只要的狀態無效則無須考慮其轉移狀態，因為導出狀態必然也是無效。

至於如何從考慮狀態？我用的是highest bit。另一種有效的方法是以gray code枚舉。

PKU 1325 - Machine Scheduling

本題源自北京賽區2002年的賽題。

假設有兩台機器a與b，分別有n和m個工作式模式。
現有K個工作，它可以分別在機器a和機器b兩種特定模式處理掉。
假設兩台機器都預設在0模式運作，問需要更改兩台機器次數總和最少使得工作能全部完成。

可以觀察到的是舉凡工作可以在其中一台機器的模式零運作都可以預先處理掉而不需更改兩台機器的運作模式。

剩下來的工作可以看成是二分圖的最小頂點覆蓋。根據konig's theorem，此問題等價於最大二分圖匹配。

難度系數從1.91804 降至1.91142。

USACO Cow Pedigrees

給定N和K，問有多少棵高度為K、N個頂點的二叉樹。對二叉樹的要求是除葉子外所有頂點必須有兩個子節點。

明明是很簡單的動態規劃，卻搞了我很多時間…

定義目標函數 F[N][K] 即題目要求數。

觀察﹕
(1) F[N][K]必須依賴 F[i][K-1]，使得二叉樹數符合要求。
(2) 必須分配單數子節點予任意子樹，否則必得無乎合要求的二叉樹。
(3) 得出轉移方程為 F[i][K-1] * F[N-1-i][j] * 2 的總和，當中 j < K-1。
(4) 另需加上F[i][K-1] * F[N-i-1][K-1]，因為交換子樹視同相等。
(5) 合法狀態必須符合 2*K < N + 2，因為一棵符合要求的子樹至少是Left Completed，必然有2 * K - 1點，否則無法構建二叉樹。

沒有留意(5)便會造成很多無謂的錯誤。