Codeforces 1474D - Array Destruction (設計解題、數學推理)

2021-01-31

字數統計： 1.9k | 閱讀時間≈ 7分鐘

題目大意：

有一個遊戲規則，遊戲規則如下：
有 x 堆的石頭，每堆石頭都可以跟鄰近的石頭進行移除，移除方式為雙方各移除 y 顆石頭，移除數量必須小於石頭數量，最終要求為要讓所有堆的石頭全部數量歸零。

特殊規則：可以有一次將兩堆石頭進行交換。

題目連結

重點觀念

對於數字的邏輯推理
快速找出題目的重點與其作答方向

分析：

我們可以先根據題目找出一些邏輯觀念：

定義石頭堆為 \(a_i\)
沒有移動石頭堆的情況下
- 如果 \( a_1 > a_2 \)，那麼 \(a_1 \) 這堆石頭永遠不會歸零，因此就永遠無法完成題目的 “Yes”
- 即使 \( a_1 > a_2 \)，那也要移除到最後一堆石頭時剛好全部移除完畢，因此需要開一個陣列紀錄 \(a_{i-1} - a_{i-2} \) 的剩下數量，再跟我們的 \(a_i\) 進行移除比較；這裡我們透過一個陣列來維護他，陣列就稱為 pre。
- 因此可以得出一個規則，石頭堆中的每一個 \(pre[i-1] < pre[i] \)，否則無法完成題目的 “Yes”，定義為向後消除規則；因為此規則紀錄的陣列就與前綴和近乎相同，只有在前綴和為 -1 時，後面全部都設為 -1，表示無法被成功移除，只要到最後一堆石頭完成時前綴和為 0 就會是 “Yes”
- 可以再延伸出一個規則，題目沒有說移除的方向，因此可以從左邊移除也可以從右邊移除石頭
- 即使 \( a_1 < a_2 \)，那也要移除到最後一堆石頭時剛好全部移除完畢，因此需要開一個陣列紀錄 \(a_{i+1} - a_{i+2} \) 的剩下數量，再跟我們的 \(a_i\) 進行移除比較；這裡我們透過一個陣列來維護他，陣列就稱為 suf。
- 因此可以得出一個規則，石頭堆中的每一個 \(suf[i] > suf[i+1] \)，否則無法完成題目的 “Yes”，定義為向前消除規則，陣列就稱為 suf；因為此規則紀錄的陣列就與後綴和近乎相同，只有在後綴和為 -1 時，前面全部都設為 -1，表示無法被成功移除，只要到第一堆石頭完成時後綴和為 0 就會是 “Yes”
- 向後消除規則或向前消除規則滿足其中一個條件即可，
有交換石頭堆的情況下
- 由於可以進行交換石頭，因此前面兩個規則就不適用，但可以透過他們擴展出一套新的規則，如果只是將某兩堆的石頭進行交換，可以發現一定會影響到 \(pre[i]\) and \(suf[i+1]\)
- 再來我們可以發現在一個可以被全解的石頭堆測試範例中可以發現 \(pre[i] = suf[i+1]\)，那是因為移除本身沒有方向性，因此如果以 i 為分水嶺，i 前面的都用向後消除規則，i 後面的都用向前消除規則，會發現則最後一個移除無論是向後消除規則或向前消除規則都是相同的。
- 因此 \(pre[i] = suf[i+1]\) 表示這裡是最後一次的移除，並且可以完全移除成功，如果不等於就表示把這裡當作最後一次的移除時，並沒有辦法完全移除成功。
- 根據上面的規則，因為只有 \(pre[i]\) and \(suf[i+1]\) 會被更動到，因此我們先假設讓 \(a[i] \) 與 \(a[i+1]\) 交換，算出交換後的 \(pre[i]\) and \(suf[i+1]\)，再判斷他們是否相等即可。
- 只要 \(pre[i-1]\) 為 -1 表示已經打破了向後消除規則，在 \(a_i\) 前面就已經有石頭堆不可以被消除 or \(suf[i+2]\) 為 -1 表示已經打破了向前消除規則 在 \(a_i\) 後面就已經有石頭堆不可以被消除；因此 \(pre[i] = -1\) or \(suf[i+1] = -1 \) 就表示在這邊交換也沒辦法完成題目規定的 “Yes”。

參考來源

Codeforces Round #696 Editorial - IgorI’s blog
Codeforces-1474 D. Cleaning（前缀和） - tomjobs

心得

這題好難QQQ，我花了將近 3 天的時間才能理解懂，很懊惱自己的腦袋為甚麼不夠聰明沒辦法把這些思緒都想懂阿，希望我每周這樣不斷地對自己進行訓練能夠讓自己在生活日常中不斷地運用到，讓我在寫程式的過程中不斷地運用到，那我就沒有白費我現在每天這麼努力的練習自己的腦袋了。

希望自己未來的腦袋能變好，這種設計解題都能夠順利解開

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include<bits/stdc++.h>
#define LOCAL
#define MAXN 200020
#define int long long
#define INF 0x3f3f3f * 10 //為解說中說明的 -1
using namespace std;
int t, n, num[MAXN];
int pre[MAXN], suf[MAXN];

int solve(){ //判斷是否可以解出

    for(int i = 1; i < n; i++){
        if(suf[i+1] == pre[i]) //表示不須交換就可以消除，把這裡的 i 讓他做後一次消除可以輸出 yes
            return 1; //成功輸出 yes
        int x = num[i+1] - pre[i-1], y = num[i] - suf[i+2] ; 
        // x = pre[i] y = suf[i+1]，讓 x,y 視為交換後的調整
        if(x >= 0 && y >= 0 && x == y) 
        // x,y 都要大於 0，表示假設這裡進行最後一次移除，可以嘗試判斷能否全部移除成功
        //如果 x,y 其中一個為負數表示被 INF 減去，
        //也表示這裡就算進行最後一次移除也沒辦法全部移除成功，
        //如果 pre 或 suf 為 INF 表示前面或後面已經有石頭沒辦法被消除，分析有對此進行詳細說明
        // x==y 表示答案相同，代表這裡為最後一次移除可以完全移除成功，因此可以輸出 "YES"
            return 1;
    }
    return 0; //表示沒有辦法被完全移除成功，符合題目要求，因此輸出 "NO"
}

int32_t main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL

    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> num[i];
        suf[n+1] = 0; //先將 suf[n+1] 為 0，才可以讓找後綴和不會抓到前筆資料
        pre[0] = 0; //pre[0] 為 0，才不會讓前綴和抓到前筆資料
        for(int i = 1; i <= n; i++){ //向前消除規則
            if(num[i] - pre[i-1] < 0) 
            //為了防止 pre[i-1] = -1 時，num[i] - (-1) 會等於正數時的冏境，因此將 pre[i] 設為 INF
                pre[i] = INF; //為分析中所說的 -1，由於在等等程式撰寫方便，因此使用 INT
            else
                pre[i] = num[i] - pre[i-1];
        }
        for(int i = n; i > 0; i--){ //向後消除規則
            if(num[i] - suf[i+1] < 0)
                suf[i] = INF + MAXN; //為分析中所說的 -1，由於在等等程式撰寫方便，因此使用 INT + MAXN
                //為了要讓 suf[i+1] == pre[i] 成立，且不讓 suf[i+1] == pre[i] == INF 時也成立，
                //因此讓 suf 在 INF 的時候再加 MAXN 來使在 INF 時 suf[i+1] != pre[i] 
            else
                suf[i] = num[i] - suf[i+1];
        }
        if(solve())
            cout << "YES\n";
        else
            cout << "NO\n";
    }

}