---
tags: 成大高階競技程式設計 2020
---

# 2020 高階競程 Contest #1 - 題解

## [藍的競程之旅–炎論嬸茶](https://judge.csie.ncku.edu.tw/problems/18)

- Task Provider:ian
- Task Setter:ian

### 首殺 team20_23 (00:04)

### 解法說明
本題的字典其實就是 stack ，每次只能 push or pop 最上面
但在查詢的時候不能遍歷，否則會 TLE。
解決的方式為同時維護 stack and set，查詢時使用 set 進行查詢。

另外要注意有可能在字典為空時進行 pop ，所以要特判

### 標準程式
:::spoiler

#include <bits/stdc++.h>

using namespace std;

string s;
set<string> st;
stack<string> dict;
int main() {
  int n, m, i, j, k, cmd;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  while (n--) {
    cin >> cmd;
    if (cmd == 1) {
      cin >> s;
      dict.push(s);
      st.insert(s);

    } else if (cmd == 2) {
      if (dict.size()) {
        string top = dict.top();
        st.erase(top);
        dict.pop();
      }
    } else {
      cin >> s;
      if (st.find(s) != st.end()) {
        cout << "Y";
      } else {
        cout << "N";
      }
    }
  }
  cout << endl;
  return 0;
}

:::

## [林野調查](https://judge.csie.ncku.edu.tw/problems/19)

- Task Provider:leo900807
- Task Setter:leo900807

### 首殺 team20_23 (00:10)

### 解法說明

#### Subtask 1 $\ \ \ O(n^2)$

只要每一次都 $O(k)$ 掃過去找最大值就可以，共掃 $n-k+1$ 次，以 $n-k$ 次計，根據算幾不等式 $\frac{k + (n-k)}{2}\geq\sqrt{k(n-k)}\Rightarrow k(n-k)\leq\frac{n^2}{4}$ 。

#### Subtask 2 $\ \ \ O(n\log k)$

只要用長度為 $k$ 的滑動窗口，當一個數字被包含進去時就將其計入 map/multiset ，離開時就移出 map/multiset ，每次操作完後取 map/multiset 中最大值。

#### Subtask 3 $\ \ \ O(n)$

其實這是一道經典問題，叫做「滑動窗口最大值」，由於沒教過 deque ，可以以 list 代替，但是還是建議使用 deque ，常數較小。

用一個長度為 $k$ 的滑動窗口，每次有新的值要進來時，就判斷 deque/list 尾端元素，若尾端元素小於當前元素或是 deque/list 為空時就將其 pop ，如此一來可以維護 deque/list 內的元素是遞減的，當要離開時就判斷 deque/list 前端元素的 position 是否小於當前窗口 ，若小於就將其 pop 掉，每次只要取 deque/list 前端元素就是當前窗口最大值。

而這會是正確的原因，是因為後面來的會存在在窗口中較久，代表在它前面且較小的，在之後都不會是最大值，因此可以直接將該值 pop。

每個元素至多進出 deque/list $1$ 次，均攤複雜度 $O(n)$ ，這種作法叫做「單調隊列」，因為在這個隊列中所有元素都維持著遞減的單調性。

~~被各種假解QQ~~

### 標準程式

因為常數問題，標準程式使用 deque 。

:::spoiler

#include <iostream>
#include <deque>
#define F first
#define S second
#define MP make_pair
using namespace std;

deque<pair<int, int>> q;

//first is position
//second is element

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, k, x;
  cin >> n >> k;
  for(int i = 0; i < k - 1; i++){
    cin >> x;
    while(!q.empty() && q.back().S < x)
      q.pop_back();
    q.push_back(MP(i, x));
  }
  for(int i = k - 1; i < n; i++){
    cin >> x;
    while(!q.empty() && q.back().S < x)
      q.pop_back();
    q.push_back(MP(i, x));
    while(!q.empty() && q.front().F <= i - k)
      q.pop_front();
    cout << q.front().S << " \n"[i == n - 1];
  }
}

:::

## [丟雞蛋問題](https://judge.csie.ncku.edu.tw/problems/20)

- Task Provider:leo900807
- Task Setter:leo900807

### 首殺 team20_23 (00:15)

### 解法說明

#### Subtask 1

