2020 高階競程 Contest #3 - 題解

藍的競程之旅–艾恩葛朗特

• Task Provider:ian
• Task Setter:ian

首殺 team20_23 (00:18)

解法說明

會注意到題目中的行走方向只有西、南以及換層幾種。題目本身很像是高中時會學到只能往右與往上，然後求走法的題目。
這裡將

$dp$ 定義為

$dp[\mathrm{層}\mathrm{數}][\mathrm{南}\mathrm{北}\mathrm{向}][\mathrm{東}\mathrm{西}\mathrm{向}]$ 的走法數量(從零開始，與實際數值差一)。

因為第 74 層不會被傳送到，這裡是將任何從 74 離開的都略過，你也可以選擇在第 74 層 continue 將它全部設為 0。

需要特別注意的是第 100 層，因為有提到一到達 100 層就結束，不應該在 100 層平面移動，這也是我沒有考慮到的地方，受到影響的同學不好意思。

此外還有一個很常見的錯誤，在題目中有詳細定義

$n$ 是東西向，

$m$ 是南北向，有許多人

$n$ 與

$m$ 相反。

標準程式

#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

• 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^{\prime }=p\mathrm{\%}3$ 及

$q^{\prime }=q\mathrm{\%}2$兩項
此時對於

$p^{\prime }$ 來說可以兩個

$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$ 長度與其相同，所以兩者皆可

標準程式

#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";
        }
    }
}

可愛的阿克婭 (アクア)

• 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$ 就有不錯的計算效率

要留意互乘的兩數可能很大，所以積要用較大的資料型態保存。

標準程式

#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;
}

連接棒棒

• 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 _{y=1}^{n}a[y]$)，那麼轉移式為

$dp[l][r]=\underset{l<k<r}{min}(dp[l][k]+dp[k][r])+(node[r]-node[l])$ ，要特別注意的是需要從長度為

$2(r-l=2)$ 的開始更新

$dp$ 值，再到長度

$3$ ，直到長度為

$N$ 為止，最後

$dp[0][N]$ 即為答案。

標準程式

#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";
}

最大子序列和

• Task Provider:leo900807
• Task Setter:leo900807

本題賽後新增測資，賽中的 submission 不影響

首殺 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]=\underset{i-k<j\le i}{max}(dp[j-1]+\sum _{x=j+1}^{i}a[x])$ ，為了能快速查詢區間和，將輸入的陣列做一次前綴和，最終轉移式

$dp[i]=\underset{i-k<j\le i}{max}(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=(\underset{―}{100,100},2,2,\underset{―}{100,100})$

且由於 2 維狀態要求空間過大，所以要利用滾動陣列壓縮掉 1 個維度。

標準程式

解法 1

#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

#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;
}

勇者のくせになまいきだ。

• Task Provider:ys
• Task Setter:ys

首殺 – (-:-)

解法說明

直接的，每天將所有勇者都試試能打多少魔物，取最佳的結果，接著換下一天，依此類推
但粗估一下這樣的複雜度，為頗高的

$O(n\cdot m)$

不如觀察一下問題性質，以改進複雜度
很明顯的，一樣的耐力但不同的強度的勇者們，只會用到最強的那位勇者：

for(int i = 0; i < m; i++) mx[s[i]] = max(mx[s[i]], p[i]);

用 mx 陣列記錄同耐力中最大的強度

但測資也可以產生所有耐力都不一樣的勇者，這樣上述優化就無用了

再注意到，當出現這狀況，耐力高且強度高的勇者就是首選
也就是說若

$p_i>p_j\wedge s_i>s_j$ 則不需要用上第

$j$ 位勇者：

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$ 個魔物

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 開始計

標準程式

#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

• Task Provider:leo900807
• Task Setter:leo900807

本題賽後新增測資，賽中的 submission 不影響

首殺 – (-:-)

解法說明

首先因為題目限制序列為非負整數，所以取越多肯定越好。

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]=\underset{i-k<j\le i}{max}(dp[j-1]+\sum _{x=j+1}^{i}a[x])$ ，為了能快速查詢區間和，將輸入的陣列做一次前綴和，最終轉移式

$dp[i]=\underset{i-k<j\le i}{max}(dp[j-1]+\text{sum}[i]-\text{sum}[j])$ 。

然而這樣會吃一個 TLE ，我們觀察轉移式，發現

$\text{sum}[i]$ 並不會被

$j$ 的值影響，因此可以將

$\text{sum}[i]$ 從

$max$ 函數中提出來，轉移式變為

$dp[i]=\underset{i-k<j\le i}{max}(dp[j-1]-\text{sum}[j])+\text{sum}[i]$ ，只要維護

$\underset{i-k<j\le i}{max}(dp[j-1]-\text{sum}[j])$ 即可，而你會發現

$(i-k,i]$ 是一個滑動窗口，如此一來想到了一個問題–-滑動窗口最大值，因此可以用單調隊列來將轉移複雜度壓到均攤

$O(1)$ ，如此一來總複雜度便是

$O(N)$ 。

標準程式

#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";
}