---
tags: 成大高階競技程式設計 2020
---

# 2020高階競程課前賽-題解

## [pA Calculating EAN check digit](https://judge.csie.ncku.edu.tw/problems/4)

- Task Provider:tsai_mh
- Task Setter:leo900807

### 首殺 TedLiao (00:04)

### 解法說明

本題為模擬題，僅需依照題目所述：
1. 將第 $2,4,6,8,10,12$ 位數的數字相加為 $a$
2. 將第 $1,3,5,7,9,11$ 位數的數字相加為 $b$
3. 將 $a$ 乘 $3$ 並加上 $b$ 為 $x$ ， $x=3a+b$
4. 將 $x$ 減 $1$ 為 $y$ ， $y=x-1$
5. 將 $y$ 對 $10$ 取餘數為 $z$ ， $z=y\ \%\ 10$
6. $9-z$ 即為答案

算式： $\text{Ans}=(9-(b+3a-1)\ \%\ 10)$

### 標準程式
:::spoiler

#include<bits/stdc++.h>
using namespace std;
int main(){
  int odd = 0, even = 0;
  string str;
  cin >> str;
  for ( int i = 0 ; i < 12 ; ++i )
    if ( i % 2 == 1 )
      even += str[i] - '0';
    else
      odd += str[i] - '0';
  cout << 9 - ( odd + 3 * even - 1 ) % 10 << '\n';
}

:::

## [pB Beaufort scale](https://judge.csie.ncku.edu.tw/problems/5)

- Task Provider:tsai_mh
- Task Setter:leo900807

### 首殺 Mandy (00:04)

### 解法說明

只要照著題目所述判斷條件就好。

### 標準程式
:::spoiler

#include <stdio.h>

int main()
{
  int wind_speed;

  scanf("%d", &wind_speed);

  if(wind_speed < 1)
    printf("Calm\n");
  else if(wind_speed < 4)
    printf("Light air\n");
  else if(wind_speed < 28)
    printf("Breeze\n");
  else if(wind_speed < 48)
    printf("Gale\n");
  else if(wind_speed <= 63)
    printf("Storm\n");
  else 
    printf("Hurricane\n");

  return 0;
}

:::

## [pC 藍的競程之旅--魔法藥](https://judge.csie.ncku.edu.tw/problems/7)

- Task Provider:ian
- Task Setter:ian

### 首殺 TedLiao (00:11)

### 解法說明
本題的魔法藥優先度跟魔法藥的種類相同，假設某個魔法藥的優先度是 $j$ 其實就代表他是第 $n-j+1$ 個加入的藥，依照此方法寫出以下程式。

### 標準程式
:::spoiler

#include <iostream>
using namespace std;

int a[500050];
int n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  int i, j;
  for (i = 1; i <= n; i++) {
    cin >> j;
    a[n - j + 1] = i;
  }

  for (i = 1; i <= n; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}

:::

## [pD 彩彩劈瓦](https://judge.csie.ncku.edu.tw/problems/8)

- Task Provider:ys
- Task Setter:ys

### 首殺 -- (-:-)

### 解法說明
對於目前修瓦值為 $P$，考慮劈與不劈都能影響到最終答案﹔最多共能劈多少瓦
所以令狀態為 $dp(i, P)$ 表示考慮目前有修瓦值 $P$ 且已評估過第 $1$ 到 $i$ 天的瓦

第 $i$ 天結束了，彩彩能考慮劈不劈 $i+1$ 天的瓦
- 劈
則 $dp(i+1, P - \min(P, a_{i+1})) = dp(i, P) + \min(P, a_{i+1})$
由於 $P$ 有可能不夠劈全部的瓦 $a_{i+1}$，所以取最小值 $\min(P, a_{i+1})$
- 不劈
則 $dp(i+1, \min(P+a_{i+1}, L)) = dp(i, P)$
修瓦值的上限為 $L$，則 $P$ 只能加至 $L$，於是取最小值 $\min(P+a_{i+1}, L)$

