2020 高階競程 Contest #4 - 題解

攻城行動

Task Provider:leo900807
Task Setter:leo900807

首殺 team20_23 (00:10)

解法說明

這題目可以視為區間修改、查詢全域最大值，且修改操作均在查詢操作前。

Subtask 1
$O (N C + C)$

每次都暴力將區間所有值修改，最後

O (C)

取

max

。

Subtask 2
$O (N + C)$

運用課堂上的差分，每次修改將

l - 1

的值加

w

，

r

的值減

w

，但要小心題目中的

l

可能有

0

。

最後

O (C)

跑一次前綴和並取

max

。

Subtask 3
$O (N \log N)$

直接將所有

l, r

離散化，然後開線段樹或是 BIT 。

Subtask 4
$O (N \log N)$

其實這題是想告訴各位不要使用樹狀結構，在某些比較嚴謹的比賽中可能會 TLE 或是 MLE 。

只要將每個輸入進來的

l, r

搭配上厚度存成 pair ，第一個存位置

(l, r)

，第二個存厚度，如果是

l

就存

w

，如果是

r

就存

- w

。

舉個例子，假設有一道城牆位於

[3, 8]

、厚度為

6

，則存入兩組 pair 分別是

{3, 6}

與

{8, - 6}

。

接著將

2 N

組 pair 依照位置由小到大排序，初始sum = mx = 0，接著依序跑過去，當遇到

w

值為正時就將sum += w，

w

值為負時就先取最大值mx = max(mx, sum)，再將sum -= w，最後的mx值就是答案。

如果理解這題的解法的話，可以去試試這題。

標準程式

#include <iostream>
#include <algorithm>
#define F first
#define S second
using namespace std;

pair<int, int> a[2000000];

int main() {
    long long n, l, r, w, mx = -1, now = 0;
    cin >> n;
    for(int i = 0; i < 2 * n; i += 2){
        cin >> l >> r >> w;
        a[i].F = l, a[i].S = w;
        a[i + 1].F = r, a[i + 1].S = -w;
    }
    sort(a, a + 2 * n);
    for(int i = 0; i < 2 * n; i++){
        now += a[i].S;
        mx = max(mx, now);
    }
    cout << mx << "\n";
}

魔法球

Task Provider:leo900807
Task Setter:leo900807

pB 賽後新增測資，不影響賽中 submission

首殺 team20_21 (00:21)

解法說明

Subtask 1

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

Subtask 2

首先跑

N

次取

min

，再跑

N

次取

max

。

Subtask 3

將

N

個數字拆成兩組，每一組分別有

\frac{N}{2}

個數字，若

N

為奇數時，先將落單的數字放一旁。

接著將兩組數字一對一比較大小，將較小的一組放一起，較大的一組放一起，共得到兩組，接著取小的那組最小值為

m i

，大的那組最大值為

m x

，最後將這兩個數字再跟最一開始落單的數字比較即得出全部的最小值與最大值。

最一開始比較

\frac{N}{2}

次，接下來兩組中分別比較

\frac{N}{2} - 1

次，如果

N

為奇數再加

2

次，總比較次數

\frac{N}{2} + 2 \times (\frac{N}{2} - 1) + 2 = \frac{3 N}{2} = 1.5 N

標準程式

#include <vector>
#include "lib_sample.h"
using namespace std;

vector<int> migroup, mxgroup;

int main() {
    int n, mi, mx;
    MagicBalls(&n);
    for(int i = 1; i < n; i += 2){
        if(Collision(i, i + 1))
            migroup.push_back(i + 1), mxgroup.push_back(i);
        else
            migroup.push_back(i), mxgroup.push_back(i + 1);
    }
    mi = migroup[0];
    for(int i = 1; i < migroup.size(); i++)
        if(Collision(mi, migroup[i]))
            mi = migroup[i];
    mx = mxgroup[0];
    for(int i = 1; i < mxgroup.size(); i++)
        if(!Collision(mx, mxgroup[i]))
            mx = mxgroup[i];
    if(n & 1){
        if(Collision(mi, n))
            mi = n;
        if(!Collision(mx, n))
            mx = n;
    }
    Choose(mi, mx);
}

22/7

Task Provider: ian
Task Setter: ian

首殺 – (-:-)

解法說明

這題比較可惜沒有人想到
他其實是二分搜，用二分搜去嘗試單條的長度
如果發現這個 mid 可以成功，就試著用更小的 mid
如果失敗，就試著用更大的 mid

