第一場比賽 題解
=
> 真材實料，百練自得！
# [z001](https://judge.cp.ccns.io/problem/z001)：
重新解析題義，題目的意思就是 1. 找出整個數列裡最大的數，2. 找出此數在此數列中的最長連續出現次數。
特別要注意的是，本題會有許多人寫出可以 RE 的 code，通常是在讀數列的時候沒有擋好邊界，衝出宣告範圍。某個人就因為在 Codeforces 中四分鐘快速刷掉本題，結果賽後被 hack，因此很久都不打 Codeforces。
> 橘色的也一樣la ==
以下完整解題程式碼：
```cpp
#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](https://judge.cp.ccns.io/problem/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。
以下完整解題程式碼：
```cpp
#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](https://judge.cp.ccns.io/problem/z003)：
當一開始看到這題的時候，我們會想要去模擬，但是看到他的範圍之後，粗估一下複雜度發現，模擬的複雜度太大，這時候會有兩個想法，`O(logN)` 或是 `數學解`，自此之後還是沒有想法，所以只好老老實實做實驗，把同一個`root`的數字全部找出來，這時候會發現他們都差`9`，到這裡這題就差不多了，只剩下實現這個數學解的想法。
```cpp
#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](https://codeforces.com/contest/1110/problem/C)，[參考解答](https://codeforces.com/contest/1110/submission/49595286)。
# [z004](https://judge.cp.ccns.io/problem/z004)：
> 其實這題在第二週的練習題中有出 [name=ys]
很明顯的我們需要依序從**大到小**把傷害給挑出來按
問題是有個限制是：連續按超過 $k$ 次按鈕，就失敗
那麼就想看看如何在**不造成失敗**的情況下，依序從**大到小**把傷害給挑出來按
注意到**切換到不同**的按鈕之前，我們至多只能按 $k$ 次
當然是要按好按滿 :+1:
那將**連續相同**的按鈕，分為一組，從大到小將傷害給挑出來按，直到按了 $k$ 次就別按了
一組連續相同按鈕有個左界 $l$，接著找出右界 $r$ (採用左閉右開)
```cpp
while(r < n && s[l] == s[r]) r++;
```
而找到連續相同的一組，就將傷害排序，以方便從**大到小**把傷害給挑出來按
```cpp
sort(a+l, a+r);
```
然後累加前 $k$ 項
```cpp
sum = accumulate(a+max(l, r-k), a+r, sum);
```
要特別注意如果這連續按鈕**個數少於 $k$**，要做點處裡： `max(l, r-k)`
以下完整解題程式碼：
```cpp
#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](https://judge.cp.ccns.io/problem/z005)：
模擬切格子的步驟就行了
從最高的地方 (`maxh`) 一路一層層往最低處 (`1`) 看
```cpp
for(int i = maxh; i >= 1; i--) {
:
.
}
```
對於每一層，收集**該層**的**格子**們 $s$，收集完存到累計的 `sum` 中
```cpp
sum += s;
```
但是當該層的格子加進 `sum` 中會超過 $k$ 時，就不能再收集了
此時**這個位置**就是要 slice 的地方
```cpp
if(sum + s > k) slice++, sum = 0;
```
而當 $s$ 等於 $n$ 時，也就是所有 tower 都**一樣高**了，就可以結束了
```cpp
if(s == n) {
if(sum) slice++;
break;
}
```
這裡特別注意 `sum` 如果還有東西，表示結束前還要切一刀 (slice)
在以上步驟之前，我們還得問，如何知道**某層**的 $s$ 為何？
```cpp
for(int i = 0; i < n; i++) scanf("%d", &h), s[h]++;
for(int i = maxh; i >= 1; i--) s[i-1] += s[i];
```
以下完整解題程式碼：
```cpp
#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;
}
```
Sign in with Wallet
Connect another wallet