Codeforces 1480D2 - Painting the Array II (設計解題、數學推理)

題目大意：

給出一個陣列，我們可以把它放到另外兩個陣列 (A,B)，A,B 這兩個陣列計算元素是這樣計算的：

• 陣列中如果周遭都是相同的數值就可以表示為一個元素，如 \((3,3,3) \) 就算一個、\((1,2,3)\) 就算是三個。
• 順序不可以交換，必須是一開始陣列的順序，透過給予 A or B 來讓 A and B 這兩個陣列元素最小，求這兩個 A,B 全部元素的數量

重點觀念

• 跳脫思考，不將重心思考放在如何把數字給這兩個陣列
• 思考放在如何讓重複的數字做到最大合併

分析：

CF 的設計解題都是好題阿，往往都能啟發出我的好想法，或是透過他人的好想法來進行學習，真的有趣，需要多練習。

首先我們先將題目一開始的陣列進行壓縮，相同的重複數值合併成一個，定義此陣列 \(num\)

這題最好的方式就是將重心放在如何將所有相同的數字都放在一起，為了方便說明，我們一樣假設我們有兩個陣列 (A,B)，而他們陣列中最後的元素為 \(x,y\)，我們可以進行假設

• 如果 \(num = x \ or \ num = y\)，這種情況當下不會多產生一個新元素
• 如果 \(num != x \ or \ num != y\)，那勢必會增加一個陣列新元素嗎？
  • 如果這個數字在上次合併前沒有出現過，那一定會增加新元素
  • 如果有出現過，則不會

合併是甚麼意思，看下面舉例。

舉例

我們假設題目陣列為 \(1,2,3,1,2,2\)，壓縮後的 num 陣列為 \(1,2,3,1,2\)

我們一開始定義 A,B 兩個陣列，會依照順序給值，因此在 num 陣列給 \(1,2,3\) 應該要是這樣

• \(A = 1,3\)
• \(B = 2\)

接下來下一個 num 值是 1，這個時候問題來了。
我們其實可以做點操作，假如我們把 A 陣列的 3，給到 B 是不是就可以讓 num 的 1 放入 A 達到不產生元素的效果？對，沒問題，因此 A,B 陣列變了

• \(A = 1\)
• \(B = 2,3\)

此時 num 陣列中的素質為 2，我們還可以合併嗎？不行
為甚麼不能合併呢，因為我們前面已經進行了一次合併，num \(1,2,3,1\) 這邊我們已經進行了合併，我們不可以破壞上次的合併，否則會破壞題目陣列的順序姓，因此這邊勢必要加一元素。

但我們可以保留 A 的 1 與 B 的 3，這兩個可以被合併，因為他們是陣列最尾端，與他們合併並不會破壞其陣列順序姓。

• 一個是因為進行合併而使得 A 陣列中的元素還是 1
• 另一個則是題目陣列中當前倒數第一個的數值

透過此方式就能解出此題，用 map 紀錄哪些數字未合併但已被加入 A,B 陣列，如果下個數字是有在未合併中的數字時那就進行合併，如果還是一個未合併數字就讓答案加一。

參考來源

D2. Painting the Array II - 准准准准准菜鸡
Editorial of Codeforces Round #700 - liouzhou_101’s blog

心得

這題要是沒有准准准准准菜鸡的大力解說，我一定沒有辦法那麼快就想出這題，透過他在網路上的詳細解說讓我快速地學會此題，我要非常謝謝他！

希望我自己在解設計解題時都可以想到這些想法，那我在現實生活中一定會比這些不會寫 cf 的人更聰明、更加優秀。

希望大家都能夠快速理解，那是我的榮幸。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 1000020
#define LOCAL
using namespace std;
int n, temp;
int a[MAXN]; //原本題目陣列
vector<int> num; //壓縮的題目陣列
unordered_map<int,int> mp; //紀錄這些還沒合併的數字

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i]; //輸入資料
    for(int i = 1; i < n; i++){ //壓縮陣列
        if(a[i] == a[i-1]) temp = a[i]; //如果等於上次的，那就表示這邊可以再進行壓縮
        else num.push_back(a[i-1]); //不同了，所以放值
    }
    num.push_back(a[n-1]); //最後的值一定要被加入，因為 for 沒有提到
    //for(int i = 0; i < num.size(); i++) cout << num[i] << ' ';
    //cout << '\n';

    int ans = 0;
    for(int i = 0; i < num.size() ; i++){
        if(mp[num[i]] == 0){ //又一個數字加入未合併數字中
            mp[num[i]] = 1; //標示被加入
            ans++; //答案 +1
        }
        else{
            mp.clear(); //合併了，因此要記錄新的合併
            mp[num[i]] = 1; //合併的數字
            mp[num[i-1]] = 1; //原本當前題目壓縮陣列中最後一個元素
        }
    }
    cout << ans << '\n'; //輸出答案
    return 0; 
}