標準程式

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main() {
    int n, m, i, j, k;

    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (i = 0; i < m; i++) {
        cin >> a[i];
    }

    long long l = 2, r = INT_MAX, mid;
    int last_succ;

    while (r >= l) {
        j = 0;
        mid = (l + r) >> 1;
        for (i = 0; i < k; i++) { // 試試看能不能用 k 條 mid 長度的
            int used = 0;
            int last = a[j] - 1;
            for (; j < m; j++) {
                if (used + a[j] + 1 - last > mid) {
                    break;
                }
                used += a[j] + 1 - last;
                last = a[j] + 1;
            }
        }
        if (j == m) {  // success
            last_succ = mid; // 成功就記錄下來
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << last_succ << endl;

    return 0;
}

Mana

Task Provider: joeization
Task Setter: joeization

首殺 team20_26 (02:21)

解法說明

暴力解的話就是產生

1

到

N

的編碼
對其中的

M

個句子找出現過的前綴，或著建一顆 Trie 看有幾個 node

但是這題有這句
每個魔法句子

$K$ 可透過增加
$1$ 詠唱魔力來變化為另外兩種新的魔法句子
$K + ᚢ$ 和
$K + ᚦ$
可以知道每個句子的轉移都只有兩種，使用 Trie 雖然可解但不是最好
若對 Tree 熟悉的話可能馬上就能想到句子的轉移過程可能是一顆 Binary Tree
並且編號正好是從

level 0

開始編碼

{1}

是

level 0

{2, 3}

是

level 1

{4, 5, 6, 7}

是

level 2

取到第

N

個句子的話此時所有轉移就能組成一個 Complete Binary Tree

此時考慮

N = 3

的情況，我們知道不管取

2 (ᚢ)

還是

3 (ᚦ)

都需要額外的一點魔力
同樣的若

N = 7

，我們取

4 (ᚢ ᚢ)

或

5 (ᚢ ᚦ)

時都會經過

2 (ᚢ)

可以知道以某點

K

為根節點的子樹中若有要取的點，

K

也一定會取到
因此對所有點

K_{i}

來說只要把 ancestor 標記起來即可，這樣相當於 Trie 的操作，但是省去了產生每個

K_{i}

的編碼的過程

有了以上的想法，最後的輸出就是有幾個子樹需要標記
標記的過程中遇到標記過的點就可以跳出，因為同樣的前綴只會遇到一次
每個

Ｋ_{i}

都找到 root 才停止的話會 TLE

註：賽中有些隊伍做法是對的但是直接用 cin/cout 會 TLE ，要注意題目的輸入次數

標準程式

#include <bits/stdc++.h>
using namespace std;
int n, m;
bool cast_w[1111111];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    int k;
    for (int i = 0; i < m; i++)
    {
        cin >> k;
        cast_w[k] = true;
    }
    int ans = 0;
    //從最高level開始到level 1
    for (int i = n; i > 1; i--)
    {
        //該子樹有標記
        if (cast_w[i])
        {
            //答案加一
            ans++;
            //標記以parent node為root的子樹
            cast_w[i / 2] = true;
        }
    }
    cout << ans << "\n";
}

平衡子序列

Task Provider: codeforces
Task Setter: 西瓜

首殺 team20_29 (00:25)

解法說明

尋找最少的字母，在最大的子序列中，其他字母也需要有同樣的數量，那就知道這個子序列的長度了！ ~~西瓜水不水，絕對超級水。~~
題目出處

標準程式

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<int> cnt;
string str;
int main() {
        cin >> n >> k;
        cin >> str;
        cnt.resize(26);
        for(int i = 0; i < n; i++) {
                cnt[str[i] - 'A']++;
        }
        int mini = 1e9;
        for(int i = 0; i < k; i++) {
                mini = min(mini, cnt[i]);
        }
        cout << mini * k << endl;
}

共同子序列

Task Provider: raiso
Task Setter: raiso

首殺 team20_06 (00:32)

解法說明

簡單來說，因為在建立 LCS 時使用的僅僅是上一個 row 的資料，所以我就使用類二維陣列的方式，開 2x3000 的矩陣，僅記錄兩個 row ，這樣可以不用擔心邊界容易寫錯，我覺得比起滾動，這個更好理解。
下方註解是使用二維陣列時的三元運算子寫法，先看懂這個會比較好理解壓縮到 2x3000 的符號意義。

標準程式

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

int n;
char str[2][3005];
int dp[2][3005];

int main() {
  cin >> n >> str[0] >> str[1];
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) dp[0][j] = dp[1][j];
    for(int j = 0; j < n; j++) {
      if(str[0][i] == str[1][j])
        dp[min(i, 1)][j] = (i == 0 || j == 0)? 1: dp[0][j-1]+1;
        //dp[i][j] = (i == 0 || j == 0)? 1: dp[i-1][j-1]+1;
      else
        dp[min(i, 1)][j] = (i == 0 || j == 0)? (dp[min(max(i-1, 0), 1)][max(j-1, 0)]): (max(dp[0][j], dp[1][j-1]));
        //dp[i][j] = (i == 0 || j == 0)? (dp[max(i-1, 0)][max(j-1, 0)]): (max(dp[i-1][j], dp[i][j-1]));
    }
  }
  cout << dp[1][n-1] << endl;
  return 0;
}

