2017年3月17日 星期五

農場例行賽 #28 不負責任快速講評

由於現在是個忙碌的上班族...題解就隨便講一下吧...

Problem A --- Guess the Number


這題我似乎估太難了?似乎大部分的人都會做嘛!

由於對於一個數愛麗絲心中所想的數 $i$ ,隨著艾利斯的猜測可能的範圍下界會愈來愈大,上界會愈來愈小。所以我們從 $a_1$ 看到 $a_N$ ,若 $i = a_x$,我們去找到比 $i$ 小的數中,艾利斯最後猜的數字是哪個,記做 $low_i$,以及比 $i$ 大的數中,艾利斯最後猜的數字是 $high_i$,並令 $dp[i][0]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 小的數,以及令 $dp[i][1]$ 為猜到 $i$ 的過程中會猜到幾個比 $i$ 大的數,於是我們有 $dp[i][0] = dp[low_i][0] + 1$ 及 $dp[i][1] = dp[high_i][1] + 1$,於是第 $i$ 行只要印出 $dp[i][0] + dp[i][1] + 1$ 就好啦!細節請自行想像囉(可能要用一些簡單的 STL或資料結構。)

Problem B --- Swap Color

這題我估太簡單了...? 

$k=1$ 的測資,只要去數相鄰的格子對有多少組是顏色相異的,並且看看是否存在一組相鄰格子對顏色相同,就可以算出答案了~

$k = 2$ 的測資呢 ...依照有多少格子與原本的格子顏色不同個別處理,不同的個數只可能為 $0$ 或 $2$ 或 $4$。

相差為 $0$ 的一定辦的到。

相差為 $2$  的,又可在分為兩種情況,第一種為兩格相鄰,第二種诶兩格距離為 $2$。實際上若相異的格子對距離為 $1$ 或 $2$,在 $n, m \ge 2$ 時,一定有辦法用恰兩步交換構造出來 (若 $n = 1$ 或 $m = 1$ 就不一定囉!原本想說我沒有考這種情況已經夠善良了 XD)

相差為 $4$ 的,一定可以用兩組相鄰為的異色格子湊出。所以我們就計算兩組的組合有幾個,在扣掉有重疊的部分,重疊的情形有兩種,一種是重疊在黑色個子,另一種是重疊在白色格子,最後還要要在扣掉形如 "WB\nBW\n" 或 "BW\nWB\n" 的情形,因為有兩種可能的組合都會算到他。我自認為很善良的把這種情形放在 範例測資裡,不知道大家有沒有看到呢 @@

像這種題目啊... 若是出在 TOI 這種長時間的比賽,不如寫個暴搜的程式碼,在隨機產生小測資,驗證自己的答案是否正確,通常你寫的若是錯的,大概 $2 x 3$ 的測資就會讓你錯掉,你就可以想想看你是否漏想了什麼。

Problem C --- Count Simple Cycles

小測資直接暴力搜索就行了,可以自己試著估估看複雜度,當 $n = 10$ 時,就算是完全圖,遞迴搜索的步數也不多,但要注意是否會算到重覆的 Cycle,例如 $1-2-3$, $2-3-1$ 這兩種情形會不會重複算到,要步重複算到也有多種處理方法,可以自己想想看~

大測資的話,首先要知道 Cycle Basis ~,有了這個東西你就會知道 Cycle 數目一定不超過 $2^{18}$,所以也可以暴搜啦!!!

對不起這是騙你的。

要暴搜,首先要把度數為 $1$ 的點都拔掉,他們一定不會對 Simple Cycle 有貢獻,接著要把度數 為 $2$ 的點也縮起來,反正他連那麼長也沒什麼用, 就算把 $10^5$ 個度數為 $2$ 的點連在一起縮成一條邊也不會影響 Simple Cycle 的個數。

所以做完這些步驟後,掐指一算,會剩不到 $40$ 個點也不足 $60$ 條邊~,這個時候暴搜就可以過啦,但我不知道怎麼估這時暴搜的複雜度... 但就算不暴搜,我們也可以使用 Cycle Basis 的性質,好好做個 $O(2^{19} \times 60 )$ 之類的事情來解出這題,這裡就不細講了。