而第 $1$ 天開始前 $P = 0$，彩彩只能選擇不劈 $dp(1, \min(a_1, L)) = 0$
且求解狀態前將所有狀態值設為**無限小**，表示尚未得解

依照原先狀態定義，最終答案為 $\max\{dp(n, P)\ |\ 0\leq P\leq L\}$

### 標準程式
:::spoiler
#### version 1:

#include<cstdio>
#include<algorithm>
using namespace std;

int const maxn = 3e3 + 10, maxl = 3e3 + 10;
int const INF = 0x3f3f3f3f;

int n, L, a[maxn], dp[maxn][maxl];

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

  for(int i = 0; i < n; i++)
    for(int P = 0; P <= L; P++) dp[i][P] = -INF;
  dp[0][min(L, a[0])] = 0;

  for(int i = 1; i < n; i++)
    for(int P = L; P >= 0; P--) {
      int g = min(P, a[i]);
      if(P-g    >= 0) dp[i][P-g]    = max(dp[i][P-g], dp[i-1][P] + g);
      if(P+a[i] <= L) dp[i][P+a[i]] = max(dp[i][P+a[i]], dp[i-1][P]);
      else dp[i][L] = max(dp[i][L], dp[i-1][P]);
    }

  int ans = 0;
  for(int P = 0; P <= L; P++) ans = max(ans, dp[n-1][P]);

  printf("%d\n", ans);

  return 0;
}

#### version 2:

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll dp[3333][3333], a[3333], n, m;

