---
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";
}
```
:::