藍的競程之旅–WA

Task Provider: NPSC
Task Setter: ian

首殺 team20_21 (02:09) team20_22

解法說明

本題不是 greedy 所以一直切最大的是錯的，其中一個例子是 5 6

我們知道某個長方形的解答一定是這個長方形切成某兩個長方形的解相加
所以將

d p [i] [j]

定義成長寬

i 、 j

的長方形的解
另外可以知道如果

i == j

的解為

1

接下來由小到大針對每個

i 、 j

嘗試每一種切法，然後選最小的
例如

3

2

切成

d p [3] [1] + d p [3] [1]

或

d p [1] [2] + d p [2] [2]

或

d p [2] [2] + d p [1] [2]

取裡面最小的

標準程式

直接拿 team 21 的解，他們很棒

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int dp[110][110];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    memset(dp, 0x3f, sizeof(dp));
    dp[1][1] = 1;
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= 100; j++) {
            for (int k = 1; k <= i; k++) {
                if (i != j) {
                    int tmp = dp[i - k][j] + dp[k][j];
                    dp[i][j] = min(dp[i][j], tmp);
                } else
                    dp[i][j] = 1;
            }
            for (int k = 1; k <= j; k++) {
                if (i != j) {
                    int tmp = dp[i][j - k] + dp[i][k];
                    dp[i][j] = min(dp[i][j], tmp);
                } else
                    dp[i][j] = 1;
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

天線覆蓋問題

Task Provider:ys
Task Setter:ys

首殺 – (-:-)

解法說明

解法 1

由於需要決策使哪些天線成長，並且評估最小的花費
考慮看看這是不是個 DP 問題

細看問題，須將涵蓋的範圍遍及每個點，而每個點都知道被哪支天線覆蓋

但對我們而言是哪支並不重要

先試試粗暴的定義狀態

dp (i)

就是涵蓋

[1, i]

範圍的最小成本
若是有這個狀態，再配合一支天線範圍會到

j

的，那麼也能直接求得

dp (j)

的解

而明顯的，一但

dp (i)

被解出來，

\forall j > i . dp (j)

的解並不干擾

dp (i)

接著設計狀態轉移，
對於固定點

i

，

dp (i)

僅需顧好範圍

[1, i]

看極端例子，若

s = 0

，則只看

x

的位置在哪就好

若
$x$ 在
$i$ 的左側，花費
$i - x$ 再加上
$x - 1$
若
$x$ 在
$i$ 上，花費
$x - 1$

$- 1$ 表示扣除天線本身位置

而

s > 0

的話，就看

[x - s, x + s]

這整個範圍是落在

i

的左側還是裡面

在左側，花費為
$i - (x + s)$ 再加上
$max (x - s - 1, 0)$
在裡面，花費為
$max (x - s - 1, 0)$

$x - s - 1$ 有可能會跑到範圍
$1$ 之外

靠

dp (i)

要解出

\forall j > i . dp (j)

，最差的狀況就是沒有天線預設涵蓋

dp (i)

，所以初始化為

i

可以想像有天線涵蓋
$j$ 但不涵蓋
$i$ 的狀況，那麼花費就是
$i$ 到
$x - s$ 加上
$dp (i)$

解法 2

dp (i)

的狀態定義與解法 1 一樣
但在計算上，在遍歷到點

i

上時會以早已解出

dp (i)

為前提做狀態轉移

且事先加上已知的解

dp (0) = 0

，為了那些預設已經涵蓋到

i = 1

的天線

解法 3

若一支天線與另一支天線的範圍互相重疊或碰觸，那麼可將他們看作一支範圍更大的天線
而對於一支天線，花成本升級就能看作產生另一支範圍更大的天線

也就是說只要將所有種覆蓋整個街道的天線產生，看哪個成本低就行了

如何有效率的產出覆蓋整個街道的天線？

街道從左至右，每遇到一個天線，就看他範圍內有沒有別的天線能碰到

1

位置，如果有就將他跟這個天線合成為一支範圍更大的天線
而明顯的，眾多選擇中只要每次挑的天線成本最低，那麼合成的天線一定成本低
這樣一路合成天線到最右端

m

，就能得到成本最低且覆蓋整個街道的天線。

實作採用線段樹，因為複雜度較小，細節請參考標準程式

標準程式

解法 1

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

int const maxn = 90;

int n, m, x[maxn], s[maxn];

int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &s[i]);

  vector<int> dp(m+1);
  iota(dp.begin(), dp.end(), 0);

  for(int i = 1; i <= m; i++) {
    for(int j = 0; j < n; j++) {
      if(i > x[j]+s[j])
        dp[i] = min(dp[i], dp[max(0, x[j]-(i-x[j])-1)] + i-(x[j]+s[j]));
      else
        dp[i] = min(dp[i], dp[max(0, x[j]-s[j]-1)]);
    }
  }

  printf("%d\n", dp[m]);

  return 0;
}

