1. 程式考試
用迴圈跑過所有的提交紀錄即可，利用變數紀錄最高分數的時間點以及有幾次嚴重錯誤。
複雜度: O(k)
主要知識: 條件判斷與迴路 (conditional expressions and loop)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int k;
cin >> k;
int wrong = 0, maxScore = -2, maxTime = 0;
for(int i = 1;i <= k;i++){
int t, s;
cin >> t >> s;
if(s == -1) wrong ++; // 嚴重錯誤
if(s > maxScore){ // 最高分數
maxScore = s; // 更新時間，最高分數
maxTime = t;
}
}
cout << max(0, maxScore - k - wrong * 2) << ' ' << maxTime << '\n';
}2. 造字程式
利用二維陣列來模擬每次修改後的字串，最後一起輸出。
我這邊是採用 1-base 的寫法，所以輸入一開始的字串後要把每個字元往後移從 0-base 變成 1-base。
複雜度: O(qk)
主要知識: 條件判斷與迴路 (conditional expressions and loop)，陣列與結構 (arrays and structures)
#include <bits/stdc++.h>
using namespace std;
char ans[25][25]; //
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int k, q, r;
cin >> k >> q >> r;
cin >> ans[0]; // ans[i][j] 紀錄第i次修改後 第j個字元是什麼
for(int i = k;i >= 1;i--){ // 把原本的字串往後移變成 1-base
ans[0][i] = ans[0][i-1];
}
for(int i = 0;i < q;i++){
for(int j = 1;j <= k;j++){
int x; cin >> x;
ans[i+1][x] = ans[i][j];
}
}
for(int i = 1;i <= r;i++){
for(int j = 1;j <= q;j++){
cout << ans[j][i];
}
cout << '\n';
}
}3. 先加後乘與函數
這題有主要幾個難點:
- 運算處理要先加後乘
- f 函數需要處理
這邊我們利用遞迴的想法來實作，每次傳入一個現在的字串
每次遇到 f 字串就將 f 字串整個遞迴下去尋找答案
剩下就是數字的處理以及一些實作細節:
- 把字串轉換成數字時可以使用 C++內建的 stoi 函數
- 需要紀錄括號數量，以便判斷傳入 f 的參數要在哪裡結束以及 f 在哪裡結束
- 如果不這樣判斷的話，當 f 函式中有第二個 f 函式就會出現問題，因為不知道哪部分是屬於哪個地方 Ex. f(1, f(1, 2), 3)
- 在跑過每個字元時，先將加法的部分轉成數字處理好，再跑完整個迴圈時再一起乘，達到先加後乘的效果
複雜度: O(n^2)
主要知識: 函數呼叫與遞迴 (function call and recursion)
#include <bits/stdc++.h>
#define ll long long
#define ft first
#define sc second
using namespace std;
ll f(string s){ // 模擬
ll cur = 0; // 紀錄
vector <ll> mul; // 紀錄最後有哪些數字需要乘起來
string num = ""; // 紀錄現在的數字
string func = ""; // 紀錄 f 函式以便之後整個遞迴下去算
int cnt = 0; // 紀錄有幾個括號 （判斷要在什麼時候停下來)
if(s[0] == 'f'){ // 如果我們現在要處理 f 字串
ll mn = INT_MAX, mx = 0;
cnt = 1; // 從第二個開始跑
for(int i = 2;i < s.size();i++){ // 所以第一個括號先加上去 (cnt = 1)
if(s[i] == '(') cnt++;
if(s[i] == ')') cnt--; // 遇到左括號 + 1 右括號 - 1
if(i == s.size() - 1 || (cnt == 1 && s[i] == ',')){ // 在這之前的所有括號都匹配完了
ll tmp = f(num);
mn = min(mn, tmp);
mx = max(mx, tmp);
num = "";
} else {
num += s[i];
}
}
return mx - mn;
} else {
bool found = false;
for(int i = 0;i <= s.size();i++){
if(s[i] == 'f' || found){
func += s[i];
found = true;
if(s[i] == '('){
cnt ++;
} else if(s[i] == ')'){
cnt --;
if(cnt == 0){ // f 函數結束
cur += f(func); // 遞迴找到這段的答案
func = "";
found = false;
}
}
} else {
if(i == s.size() || s[i] == '*'){
if(!num.empty()) cur += stoi(num);
mul.push_back(cur); // 將數字加進去
num = "";
cur = 0;
} else if(s[i] == '+'){
if(!num.empty()) cur += stoi(num); // 將數字加起來
num = "";
} else if('0' <= s[i] && s[i] <= '9'){
num += s[i];
}
}
}
// 最後在一併把所有數字乘起來
if(mul.empty()) return 0;
else {
ll ans = 1;
for(ll x : mul) ans *= x;
return ans;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
cout << f(s) << '\n';
}4. 機器出租
這題算是非常經典的一道題目，在cses上有幾乎一樣的一題: Movie Festival II
部分分的解法在 CSES 上面也有: Movie Festival, 題解
這題主要是利用 greedy 的想法先將活動用結束時間排序，每次都選取結束時間最早的活動給機器。每次都選結束最早的活動才能讓機器比較快給下一個活動使用。而要分配給哪台機器則是利用 C++ 內建的 multiSet 在 O(log n)的時間來尋找可以用的機器 (結束時間比這個活動開始時間還要早)。
複雜度: O(nlogn)
主要知識: 貪心法則 (greedy method), 排序 (sorting),
#include <bits/stdc++.h>
#define ll long long
#define ft first
#define sc second
using namespace std;
bool cmp(pair <int,int> a, pair <int,int> b){
if(a.second == b.second) return a.first > b.first;
else return a.second < b.second;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
multiset <int> s;
vector <pair<int,int> > a(n);
for(int i = 0;i < n;i++){
cin >> a[i].ft;
}
for(int i = 0;i < n;i++){
cin >> a[i].sc;
}
sort(a.begin(), a.end(), cmp);
for(int i = 0;i < k;i++){
s.insert(0);
}
int ans = 0;
for(int i = 0;i < n;i++){
auto it = s.lower_bound(a[i].first);
if(it == s.begin()) continue;
else {
s.erase(--it);
s.insert(a[i].second);
ans++;
}
}
cout << ans << '\n';
}
發表迴響