APCS 2023/1/8 實作題 解題報告

2023/1/31 更

兩眼一黑 我的年份竟然打錯了

第一題

思路

直接輸入 算一算就好了

Code

點我看Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int num;
    cin >> num;

    int max_score = -99, max_time = 0, bad_count = 0;
    int score;
    int input_score, input_time;

    for (int i = 0; i < num; i++)
    {
        cin >> input_time >> input_score;
        if(input_score > max_score)
        {
            max_time = input_time;
            max_score = input_score;
        }
        if(input_score == -1)
        {
            bad_count++;
        }
    }

    score = max_score - num - bad_count * 2;
    if(score < 0)
        score = 0;

    cout << score << " " << max_time;
}

第二題

思路

直接輸入 思考一下對應關係
注意輸出是要輸出哪一行，for i {for j} 輸出要array[j][i]
就好了

Code

點我看Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int string_len, output_len, output_line;
    cin >> string_len >> output_len >> output_line;

    vector<string> str(output_len + 1, string(string_len, ' '));
    cin >> str[0]; 

    int index;
    for (int i = 1; i <= output_len; i++)
    {
        for (int j = 0; j < string_len; j++)
        {
            cin >> index;
            str[i][index - 1] = str[i - 1][j]; // 將上個字串 j 放到，新的字串 index(輸入) 的位置
        }
    }

    for (int i = 0; i < output_line; i++)
    {
        for (int j = 1; j <= output_len; j++) // str[0]原始字串不用輸出，注意輸出的排列方向
            cout << str[j][i];
        cout << "\n";
    }
}

第三題

我太爛了，現場沒f()來不及寫 :(

思路

我用遞迴解，定義兩個函數:

parse(string s)

用來解析字串，決定要先用哪個運算符號，將符號左右的數字做 parse(左字串) * or + parse(右字串)
或將判斷字串並將其丟進f(整個字串)運算，或是沒有運算符號則回傳數字。

f(string s)

功能如題目中所述，最大-最小，解析()及,，其中每個參數就丟進去parse()。

舉例

input: 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2))*2

parse( 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2))*2 )
parse( 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2)) ) * parse( 2 )
parse( parse( 12 ) + parse( f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2)) ) ) * parse( 2 )

parse( parse( 12 )
	+  parse( f( parse( 13 ) ,
		      parse( 2+f(8,1+2*3) ) ,
		      parse( 1+1*f(20,4)*f(2)) 
	            ) 
	         ) 
        )  *  parse( 2 )

parse( parse( 12 )
	+  parse( f( parse( 13 ) ,
		      parse( parse( 2 ) 
		              + parse ( f(8,1+2*3) ) ),
		      parse( parse( 1+1 )
		              * parse( f(20,4)*f(2)) ) 
	            ) 
	         ) 
	 )  *  parse( 2 )

… 然後繼續套 我懶得寫了 HackMD排版有點困難

Code

點我看Code

#include <bits/stdc++.h>
using namespace std;

// declaring some function
uint64_t f(const string &s);
uint64_t parse(const string &s);
uint64_t to_ll(const string &s);

// 有種東西叫 std::stoll 可以做一樣的事情
// 考試時code::blocks有InteliSense但幾乎殘廢，我也沒有背太多語法，就手刻一個
uint64_t to_ll(const string &s) // convert string to long long
{
    uint64_t out = 0;
    for (int i = 0; i < (int)s.size(); i++)
    {
        out += (s[s.size() - 1 - i] - '0') * pow(10, i);
    }
    return out;
}

uint64_t parse(const string &s)
{
    int type = 0, prev_type = 0;
    int index = -1;
    int layer;
    int len = (int)s.size();

    for (int i = 0; i < len; i++)
    {
        if (s[i] == '*')
            type = 3;
        else if (s[i] == '+')
            type = 2;
        else if (s[i] == '(') // f(
        {
            type = 1;
            layer = 0;
            for (; i < len; i++) // 1. 解析嵌套的括號 如: ( (左右的括號跳過) ) ，以跳過f()中的+以及*，
            {
                if (s[i] == '(')
                    layer++; // starting from 1 here
                else if (s[i] == ')')
                    layer--;
                if (layer == 0)
                    break;
            }
        }

        if (type > prev_type) // 找到的運算符號 優先級更高
        {
            prev_type = type;
            index = i;
        }
    }

    if (prev_type == 0) // 如果沒有運算符號，回傳數字
        return to_ll(s);
    else if (prev_type == 3) // 切字串，分別計算運算符號前後的兩個字串
        return parse(s.substr(0, index)) * parse(s.substr(index + 1));
    else if (prev_type == 2)
        return parse(s.substr(0, index)) + parse(s.substr(index + 1)); 
    else if (prev_type == 1)
        return f(s); // 把整個字串丟給f()處理 這邊字串只會出現 "f(1+2, 3)" 之類的，不用再切
    else
        return 99999999; 
}

