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