2021 高階競程 Contest #3 - 題解

--- tags: 成大高階競技程式設計 2021 image: https://i.imgur.com/IIj9BcL.png --- # 2021 高階競程 Contest #3 - 題解 ## [香蕉哥哥](https://judge.csie.ncku.edu.tw/problems/99) - Task Provider: raiso - Task Setter: raiso ### 首殺 team21_12 (00:08) ### 解法說明 STL 練習題，當 S 為 set or multiset 時，使用 `for(auto it: S)`，會依序由小到大輸出。 ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define add insert #define Int long long #define pi acosl(-1) #define MEM(x) memset(x,0,sizeof(x)) #define x first #define y second using namespace std; map<string, multiset<string> > M; void solve(){ Int m; cin >> m; while(m--) { string str; cin >> str; if(str[0] == 'I') { string A, B; cin >> A >> B; M[A].add(B); } else { string A; cin >> A; if(M[A].size() == 0) cout << "CALL THE POLICE" << endl; else { cout << A; for(auto it: M[A]) cout << " " << it; cout << endl; M[A].clear(); } } } } int main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) solve(); return 0; } ``` ::: ## [收納的智慧。Easy](https://judge.csie.ncku.edu.tw/problems/100) - Task Provider: D4nnyLee - Task Setter: D4nnyLee ### 首殺 team21_24 (00:02) ### 解法說明定義 $dp_n$ 為放完 $2 \times n$ 的方法數。觀察一下，如果只要放滿第 $n$ 直排的話，我們只有下面 $2$ 種放法。 1. 用 $1$ 個 $2 \times 1$ 2. 用 $2$ 個 $1 \times 2$ 如果是第 $1$ 種放法，那可以得知放完 $2 \times n$ 的方法數為 $dp_{n - 1}$。如果是第 $2$ 種放法，放完 $2 \times n$ 的方法數就是 $dp_{n - 2}$。因此我們就得到了式子 $dp_n = dp_{n - 1} + dp_{n - 2}$。 $dp_1 = 1$, $dp_2 = 2$ ### 標準程式 :::spoiler ```cpp #include <iostream> using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> dp(max(3, n + 1)); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; ++i) dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007; cout << dp[n] << '\n'; return 0; } ``` ::: ## [超時空跳躍](https://judge.csie.ncku.edu.tw/problems/101) - Task Provider: arashi87 - Task Setter: arashi87 ### 首殺 team21_32 (02:32) ### 解法說明根據題目我們可以知道答案會根據步數以及起點和終點的不同而不同，所以我們可以使用一個陣列 `dp[t][u][v]` 來維護**從 u 到 v 走 t 步能得到的最大值**。假設現在已經知道從 `u->v` 的最大值了，接著需要尋找有沒有一個 `k` 點可以讓 `u->k->v` 的值更大，這樣我們就可以推導出轉移式為 `dp[t][u][v]=max(dp[t][u][v], dp[t-1][u][k]*dp[1][k][v])`，最後只需要判斷 $1.01\leq dp[t][u][u]$，有沒有成立就行，如果有的話就代表得到答案了，否則就 $t+1$ 繼續尋找有沒有，直到通通跑完還是得不到解才輸出 `go back go back`。需要注意的是雖然根據題目定義是可以來回穿越的，但這行為是沒有意義的，只要第一次穿越沒有超過 $1$ 接下來的穿越也不會超過，只會越來越小。 ### 標準程式 :::spoiler ```cpp #include <stdio.h> const int maxN = 30; int n, front[maxN][maxN][maxN]; double mp[maxN][maxN][maxN]; void output(int t, int u, int v) { if (t >= 1) { output(t - 1, u, front[t][u][v]); printf(" %d", v); } else printf("%d", u); } int dp() { for (int t = 2; t <= n; t++) { for (int u = 1; u <= n; u++) { for (int v = 1; v <= n; v++) { mp[t][u][v] = -1.0; for (int k = 1; k <= n; k++) { if (mp[t][u][v] < mp[t - 1][u][k] * mp[1][k][v]) { mp[t][u][v] = mp[t - 1][u][k] * mp[1][k][v]; front[t][u][v] = k; } } } if (mp[t][u][u] > 1.01) { output(t, u, u), puts(""); return 1; } } } return 0; } int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i == j) mp[1][i][j] = -1.0; else scanf("%lf", &mp[1][i][j]); if (!dp()) puts("go back go back"); } } ``` ::: ## [收納的智慧。Hard](https://judge.csie.ncku.edu.tw/problems/102) - Task Provider: D4nnyLee - Task Setter: D4nnyLee ### 首殺 team21_32 (01:03) ### 解法說明定義 $dp_{i, j}$， $dp_{i, 0}$ 為放滿 $2 \times i$ 的方法數， $dp_{i, 1}$ 為放滿 $2 \times (i - 1)$ 以及第 $i$ 直排的**上面**的格子， $dp_{i, 2}$ 和 $dp_{i, 1}$ 差不多，只是換成**下面**的格子。 > 其實 $dp_{i, 1}$ 和 $dp_{i, 2}$ 一直都會一樣，所以實作上可以合併成一個變數就好如果只考慮放滿第 $n$ 個直排，則只有以下 $5$ 種放法： 1. $2$ 個 $1 \times 1$ 2. $1$ 個 $2 \times 1$ 3. 上面 $1 \times 2$ 和下面 $1 \times 1$ 4. 上面 $1 \times 1$ 和下面 $1 \times 2$ 5. $2$ 個 $1 \times 2$ 因此 $dp_{n, 0}$ 就可以寫成 $dp_{n - 1, 0} + dp_{n - 1, 0} + dp_{n - 1, 2} + dp_{n - 1, 1} + dp_{n - 2, 0}$。而 $dp_{i, 1}$ 和 $dp_{i, 2}$ 也可以用類似的方法得到式子。 $dp_{i, 1} = dp_{i - 1, 0} + dp_{i - 1, 2}$ $dp_{i, 2} = dp_{i - 1, 0} + dp_{i - 1, 1}$ $dp_{1, 0} = 2$, $dp_{2, 0} = 7$ $dp_{1, 1} = 1$, $dp_{2, 1} = 3$ $\forall \ i \geq 1, dp_{i, 2} = dp_{i, 1}$ :::spoiler Bonus 大家可以試著將上面的解法改為一維的 dp。 ::: ### 標準程式 :::spoiler ```cpp #include <iostream> #include <vector> #include <array> using namespace std; int mod = 1000000007; int main(void) { int n; cin >> n; vector<array<int, 2>> dp(max(3, n + 1)); dp[1][0] = 2; dp[1][1] = 1; dp[2][0] = 7; dp[2][1] = 3; for (int i = 3; i <= n; ++i) { dp[i][0] = dp[i - 1][0]; dp[i][0] = (dp[i][0] + dp[i - 1][0]) % mod; dp[i][0] = (dp[i][0] + dp[i - 1][1]) % mod; dp[i][0] = (dp[i][0] + dp[i - 1][1]) % mod; dp[i][0] = (dp[i][0] + dp[i - 2][0]) % mod; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod; } cout << dp[n][0] << '\n'; return 0; } ``` ::: ## [大大大優惠](https://judge.csie.ncku.edu.tw/problems/103) - Task Provider: ys - Task Setter: ys ### 首殺 team21_32 (01:21) ### 解法說明從[第三週教材](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%EF%BC%88Dynamic-Programming%EF%BC%89)延伸，$k(i)$ 表示以 $i$ 為結尾的最大區間和假設 $[p, q]$ 為乘上 $x$ 的區間那麼從左至右遍歷 $i$ 結尾的最大區間和： - 若 $i < p$ 則 $k(i) = \max\{k(i-1) + A_i, A_i\}$ - 若 $p \le i \le q$ 則 $k(i) = \max\{k(i-1) + x \cdot A_i, x \cdot A_i\}$ - 若 $q < i$ 則 $k(i) = \max\{k(i-1) + A_i, A_i\}$ 由於無法確定最佳的 $[p, q]$ 為何，考慮計算 $k(i)$ 時**尚未使用**及**已經使用**乘上 $x$ 後的區間和的決策則可以**拆成**三種定義狀態： - $k_1(i)$ 為 $i < p$ 以 $i$ 結尾的最大區間和 - $k_2(i)$ 為 $p \le i \le q$ 以 $i$ 結尾的最大區間和 - $k_3(i)$ 為 $q < i$ 以 $i$ 結尾的最大區間和 <img src="https://i.imgur.com/rQnnUPH.png" width=300px /> >狀態示意圖(？) 狀態轉移為： - $k_1(i) = \max\{k_1(i-1) + 1\cdot A_i, 1\cdot A_i\}$ - $k_2(i) = \max\{k_2(i-1) + x\cdot A_i, k_1(i-1) + x\cdot A_i, x\cdot A_i\}$ - $k_3(i) = \max\{k_3(i-1) + 1\cdot A_i, k_2(i-1) + 1\cdot A_i, 1\cdot A_i\}$ 其中邊界 $i \in \{1, 2, 3\}. k_i(0) = 0$ 實作上，對於 $i$ 轉移只需用到 $i-1$ 時的狀態，可利用滾動陣列將用不到的空間省下 ### 標準程式 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; typedef long long Int; int constexpr maxn = 5e5 + 10; int n, x; Int a[maxn]; int main() { cin >> n >> x; Int dp[3] {}, best = 0; for(int i = 0; i < n; i++) { cin >> a[i]; dp[2] = max({dp[1] + 1*a[i], dp[2] + 1*a[i], 1*a[i]}); dp[1] = max({dp[0] + x*a[i], dp[1] + x*a[i], x*a[i]}); dp[0] = max({dp[0] + 1*a[i], 1*a[i]}); best = max({best, dp[0], dp[1], dp[2]}); } cout << best << endl; return 0; } ``` :::