Codeforces 1496D - Let's Go Hiking(設計解題)

題目大意

有 Q 先生與 D 先生兩個人在玩遊戲，給你一組數列，Q 先生只能走遞減(可以向左或向右)、D 先生則是遞增(可以向左或向右)，Q 先走，D 後走，如果 Q 可以贏的話，輸出它有幾種贏法，第一個 x 的 index 算一種。
沒有就輸出零

題目連結

重點觀念

• 了解贏有哪幾種情況
• 了解輸有哪幾種情況
• 贏的話可以有幾種贏法?

分析

好題，但我智商不高一直解不出來，還有些地方一直用常理去判斷QQQ，商科的爛題目大部分都還需要常理輔佐，但演算法的題目就不用，但我常常搞混:)。

簡單來說，我們可以將數列進行分析，分成遞增與遞減。
再來我們可以知道 Q、D 先生他們只要你能夠走遞增與遞減，所以理念上是他們只要有符合某種順序即可。(也就是 Q 先生不需要在意遞增或遞減，只要讓他走這兩種隨便一種即可，D 先生亦同)。

我們來簡單分析一下

• D 先生不能在走下一步，Q 先生贏
• 但 D 先生是後手可以控制 Q 先生的走法
  例如 1 2 3，Q 先生選 1，那 D 先生選 2，Q 先生就輸了
• 於是 Q 先生要到某個 x，讓他往左往右都行的通，此點我們稱為轉折點
  例如 1 3 2，那 Q 選 3 往 1 or 2 都行的通。
• 如果轉折點的左邊比較短，那 D 先生一定選右邊，這樣才能折磨死 Q 先生，反之亦同。長度:以轉折點為中心，向左或向右可延伸的最大數量。
  例如 1 4 3 2，那 Q 先生選 4，D 先生只要選右邊(3,2)，就比左邊的邊長更長，更多步可走
• 因此我們能夠知道，要找出一種轉折點是左邊的長度與右邊的長度相同。
  例如 1 3 2，這時 D 先生就不好選左邊還是右邊。
• 但題目有說，Q 先生、D 先生不能走下一步的規則是
  • 沒辦法繼續走遞增或遞減的數列
  • 下一步會撞到另外一位先生
• 也就是說，可以走曾經別人走過的路！那某些題目 D 先生又有想法可以解了
  例如 1 3 2，Q 先生選 3，D 先生選 1，Q 先生選 2，D 先生選 3，D 先生贏了！
• 發現一個問題，如果左邊邊長跟右邊邊長相同且邊長數量都是偶數時，D 先生會贏
• 因此 Q 先生贏的規則如下(必須都符合)
  • 轉折點的左邊長與右邊長相同
  • 兩邊的邊長必須是奇數

最後是題目的小陷阱，考驗思考完整能力

• 如果剛好也有一個轉折點的某個邊長與，我們 Q 先生勝利規則中的轉折點長度一樣時呢?
  很不幸的，那還是 D 先生贏，因為 D 先生可以走另外一個消耗 Q 先生的步數。舉例: 1 3 2 4，Q 先生選 3，D 先生選 2，Q 先生選 1，D 先生選 4，D 先生贏了！
• 因此我們在歸納一下
• 因此 Q 先生贏的規則如下(必須都符合)
  • 轉折點的左邊長與右邊長相同
  • 兩邊的邊長必須是奇數
  • 此轉折點的邊長必須是所有轉折點的邊長中長度最大的
  • 此轉折點的邊長不可以跟其他轉折點任一邊長長度相同
  • 由於我們只能找邊長最長的轉折點，因此答案只能有一個

參考連結

D. Let‘s Go Hiking by KIKI

心得

題目有點考倒我了QQ，好多東西都不太懂，我研究這題研究了 3hr…，雖然大部分時間是自己耍笨一直忘記 D 先生也可以走 Q 先生走過的。

總之，希望我學習的演算法，會讓我變聰明八XD，能應用上生活中。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 100020
using namespace std;
int in[MAXN], de[MAXN]; //遞增長度與遞減長度的陣列，
int n, num[MAXN], maxn = 0; //num 是題目數列資料 maxn 是最大邊長 n 是數列 size
vector<int> record[MAXN]; //紀錄在 record[index] 中，在 i 點的邊長是 index

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> n;
    for(int i = 1; i <= n; i++){ //輸入資料
        cin >> num[i];
        in[i] = num[i] > num[i-1] ? in[i-1]+1 : 1; //判斷是否遞增
        if(maxn <= in[i]){ //判斷是否是最大邊長
            maxn = in[i]; //更新
            record[in[i]].push_back(i); //將此點加入 record[index]
        }
    }

    de[n] = 1; //最後的數列值，直接設 1 否則出錯
    for(int i = n-1; i >= 1; i--){
        de[i] = num[i] > num[i+1] ? de[i+1]+1 : 1; //判斷是否遞減
        if(maxn <= de[i]) record[de[i]].push_back(i); //如果有比最大邊長大，我們再放入 record
        //前面是因為還不了解最大邊長是多少，才會只要大於就加入

    }

    int ans = 0; //判斷 x 的可能性
    if(record[maxn].size() <= 2 && maxn % 2 != 0){ //如果最大的邊長只有兩個，並且最大邊長長度為奇數時
    //否則都是不成立勝利的規則
        for(auto it: record[maxn]){ //iterator，確認那兩個最大邊長都是在同個轉折點上
            if(de[it] == in[it]) ans = 1; //是就輸出 1
        }
    }
    cout << ans;

    /*
    cout << '\n';
    for(int i = 1; i <= n; i++) cout << in[i] << ' ';
        cout << '\n';
    for(int i = 1; i <= n; i++) cout << de[i] << ' ';
        cout << '\n';
    cout << "maxn = " << maxn << '\n';
    /*/

    return 0;
}