第一場比賽 題解

真材實料，百練自得！

z001：

重新解析題義，題目的意思就是 1. 找出整個數列裡最大的數，2. 找出此數在此數列中的最長連續出現次數。

特別要注意的是，本題會有許多人寫出可以 RE 的 code，通常是在讀數列的時候沒有擋好邊界，衝出宣告範圍。某個人就因為在 Codeforces 中四分鐘快速刷掉本題，結果賽後被 hack，因此很久都不打 Codeforces。

橘色的也一樣la ==

以下完整解題程式碼：

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

int main() {
  int n, m, i, j, k;
  cin >> n;
  int d[100010];
  int maxx = 0;
  for (i = 0; i < n; i++) {
    cin >> d[i];
    maxx = max(maxx, d[i]);
  }
  int maxl = 0, cnt;
  for (i = 0; i < n; i++) {
    cnt = 0;
    while (d[i] == maxx && i < n) {
      cnt++;
      i++;
    }
    maxl = max(maxl, cnt);
  }
  cout << maxl << endl;
  return 0;
}

z002：

大家看完題目之後應該都可以很明顯的看出要把內容從大排到小，問題是方法，在本題中，我們設定了記憶體限制只有 10MB，計算過後可以發現，直接用 int 肯定是不會過的。

特別要注意的是，在某些比賽中，如果超過記憶體用量，也可能會給 RE 而不是 MLE，本題有兩種解題方法，其一，是盡可能減少變數的記憶體空間，使用 char 或 int8_t 儲存變數，並且 sort，不過這並不是很好，原因是輸入的數字最多有

$5\cdot {10}^6$ 個，

$n\log n$ 的解法會來到大概

${10}^8$ 的複雜度，雖然就結果來說，是可以 AC 的，不過有更好的解法：counting sort。

counting sort 紀錄每個數字出現的次數，像本題，數字只會有 1 ~ 100，因此很適合 counting sort。

以下完整解題程式碼：

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

int n, tmp, i;
int cnt[110];

int main() {
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> tmp;
    cnt[tmp]++;
  }
  for (i = 100; i > 0; i--) {
    while (cnt[i] --> 0) {
      cout << i << " ";
    }
  }
  cout << endl;
  return 0;
}

z003：

當一開始看到這題的時候，我們會想要去模擬，但是看到他的範圍之後，粗估一下複雜度發現，模擬的複雜度太大，這時候會有兩個想法，O(logN) 或是 數學解，自此之後還是沒有想法，所以只好老老實實做實驗，把同一個root的數字全部找出來，這時候會發現他們都差9，到這裡這題就差不多了，只剩下實現這個數學解的想法。

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

int main() {
  int n;
  cin >> n;
   
  while(n--) {
    long long k, x;
    cin >> k >> x;
    cout << (k-1)*9+x << endl;;
  }
  
  return 0;
}

PS: 有興趣想要試試看如何做實驗搭配思考的同學可以試試看這題 Codeforces-1110C，參考解答。

z004：

其實這題在第二週的練習題中有出 ys

很明顯的我們需要依序從大到小把傷害給挑出來按
問題是有個限制是：連續按超過

$k$ 次按鈕，就失敗
那麼就想看看如何在不造成失敗的情況下，依序從大到小把傷害給挑出來按

注意到切換到不同的按鈕之前，我們至多只能按

$k$ 次
當然是要按好按滿

那將連續相同的按鈕，分為一組，從大到小將傷害給挑出來按，直到按了

$k$ 次就別按了

一組連續相同按鈕有個左界

$l$，接著找出右界

$r$ (採用左閉右開)

while(r < n && s[l] == s[r]) r++;

而找到連續相同的一組，就將傷害排序，以方便從大到小把傷害給挑出來按

sort(a+l, a+r);

然後累加前

$k$ 項

sum = accumulate(a+max(l, r-k), a+r, sum);

要特別注意如果這連續按鈕個數少於

$k$，要做點處裡： max(l, r-k)

以下完整解題程式碼：

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

int const maxn = 2e5 + 100;

int n, k, a[maxn];
string s;
long long int sum = 0;

int main()
{
  cin >> n >> k;
  for(int i = 0; i < n; i++) cin >> a[i];
  cin >> s;

  int r = 0;
  while(r < n) {
    int l = r;
    while(r < n && s[l] == s[r]) r++;

    sort(a+l, a+r);
    sum = accumulate(a+max(l, r-k), a+r, sum);
  }

  cout << sum << endl;

  return 0;
}

z005：

模擬切格子的步驟就行了

從最高的地方 (maxh) 一路一層層往最低處 (1) 看

for(int i = maxh; i >= 1; i--) {
  :
  .
}

對於每一層，收集該層的格子們

$s$，收集完存到累計的 sum 中

sum += s;

但是當該層的格子加進 sum 中會超過

$k$ 時，就不能再收集了
此時這個位置就是要 slice 的地方

if(sum + s > k) slice++, sum = 0;

而當

$s$ 等於

$n$ 時，也就是所有 tower 都一樣高了，就可以結束了

if(s == n) {
  if(sum) slice++;
  break;
}

這裡特別注意 sum 如果還有東西，表示結束前還要切一刀 (slice)

在以上步驟之前，我們還得問，如何知道某層的

$s$ 為何？

for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;
for(int i = maxh; i >= 1; i--) s[i-1] += s[i];

以下完整解題程式碼：

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

int const maxh = 2e5 + 10;

int n, k, s[maxh];

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

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

  for(int i = maxh-1; i >= 1; i--) s[i-1] += s[i];

  int sum = 0, ans = 0;
  for(int i = maxh-1; i >= 1; i--) {
    if(s[i] == n) {
      if(sum) ans++;
      break;
    }

    if(sum + s[i] > k) ans++, sum = 0;

    sum += s[i];
  }

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

  return 0;
}