---
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 你們都可以觀看)
但是獲得錯誤結果時,先不要急著打開測試資料。
不妨先想想看錯誤在哪裡,哪些特別情況沒有考慮到,如果想不到再去跟其他人討論,如果還是想不到,最後再打開測試資料