ll calc(int now, ll p) {
  if (now >= n || dp[now][p]) return dp[now][p];
  ll dif = p - a[now];
  if (dif > 0) {
    return dp[now][p] = max(calc(now + 1, min(m, p + a[now])), a[now] + calc(now + 1, dif));
  } else {
    return dp[now][p] = max(calc(now + 1, min(m, p + a[now])), p + calc(now + 1, 0));
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  cout << calc(0, 0) << endl;
}

:::

## [pE Seeeeeeeeeeeeeg](https://judge.csie.ncku.edu.tw/problems/9)

- Task Provider:Miohitokiri5474
- Task Setter:Miohitokiri5474

### 首殺 -- (-:-)

### 解法說明

很簡單的RMQ。

剛開始看到題目可能會想要幹這種事

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

int data[maxN];

int main(){
  int n, m, l, r, ma, type, cnt = 0;
  cin >> n >> m;
  for ( int i = 1 ; i <= n ; i++ )
    cin >> data[i];
  while ( m-- ){
    cin >> type;
    if ( type == 1 )
      cin >> l >> data[l];
    else{
      ma = -1;
      cin >> l >> r;
      for ( int i = l ; i <= r ; i++ )
        ma = max ( ma, data[i] );
      cout << ma << '\n';
    }
  }
}

於是你就會得到一個TLE。

原因很簡單，暴力解的複雜度最差為 $O (nm)$，通常在時限1000ms的情況下不會過。

官方題解為區間RMQ問題，可以用一個很基礎的資料結構解決——線段樹。（因為以後的課程會講到，所就不在這邊寫落落長的教學，如果有興趣的可以先上網尋找相關資料）

### 標準程式
:::spoiler

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define maxN 100005

int seg[maxN << 2];

void update ( int l, int r, int index, int value, int n ){
  if ( l == r )
    seg[n] = value;
  else{
    int mid = ( l + r ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
    if ( index <= mid )
      update ( l, mid, index, value, leftSon );
    else
      update ( mid + 1, r, index, value, rightSon );

    seg[n] = max ( seg[leftSon], seg[rightSon] );
  }
}

int query ( int l, int r, int nowL, int nowR, int n ){
  if ( l <= nowL && nowR <= r )
    return seg[n];
  int mid = ( nowL + nowR ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
  if ( r <= mid )
    return query ( l, r, nowL, mid, leftSon );
  if ( mid < l )
    return query ( l, r, mid + 1, nowR, rightSon );
  return max ( query ( l, r, nowL, mid, leftSon ), query ( l, r, mid + 1, nowR, rightSon ) );
}

int main(){
  ios::sync_with_stdio ( false );
  cin.tie ( 0 );
  cout.tie ( 0 );

  int n, m, l, r, value, type;
  cin >> n >> m;
  for ( int i = 1 ; i <= n ; i++ ){
    cin >> value;
    update ( 1, n, i, value, 1 );
  }
  while ( m-- ){
    cin >> type >> l >> r;
    if ( type == 1 )
      update ( 1, n, l, r, 1 );
    else
      cout << query ( l, r, 1, n, 1 ) << '\n';
  }
}

:::

## [pF 探望麻衣](https://judge.csie.ncku.edu.tw/problems/10)

- Task Provider:Miohitokiri5474
- Task Setter:Miohitokiri5474

### 首殺 misclicked (01:29)

### 解法說明

單源最短路裸題

標程為 SPFA，不過因為用了怪怪的優化方法，所以下面放的 code 是 Dijkstra

想要 SPFA 做法的可以來問（？

### 標準程式
:::spoiler

#include<bits/stdc++.h>

using namespace std;

#define maxN 100005

vector < pair < int, long long > > edges[maxN];
long long dis[maxN];

int main(){
  ios::sync_with_stdio ( false );
  cin.tie ( 0 );
  cout.tie ( 0 );

  int n, m, u, v, w, now;
  long long d;
  cin >> n >> m;
  while ( m-- ){
    cin >> u >> v >> w;
    edges[u].emplace_back ( v, w );
    edges[v].emplace_back ( u, w );
  }
  priority_queue < pair < long long, int >, vector < pair < long long, int > >, greater < pair < long long, int > > > pq;
  memset ( dis, 0x3f3f3f3f3f3f3f, sizeof ( dis ) );
  dis[0] = 0;
  pq.push ( make_pair ( 0, 0 ) );
  while ( !pq.empty() ){
    now = pq.top().second, d = pq.top().first;
    pq.pop();
    if ( dis[now] < d )
      continue;
    for ( auto i: edges[now] ){
      if ( dis[i.first] > d + i.second ){
        dis[i.first] = d + i.second;
        pq.push ( make_pair ( dis[i.first], i.first ) );
      }
    }
  }

  for ( int i = 0 ; i < n ; i++ )
    cout << dis[i] << ' ';
  cout << '\n';
}

:::

## [pG 貪心的小明](https://judge.csie.ncku.edu.tw/problems/11)

- Task Provider:raiso
- Task Setter:raiso

### 首殺 Gary (00:17)

### 解法說明
不要偷懶，考慮所有可能性(6種)，然後你就知道了，但是因為位數很高，使用 int 會 overflow ，所以...
以下提供的範例很長，當然可以寫個更簡潔，但是這裡先使用最暴力的方法，因為暴力是入門的第一課 - **寫出你的想法**。
### 標準程式
:::spoiler
#### C++ code

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

long long tennn(long long a) {
  int c = 0;
  while(a >= 10) a /= 10, c++;
  long long b = 1;
  for(int i = 0; i < c+1; i++) b *= 10;
  return b;
}

int main() {
  long long B[3];
  long long A[6] = {};
  for(int i = 0; i < 3; i++) cin >> B[i];
  int c = 0;
  for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++) if(i != j && i != k && j != k) {
    A[c++] = B[i] + B[j]*tennn(B[i]) + B[k] * tennn(B[i]) * tennn(B[j]);
  }
  long long maxi  =  0;
  for(int i = 0; i < c; i++) maxi = maxi > A[i]? maxi: A[i];
  cout << maxi << endl;
  return 0;
}

#### Python code

a, b, c = input().strip().split(' ')
s = [a+b+c,a+c+b,b+a+c,b+c+a,c+a+b,c+b+a]
s = map(int, s)
print(max(s))

:::