uint64_t f(const string &s)
{
    uint64_t max_num = 0, min_num = INT64_MAX -1, num;
    int index_l = -1, index_r = 1, len = (int)s.size();
    int layer = 0;
    for (int i = 2; i < len; i++) // 從f( 也就是第3個字元開始。
    {
        if ((s[i] == ',' || s[i] == ')') && layer == 0) // 對每個以,分隔的參數做運算，取最大最小值
        {
            index_l = index_r + 1;
            index_r = i;
            num = parse(s.substr(index_l, index_r - index_l));
            max_num = max(max_num, num);
            min_num = min(min_num, num);
        }
        if (s[i] == '(') // 解析嵌套的括號 (())
            layer++;
        else if (s[i] == ')' && layer != 0)
            layer--;
    }
    return max_num - min_num;
}

int main()
{
    string in;
    cin >> in;

    cout << parse(in);
}

考試時原本的想法

用stack解，速度應該會更快，而且不會有遞迴深度過深的問題。
但我當時沒有想到照正確順序push進stack的方法，就用了遞迴，對我來說比較好實現。
之後再來動腦

第四題

思路

• Greedy
  • 將event按照結束時間排序。由小到大。如果結束時間相同，則按照開始時間排序。由小到大。
  • 對每一筆event判斷，將event安排給前一個結束時間最大的machine
• 具體上為什麼，可以用測試資料2畫時間線圖(如下圖)，就能理解為什麼這樣排。
• 這是我試過幾乎每一種Greedy的方式+犧牲一張數學考卷成績以獲得思考得出的結論

Code

• format是c++20的東西 拿來debug用的 不用理他

點我看Code

// #define FMT_HEADER_ONLY
// #include <fmt/include/fmt/core.h>

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int num_event, num_machine;
    cin >> num_event >> num_machine;

    vector<pair<int, int>> event(num_event); // start, end
    for (int i = 0; i < num_event; i++)
        cin >> event[i].first;
    for (int i = 0; i < num_event; i++)
        cin >> event[i].second;

    sort(event.begin(), event.end(), // sort by end time first, if same sort by start time (small -> large)
         [](pair<int, int> a, pair<int, int> b) -> bool
         { if(a.second == b.second) return a.first < b.first;
            else return a.second < b.second; });

    // for (int i = 0; i < num_event; i++)
    //     fmt::print("{}: {}, {}\n", i, event[i].first, event[i].second);

    int ans = 0, which_machine_max = -10; // index of machine
    vector<int> machine_busy(num_machine, -1);

    for (int i = 0; i < num_event; i++) // 掃過每個event
    {
        for (int j = 0; j < num_machine; j++)
        {
            if (machine_busy[j] < event[i].first && which_machine_max == -10)                                // if機器可用且沒有其他數字。如果放到下面，machine_busy[which_machine_max] 會超過範圍。
                which_machine_max = j;                                                                       // 存index
            else if (machine_busy[j] < event[i].first && machine_busy[j] >= machine_busy[which_machine_max]) // if機器可用且最大
                which_machine_max = j;                                                                       // 存index
        }
        // fmt::print("\nwhich_machine_max: {}\nmachine busy: {}\nevent: {}\nans: {}\n", which_machine_max, fmt::join(machine_busy, ", "), fmt::join(event[i], ", "), ans);

        if (which_machine_max != -10)
        {
            machine_busy[which_machine_max] = event[i].second;
            ans++;
            which_machine_max = -10;
        }
    }

    cout << ans << endl;
}

---

後記

APCS初體驗

這是我第一次考APCS，之前只有在ZJ上刷了幾題。資料結構跟演算法完全沒學，只看過資訊之芽的一點講義，我連BFS怎麼跑都沒有實作過。
選擇題部分，我覺得就是在考ability to read bad written code with bugs and without comment，寫起來很令人煩躁且無聊。好幾題都要腦中憑空模擬，或者去猜他背後的數學式子，感覺在寫數學考卷。
上機實作就是熟練度跟速度，我覺得第三題不難但很花時間(與ZJ上的考古題相比)。第四題當時我有想到Greedy，但我覺得總沒那麼簡單，因為考前看了資芽的Greedy，寫說"你覺得Greedy是最佳解很可能只是特例"，我就沒寫，專心弄第三題(結果也沒寫完 :( )。

另外 幾個疑問

• 為什麼不能Alt + Tab

  • 我都按Alt + Tab
  • 隔幾秒發現不能用，只好用滑鼠切換視窗
  • 非常影響心情

• 為什麼Terminal沒辦法貼上

  • 測資要手打
  • 非常影響心情

• 為什麼IDE那麼難用

  • Eclipse我根本看不懂怎麼用
  • Code::blocks的intellisense大概只有打i會出現int，其他時候都不能用 建議改名idiotsense
  • Code::blocks沒辦法用GDB Debugger
  • 沒有深色模式，我的眼睛:
    
  • 也許是平常VScode/VS2022太好用了，沒intellisense+auto format就要手打/手動排版很多東西，變數名稱不能取太長。

• 鍵盤滑鼠

  • 沒有習慣的機械鍵盤跟滑鼠，寫Code的效率低了許多。

考完試後一天

學長跟我抱怨他一直95%，為什麼第三題會少五分啦QQ (最後一筆Wrong answer: 153)
我們測了很多資料，都覺得沒問題
後來直接問出題者
看來出題者也累了ww (仍感謝有人花自己的時間搬運題目、生測資)
還我消失的五個小時

rejudge中 各位95%可以回去看看