Try   HackMD

2020高階競程課前賽-題解

pA Calculating EAN check digit

  • 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     即為答案

算式：

Ans=(9−(b+3a−1) % 10)

標準程式

#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

  • Task Provider:tsai_mh
  • Task Setter:leo900807

首殺 Mandy (00:04)

解法說明

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

標準程式

#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 藍的競程之旅–魔法藥

  • Task Provider:ian
  • Task Setter:ian

首殺 TedLiao (00:11)

解法說明

本題的魔法藥優先度跟魔法藥的種類相同，假設某個魔法藥的優先度是

j 其實就代表他是第
n−j+1 個加入的藥，依照此方法寫出以下程式。

標準程式

#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 彩彩劈瓦

  • Task Provider:ys
  • Task Setter:ys

首殺 – (-:-)

解法說明

對於目前修瓦值為

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

第

i 天結束了，彩彩能考慮劈不劈
i+1 天的瓦

  • 劈
    則
    dp(i+1,P−min(P,ai+1))=dp(i,P)+min(P,ai+1)
    由於
    P     有可能不夠劈全部的瓦
    ai+1    ，所以取最小值
    min(P,ai+1)
  • 不劈
    則
    dp(i+1,min(P+ai+1,L))=dp(i,P)
    修瓦值的上限為
    L    ，則
    P     只能加至
    L    ，於是取最小值
    min(P+ai+1,L)

而第

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

依照原先狀態定義，最終答案為

max{dp(n,P) | 0≤P≤L}

標準程式

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

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

標準程式

// 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 探望麻衣

  • Task Provider:Miohitokiri5474
  • Task Setter:Miohitokiri5474

首殺 misclicked (01:29)

解法說明

單源最短路裸題

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

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

標準程式

#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 貪心的小明

  • Task Provider:raiso
  • Task Setter:raiso

首殺 Gary (00:17)

解法說明

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

標準程式

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))
Last changed by 
 
NCKU ACM
NCKU 競技程式設計
0
2279

Read more

2020 Week 7: Dynamic Programming

2020 競技程設教材 HackMD Book

Sep 28, 2024
2020 Week 1: Introduction

2020 競技程設教材 HackMD Book

Sep 2, 2024
2020 Week 4: Search

2020 競技程設教材 HackMD Book

Jul 16, 2024
2020 Week 14: Number theory

:+1: 2020 競技程設教材 HackMD Book :+1:

Jun 6, 2024
Read more from NCKU ACM
Published on HackMD