--- tags: 成大高階競技程式設計 2020 --- # 2020 高階競程 Contest #3 - 題解 ## [藍的競程之旅--艾恩葛朗特](https://judge.csie.ncku.edu.tw/problems/33) - Task Provider:ian - Task Setter:ian ### 首殺 team20_23 (00:18) ### 解法說明 會注意到題目中的行走方向只有西、南以及換層幾種。題目本身很像是高中時會學到只能往右與往上,然後求走法的題目。 這裡將 $dp$ 定義為 $dp[層數][南北向][東西向]$ 的走法數量(從零開始,與實際數值差一)。 因為第 74 層不會被傳送到,這裡是將任何從 74 離開的都略過,你也可以選擇在第 74 層 continue 將它全部設為 0。 需要特別注意的是第 100 層,因為有提到一到達 100 層就結束,不應該在 100 層平面移動,這也是我沒有考慮到的地方,受到影響的同學不好意思。 此外還有一個很常見的錯誤,在題目中有詳細定義 $n$ 是東西向,$m$ 是南北向,有許多人 $n$ 與 $m$ 相反。 ### 標準程式 :::spoiler ```cpp #include <iostream> using namespace std; int dp[105][105][105] = {0}; int main() { int n, m, i, j, k; cin >> n >> m; dp[0][0][0] = 1; for (i = 0; i < 100; i++) { for (j = 0; j < m; j++) { for (k = 0; k < n; k++) { if (j && i != 99) dp[i][j][k] += dp[i][j - 1][k]; if (k && i != 99) dp[i][j][k] += dp[i][j][k - 1]; if (i && k && (i != 74)) dp[i][j][k] += dp[i - 1][j][k - 1]; if (i > 1 && (i != 75)) dp[i][j][k] += dp[i - 2][j][k]; dp[i][j][k] %= 48763; } } } int ans = 0; for (j = 0; j < m; j++) { for (k = 0; k < n; k++) { ans += dp[99][j][k]; } } cout << ans % 48763 << endl; return 0; } ``` ::: ## [Arcane](https://judge.csie.ncku.edu.tw/problems/34) - Task Provider:joeization - Task Setter:joeization ### 首殺 team20_13 (00:13) ### 解法說明 本題需要找出 $\prod_{j=1}^{D_i}K_{ij}=N$ 中的 $K_{ij}$ 可以明顯看出拆到最後就是將 $N$ 質因數分解,但題目中約定使用的數字範圍為 $[1,9]$ 故能將題目轉換為 $N = 2^p 3^q 5^r 7^s M$ , $M$ 為分解後剩下的數值 根據題意此時 $M$ 必須要為 $1$ ,否則魔理沙無法詠唱 故後續只考慮 $N = 2^p 3^q 5^r 7^s$ 這時還剩下一個條件即**最快的詠唱方式** 觀察 $2^1=2$ 、 $2^2=4$ 、 $2^3=8$,可以知道在題目範圍內 $2$ 應該要組合成 $8$ 或 $4$ ,而組成 $8$ 能夠更好的減少使用的文字數量,對於 $3$ 同理 對於 $5、7$ 來說由於範圍內沒有冪次,和其他數的乘積也會超出範圍,故只能維持原狀 最後會剩下 $p'=p \% 3$ 及 $q'=q \% 2$兩項 此時對於 $p'$ 來說可以兩個 $2$ 組成 $4$ ,也可以和 $3$ 組成 $6$ 不過兩個組合方法都是將兩個長度一的組成一個長度一的,故兩種都可以 此時已經知道要盡量組成越多的 $9$ 和 $8$ 越好,而 $6$ 和 $4$ 兩者對於長度來說等價,所以實際解法也不需要質因數分解,只要從 $9$ 開始除到 $2$ 並記錄每個文字使用了幾次,除的過程中就已經包含分解和組合了 需要注意的是除完後要檢查 $M$ 是否為 $1$ 複雜度為 $O (\log N)$ 原本要求使用的文字盡量大,但題目未寫清楚,賽後改為Special Judge,只要長度最短就能AC 例如 $12 = 2 \times 2 \times 3 = 3 \times 4 = 2 \times 6$ ,照原題意應是 $26$ ,但 $34$ 長度與其相同,所以兩者皆可 ### 標準程式 :::spoiler ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n; int cnt[10]; cin >> n; if (n == 1) { //特例 cout << "1\n"; } else { memset(ct, 0, sizeof(cnt)); for (int i = 9; i >= 2; i--) { while (n % i == 0) { n /= i; cnt[i]++; } } if (n == 1) { //M為1 for (int i = 2; i <= 9; i++) { while (cnt[i]--) { cout << i; } } cout << "\n"; } else { //M不為1 cout << "-1\n"; } } } ``` ::: ## [可愛的阿克婭 (アクア)](https://judge.csie.ncku.edu.tw/problems/35) - Task Provider:raiso - Task Setter:raiso ### 首殺 team20_45 (00:21) ### 解法說明 仔細觀察 AKA 這字串的構成 惠發現若是 K 左邊有 $x$ 個 A 而右邊有 $y$ 個 A,那麼圍繞此 K 的 AKA 就有 $x \times y$ 這麼多種 於是只需枚舉 K 出現的位置,並且利用對 A 數量的前綴和計算出 $x, y$ 就有不錯的計算效率 要留意互乘的兩數可能很大,所以積要用較大的資料型態保存。 ### 標準程式 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int N; string LanA, LanE; int main() { cin >> N; cin >> LanA >> LanE; vector<int> s1(N, 0), s2(N, 0); s1[0] = LanA[0] == 'A'; s2[0] = LanE[0] == 'A'; for(int i = 1; i < N; i++) s1[i] = s1[i-1] + (LanA[i]=='A'); for(int i = 1; i < N; i++) s2[i] = s2[i-1] + (LanE[i]=='A'); long long cnt1 = 0, cnt2 = 0; for(int i = 0; i < N; i++) if(LanA[i] == 'K') cnt1 += s1[i]*(s1[N-1]-s1[i]); for(int i = 0; i < N; i++) if(LanE[i] == 'K') cnt2 += s2[i]*(s2[N-1]-s2[i]); if(cnt1 == cnt2) puts("WINWIN"); else puts(cnt1>cnt2? "LanA WIN" : "LanE WIN"); return 0; } ``` ::: ## [連接棒棒](https://judge.csie.ncku.edu.tw/problems/36) - Task Provider:leo900807 - Task Setter:leo900807 ### 首殺 tedliao (01:03) ### 解法說明 #### Subtask 1 $O(N\log N)$ 如同經典問題--- Add All ,詳細解法請自行搜尋,不在此多贅述。 #### Subtask 2 $O(N^3)$ 我們將每個要接起來的地方視為「節點」,特別的是,我們將最頭與最尾也視為節點,因此共會有 $N+1$ 個節點。 定義 $dp[l][r]$ 為要將木棒連接為頭尾分別是 $l$ 與 $r$ 時,所需要花費的總代價, $node[x]$ 為第 $x$ 個節點的位置 (請注意 $node[0]$ 為 $0$ 、 $node[n]$ 為 $\sum\limits_{y=1}^na[y]$),那麼轉移式為 $dp[l][r]=\min\limits_{l<k<r}(dp[l][k] + dp[k][r])+(node[r]-node[l])$ ,要特別注意的是需要從長度為 $2(r-l=2)$ 的開始更新 $dp$ 值,再到長度 $3$ ,直到長度為 $N$ 為止,最後 $dp[0][N]$ 即為答案。 ### 標準程式 :::spoiler ```cpp #include <iostream> using namespace std; long long dp[1001][1001]; int main() { ios::sync_with_stdio(0), cin.tie(0); int n, a[1001]; cin >> n; a[0] = 0; for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; for(int i = 2; i <= n; i++) for(int j = 0; j + i <= n; j++){ dp[j][j + i] = 1e18; for(int k = j + 1; k < j + i; k++) dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k][j + i]); dp[j][j + i] += a[j + i] - a[j]; } cout << dp[0][n] << "\n"; } ``` ::: ## [最大子序列和](https://judge.csie.ncku.edu.tw/problems/37) - Task Provider:leo900807 - Task Setter:leo900807 <font color="red"><B>本題賽後新增測資,賽中的 submission 不影響</B></font> ### 首殺 team20_23 (01:38) ### 解法說明 #### 解法 1 首先因為題目限制序列為非負整數,所以取越多肯定越好。 #### Subtask 1 $O(1)$ 只要每次取 $k-1$ 個,隔一格再取 $k-1$ 個,直到整個數列被取完,可以得到一般式 $a_1\times(n-\lfloor\frac{n}{k}\rfloor)$ 。 #### Subtask 2 $O(N)$ 只要 Greedy 的從大到小拿,一樣一次 $k-1$ 個,因為捨棄較小的元素一定會比捨棄較大的元素來的好。 #### Subtask 3 $O(NK)$ 定義 $dp[i]$ 為到第 $i$ 個數字為止,最大的不含連續 $k$ 個和是多少,那麼轉移式就會是 $dp[i]=\max\limits_{i-k<j\leq i}(dp[j-1]+\sum\limits_{x=j+1}^ia[x])$ ,為了能快速查詢區間和,將輸入的陣列做一次前綴和,最終轉移式 $dp[i]=\max\limits_{i-k<j\leq i}(dp[j-1]+\text{sum}[i]-\text{sum}[j])$ 。 #### 解法 2 令狀態 $dp(i, j)$ 表示到第 $i$ 個數以前且最尾端的連續和長度為 $j$ 的最大子序列和 則 $j < k$ 時,$dp(i, j) = \max(dp(i-1, j-1), dp(i-2, 0)) + a_i$ - 因為 $(j-1)$ 加上 $1$ 仍然小於 $k$ 所以可直接加上 $a_i$,會讓和更大 - 有時候連續兩個數字都不挑,反而和會較大,例如 $k = 3$, $a = (\underline{100, 100}, 2, 2, \underline{100, 100})$ 且由於 2 維狀態要求空間過大,所以要利用**滾動陣列**壓縮掉 1 個維度。 ### 標準程式 #### 解法 1 :::spoiler ```cpp #include <iostream> using namespace std; long long dp[30001], sum[30001]; int main() { int n, k; cin >> n >> k; for(int i = 1; i < k; i++){ cin >> sum[i]; dp[i] = sum[i] += sum[i - 1]; } for(int i = k; i <= n; i++){ cin >> sum[i]; sum[i] += sum[i - 1]; for(int j = i; j > i - k; j--) dp[i] = max(dp[i], dp[j - 1] + sum[i] - sum[j]); } cout << dp[n] << "\n"; } ``` ::: #### 解法 2 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxn = 3e4 + 10; int N, k, a[maxn]; long long dp[2][maxn]; int main() { cin >> N >> k; for(int i = 0; i < N; i++) cin >> a[i]; if(k == 1) { puts("0"); return 0; } dp[0][0] = 0; dp[0][1] = a[0]; dp[1][0] = a[0]; dp[1][1] = a[1]; dp[1][2] = a[0]+a[1]; for(int i = 2; i < N; i++) { for(int j = 1; j < k && i+1-j >= 0; j++) dp[i%2][j] = max(dp[(i-1)%2][j-1], dp[(i-2)%2][0]) + a[i]; for(int j = 1; j < k && i+1-j >= 0; j++) dp[i%2][0] = max(dp[i%2][0], dp[(i-1)%2][j]); } long long mx = 0; for(int j = 0; j < k; j++) mx = max(mx, dp[(N-1)%2][j]); cout << mx << '\n'; return 0; } ``` ::: ## [勇者のくせになまいきだ。](https://judge.csie.ncku.edu.tw/problems/38) - Task Provider:ys - Task Setter:ys ### 首殺 -- (-:-) ### 解法說明 直接的,每天將所有勇者都試試能打多少魔物,取最佳的結果,接著換下一天,依此類推 但粗估一下這樣的複雜度,為頗高的 $O(n\cdot m)$ 不如觀察一下問題性質,以改進複雜度 很明顯的,一樣的耐力但不同的強度的勇者們,只會用到最強的那位勇者: ```cpp for(int i = 0; i < m; i++) mx[s[i]] = max(mx[s[i]], p[i]); ``` > 用 `mx` 陣列記錄同耐力中最大的強度 但測資也可以產生所有耐力都**不一樣**的勇者,這樣上述優化就*無用*了 再注意到,當出現這狀況,**耐力高**且強度高的勇者就是首選 也就是說若 $p_i > p_j \land s_i > s_j$ 則不需要用上第 $j$ 位勇者: ```cpp for(int s = n-1; s >= 1; s--) mx[s] = max(mx[s], mx[s+1]); ``` 於是就知道,當天能連續擊敗 $s$ 個魔物的那位囂張的勇者該是哪位了 也就是設 $\text{mx_a}[s]$ 表示**某一天中**勇者們能遇到的前 $s$ 個魔物中**最強**的魔物強度 則如果 $\text{mx}[s] \ge \text{mx_a}[s]$ 就表示有勇者能在**這天**連續擊敗 $s$ 個魔物 ```cpp mx_a[0] = 0; for(int s = 1, i = k; i < n; s++, i++) mx_a[s] = max(mx_a[s-1], a[i]); int s = 1; for(int i = k; i < n && mx[s] >= mx_a[s]; s++, i++); return s; // 回傳這天勇者能擊敗多少魔物 ``` 初始 `k` 表示從第一天開始到當天目前共有 $k$ 個魔物已死亡 > 所以這裡 `a` 陣列得從 `0` 開始計 ### 標準程式 :::spoiler ```cpp #include<bits/stdc++.h> using namespace std; int const maxn = 2e5 + 10; int n, m, a[maxn]; int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &a[i]); vector<int> mx(n+1, 0); scanf("%d", &m); while(m--) { int p, s; scanf("%d%d", &p, &s); mx[s] = max(mx[s], p); } for(int s = n-1; s >= 1; s--) mx[s] = max(mx[s], mx[s+1]); int day = 0, k = 0; while(++day) { int s = 1, mx_a = a[k]; for(; k < n && mx[s] >= (mx_a = max(mx_a, a[k])); k++, s++); if(k == n || s == 1) break; } printf("%d\n", k<n? -1 : day); return 0; } ``` ::: ## [最大子序列和 - EXTREME](https://judge.csie.ncku.edu.tw/problems/39) - Task Provider:leo900807 - Task Setter:leo900807 <font color="red"><B>本題賽後新增測資,賽中的 submission 不影響</B></font> ### 首殺 -- (-:-) ### 解法說明 首先因為題目限制序列為非負整數,所以取越多肯定越好。 #### Subtask 1 $O(1)$ 只要每次取 $k-1$ 個,隔一格再取 $k-1$ 個,直到整個數列被取完,可以得到一般式 $a_1\times(n-\lfloor\frac{n}{k}\rfloor)$ 。 #### Subtask 2 $O(N)$ 只要 Greedy 的從大到小拿,一樣一次 $k-1$ 個,因為捨棄較小的元素一定會比捨棄較大的元素來的好。 #### Subtask 3 $O(N)$ 定義 $dp[i]$ 為到第 $i$ 個數字為止,最大的不含連續 $k$ 個和是多少,那麼轉移式就會是 $dp[i]=\max\limits_{i-k<j\leq i}(dp[j-1]+\sum\limits_{x=j+1}^ia[x])$ ,為了能快速查詢區間和,將輸入的陣列做一次前綴和,最終轉移式 $dp[i]=\max\limits_{i-k<j\leq i}(dp[j-1]+\text{sum}[i]-\text{sum}[j])$ 。 然而這樣會吃一個 <font color="#3498db">TLE</font> ,我們觀察轉移式,發現 $\text{sum}[i]$ 並不會被 $j$ 的值影響,因此可以將 $\text{sum}[i]$ 從 $\max$ 函數中提出來,轉移式變為 $dp[i]=\max\limits_{i-k<j\leq i}(dp[j-1]-\text{sum}[j])+\text{sum}[i]$ ,只要維護 $\max\limits_{i-k<j\leq i}(dp[j-1]-\text{sum}[j])$ 即可,而你會發現 $(i-k,i]$ 是一個滑動窗口,如此一來想到了一個問題---滑動窗口最大值,因此可以用單調隊列來將轉移複雜度壓到均攤 $O(1)$ ,如此一來總複雜度便是 $O(N)$ 。 ### 標準程式 :::spoiler ```cpp #include <iostream> #include <deque> #include <utility> #define F first #define S second using namespace std; long long dp[1500001], sum[1500001]; deque<pair<int, int>> q; int main() { ios::sync_with_stdio(0), cin.tie(0); int n, k; cin >> n >> k; if(k == 1) return cout << "0\n", 0; for(int i = 1; i < k; i++){ cin >> sum[i]; dp[i] = sum[i] += sum[i - 1]; while(!q.empty() && q.back().S <= dp[i - 1] - sum[i]) q.pop_back(); q.push_back(make_pair(i, dp[i - 1] - sum[i])); } for(int i = k; i <= n; i++){ cin >> sum[i]; sum[i] += sum[i - 1]; while(!q.empty() && q.front().F <= i - k) q.pop_front(); while(!q.empty() && q.back().S <= dp[i - 1] - sum[i]) q.pop_back(); q.push_back(make_pair(i, dp[i - 1] - sum[i])); dp[i] = q.front().S + sum[i]; } cout << dp[n] << "\n"; } ``` :::