解法 2

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

int const maxn = 90;

int n, m, x[maxn], s[maxn];

int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &s[i]);

  vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int a, int b) {
    if(x[a] == x[b]) return s[a] < s[b];
    return x[a] < x[b];
  });

  vector<int> dp(m+1);
  iota(dp.begin(), dp.end(), 0);

  for(int j: idx) {
    for(int i = 0; i <= m; i++) {
      int g = max(0, x[j]-s[j]-1 - i); // gap
      int r = min(m, x[j]+s[j]+g); // right
      dp[r] = min(dp[r], dp[i]+g);
    }
  }

  int best = m-1;
  for(int i = 1; i <= m; i++) best = min(best, dp[i] + m-i);
  printf("%d\n", best);

  return 0;
}

解法 3

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

int const maxm = 1e5 + 10;
int const INF = 0x3f3f3f3f;

int n, m;
vector<pair<int, int>> ant[maxm];

struct node {
  int cost;
  node *lc, *rc;
  node() { cost = 0; lc = rc = NULL; }
};

node* build(int L, int R) {
  node *u = new node();
  if(L != R) {
    int M = (L+R) / 2;
    u->lc = build(L,   M);
    u->rc = build(M+1, R);
  }

  return u;
}

int query(node *u, int L, int R, int qL, int qR) {
  if(R < qL || qR < L) return INF;
  if(qL <= L && R <= qR) return u->cost;

  int M = (L+R) / 2;
  return min(query(u->lc, L, M, qL, qR), query(u->rc, M+1, R, qL, qR));
}

int update(node *u, int L, int R, int i, int cost) {
  if(i < L || R < i) return u->cost;
  if(L == R) return u->cost = cost;

  int M = (L+R) / 2;
  return u->cost = min(update(u->lc, L, M, i, cost), update(u->rc, M+1, R, i, cost));
}

int main()
{
  scanf("%d%d", &n, &m);

  while(n--) {
    int x, s;
    scanf("%d%d", &x, &s);

    if(x-s <= 1 && m <= x+s) { puts("0"); return 0; }

    for(int cost = 0; 1 <= x-s || x+s <= m; s++, cost++) // 將此天線能升級出的所有天線產出
      ant[min(x+s, m)].emplace_back(max(x-s, 1), cost); 
  }

  node *root = build(1, m);
  for(int i = 1; i <= m; i++) {
    int best = INF;
    for(auto [qL, cost]: ant[i]) // 範圍 [qL, i] 的天線成本為 cost
      best = min(best, query(root, 1, m, qL, i) + cost); // 選擇範圍中有重疊或碰觸的成本最小天線

    if(i == m) printf("%d\n", best);
    update(root, 1, m, i+1, best); // 若其他天線範圍有 i+1 則能與這個成本為 best 的天線合成
  }

  return 0;
}

2020 高階競程 Contest #4 - 題解

首殺 team20_23 (00:10)

解法說明

Subtask 1 O(NC+C)

Subtask 2 O(N+C)

Subtask 3 O(Nlog⁡N)

Subtask 4 O(Nlog⁡N)

標準程式

首殺 team20_21 (00:21)

解法說明

Subtask 1

Subtask 2

Subtask 3

標準程式

首殺 – (-:-)

解法說明

標準程式

首殺 team20_26 (02:21)

解法說明

標準程式

首殺 team20_29 (00:25)

解法說明

標準程式

首殺 team20_06 (00:32)

解法說明

標準程式

首殺 team20_21 (02:09) team20_22

解法說明

標準程式

首殺 – (-:-)

解法說明

解法 1

解法 2

解法 3

標準程式

解法 1

解法 2

解法 3

Read more

2020 Week 7: Dynamic Programming

2020 Week 1: Introduction

2020 Week 4: Search

2020 Week 14: Number theory

Subtask 1
$O (N C + C)$

Subtask 2
$O (N + C)$

Subtask 3
$O (N \log N)$

Subtask 4
$O (N \log N)$