農場例行賽 #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 )$ 之類的事情來解出這題，這裡就不細講了。