本 Subtask 主要是為了讓參賽者測試程式是否能執行。

#### Subtask 2 $\ \ \ O(M)$

只要從 $1$ 到 $60$ 慢慢往上查詢即可。

#### Subtask 3 $\ \ \ O(\log M)$

假設在第 $i$ 層會破，則大於第 $i$ 層都會破；假設在第 $i$ 層不會破，則小於第 $i$ 層都不會破，可以用此方法來二分搜找出 $k$ 是多少。

### 標準程式
:::spoiler

#include "lib0020.h"

long long height_limit(long long M){
  long long l = 1, r = M + 1, mid;
  while(l < r){
    mid = l + r >> 1;
    if(is_broken(mid))
      r = mid;
    else
      l = mid + 1;
  }
  return l - 1;
}

:::

## [修補棒棒](https://judge.csie.ncku.edu.tw/problems/21)

- Task Provider:raiso
- Task Setter:raiso

### 首殺 team20_23 (00:31)

### 解法說明
這題重點在於 $k < n$ 時，勢必有兩個洞以上需要使用同一段膠帶修復。
1. 修補完全部的洞，至少需要長度 $n$。
2. 找出需要使用同一段膠帶補的個數 ($n-k$)。
ex: $n=4, k=2$，需要連接兩組洞，省下兩段
3. 找出滿足使用同一段膠帶連接兩個洞的代價，排序，從最小的代價開始選用。
### 標準程式
:::spoiler

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll n, m, k;
vector< ll > del;
ll ans = 0;
 
int main() {
  cin >> n >> m >> k;
  del.resize(n-1);
  ll lst, now;
  cin >> lst;
  if(n == 1) {
    cout << 1 << endl;
    return 0;
  }
  for(int i = 1; i < n; i++) {
    cin >> now;
    del[i-1] = now - lst;
    lst = now;
  }
  sort(del.begin(), del.end());
  ans += n;
  for(int i = 0 ; i < n-k; i++) {
    ans += (del[i]-1);
  }
  cout << ans << endl;
  return 0;
}

:::

## [爬樓梯 k](https://judge.csie.ncku.edu.tw/problems/22)

- Task Provider:ys
- Task Setter:ys

### 首殺 team20_23 (01:00)

### 解法說明
回顧教材的[上樓梯問題](https://hackmd.io/@nckuacm/r1ZEy4ar8#%E7%AF%84%E4%BE%8B-LeetCode-70-Climbing-Stairs%EF%BC%9A)

dp[0] = dp[1] = 1;
for(int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

造成答案變動的**決策**有每次要走 $1$ 階還是走 $2$ 階的選擇
但是 $dp(i)$ 依舊沒辦法紀錄是否走了 $k$ 次或是正往 $k$ 次邁進
不妨就多為**目前走了幾次**新增一個狀態 $dp(i, j)$

由於走一次會從當前 $j-1$ 次變為 $j$，轉移為
$$
dp(i, j) =
\begin{cases}
dp(i-1, j-1) + dp(i-2, j-1) &\text{if } j \le \min(i, k) \\
0 &\text{otherwise}
\end{cases}
$$
> $j$ 不能超過 $k$ 次，也沒辦法用 $i$ 次以上走到第 $i$ 階樓梯

邊界為 $dp(0, 0) = dp(1, 1) = dp(2, 1) = 1$
> $dp(0, 0) = 1$ 表示站在地板不需要走就是一種方法

最終答案為 $\sum\limits_{j=0}^k dp(N, j)$

特別留意，在求解過程中，變數可能會溢位
但題目只要求答案在除餘 $10^9 + 9$ 範圍內，所以求解中可順便除餘 $10^9 + 9$ 以防溢位

### 標準程式
:::spoiler

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e3 + 10;
int const MOD = 1000000009;

int N, k, dp[maxn][maxn];

int main()
{
  scanf("%d%d", &N, &k);

  dp[0][0] = dp[1][1] = dp[2][1] = 1;

  for(int i = 2; i <= N; i++)
    for(int j = 2; j <= min(k, i); j++)
      dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1]) % MOD;

  int sum = 0;
  for(int j = 0; j <= k; j++) sum = (sum + dp[N][j]) % MOD;
  printf("%d\n", sum);

  return 0;
}

:::