---
# System prepended metadata

title: 2019.10.02 慈中校內初選 題解
tags: [' 題解', ' 108 校內初選', 慈中]

---

---
title: 2019.10.02 慈中校內初選 題解
tags: 慈中, 108 校內初選, 題解
---

# 2019.10.02 慈中校內初選 題解

個人覺得難度排序：$A > E > B > D > C$

## [A. 時間 A + B Problem](https://tcshoj.tw/problem/1006)

本題題型：`scanf 應用、浮點數處理`

`scanf` 叫做格式化輸入
你其實可以這樣拿取時間：

```cpp
scanf("%d:%d:%lf", &H, &M, &S);
```

但浮點數有 Rounding 問題，你可以問問看電腦 0.1 + 0.2 == 0.3

```cpp
if(0.1 + 0.2 == 0.3){
    printf("OK!");
}
else{
    printf("WTF?!");
}
```

這段程式碼一定顯示 `WTF?!`，基本上全世界的電腦都有這個問題

然而這題還要你捨去小數點六位以後

這題有很多種做法，標程是直接暴力刻出，或者可以用字串轉整數，long long 也可以存起來

**標程 tico88612：[#66](https://tcshoj.tw/submission/66)**

**long long 做法 tico88612：[#91](https://tcshoj.tw/submission/91)**

**驗題 jujuga：[#73](https://tcshoj.tw/submission/73)**

出題者垃圾話：自己寫原本是以水題為目標，但出完發現自己 WA 了 4 次

## [B. ChinFish 暗戀對象的告白密碼](https://tcshoj.tw/problem/1007)

本題題型：`string 應用`

$40 \%$ 直接喇過去也可以

```cpp
int ans = 0, enter;
while(cin >> enter){
    ans += enter;
}
cout << ans << '\n';
```

$100 \%$ 遇到數字加上去即可

```cpp
ll ans = 0;
string s;
while(cin >> s){
    ll now = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(isdigit(s[i])){
            now *= 10;
            now += s[i] - '0';
        }
    }
    ans += now;
}
cout << ans << '\n';
```

**標程 tico88612：[#126](https://tcshoj.tw/submission/126)**

**驗題 jujuga：[#145](https://tcshoj.tw/submission/145)**

## [C. 階級](https://tcshoj.tw/problem/1008)

本題題型：`if-else 應用`

本題靈感來源：[Codeforces Round #573 (Div. 2) pA](https://codeforces.com/contest/1191/problem/A)

當初寫還用 Function 呼叫，然後還三個比較，賽後看別人的 Code 才知道 if-else 搭配就好

但只要預先想好結果，再用 if-else 寫出來就 AC 了

（如果你看到這題，馬上知道怎麼寫，推薦你可以去比看看 Codeforces 哦！）

**標程 tico88612：[#94](https://tcshoj.tw/submission/94)**

**驗題 jujuga：[#95](https://tcshoj.tw/submission/95)**

## [D. 選題搶排名](https://tcshoj.tw/problem/1009)

本題題型：`二分搜尋？`

本題敘述改編自`洛谷 P1372`

看完題目的心得，這是排列組合吧？
但 $k$ 有點大，不太可能窮舉到底

我們假設答案為 $x$，那必定 $x \cdot k \leq n$
於是我們可以寫個二分搜尋

**二分搜尋 tico88612：[#92](https://tcshoj.tw/submission/92)**

**驗題 jujuga：[#88](https://tcshoj.tw/submission/88)**

總複雜度 $O(\log n)$，已經在時限內了，完美

等等，這樣也能 AC？

**？？？ tico88612：[#78](https://tcshoj.tw/submission/78)**

把 $x \cdot k \leq n$ 這個式子換成這樣 $x \leq {n \over k}$
然後 C++ 的整數整除的特性就獲得 AC 了
總複雜度，無庸置疑就是 $O(1)$

## [E.【來自深淵】〈序〉阿比斯的奈落至寶](https://tcshoj.tw/problem/1010)

本題題型：`動態規劃 DP`

想要試著出系列題，~~當然還是可能被我腰斬~~

先跟你說，貪心法一定不會過這題

```plain
3 4
0 100 1 100
2 2 2 1
2 2 2 0
```

輸出應為 $7$，貪心法會解成 $104$

動態規劃的中心思想：分解子問題，從小問題推到大問題

走到 $(N, M - 1)$ 只能從 $(N, M)$ 過來

走到 $(N - 1, M)$ 只能從 $(N, M)$ 過來

走到 $(N - 1, M - 1)$ 是不是只能從 $(N - 1, M)$ 或 $(N, M - 1)$ 過來（兩者取最小者）

從小問題選出最優解並且記錄下來，大問題就會被解出來。

**（滾動 DP）標程 tico88612：[#124](https://tcshoj.tw/submission/124)**

**（一般 DP）標程 tico88612：[#125](https://tcshoj.tw/submission/125)**

**（一般 DP）驗題 jujuga：[#185](https://tcshoj.tw/submission/185)**

滾動 DP 差別只是節省了記憶體，想一想，為何可以這樣做呢？

## 結語

Online Judge 現在可以下載測試資料、別人的程式碼（連我的 AC Code 你們都可以觀看）

但是獲得錯誤結果時，先不要急著打開測試資料。

不妨先想想看錯誤在哪裡，哪些特別情況沒有考慮到，如果想不到再去跟其他人討論，如果還是想不到，最後再打開測試資料