ZeroJudge 解題筆記：d566. 秒殺率

作者：王一哲
日期：2025年9月1日


ZeroJudge 題目連結：d566. 秒殺率

解題想法

這題要注意：

1. 此處的解題紀錄排在前面的資料代表時間越晚
2. 第 4 筆測資格式有問題，全部塞在同一行，用 Python 解題需要特別處理這筆測資。

Python 程式碼

理論上這樣寫應該要過關，但是第 4 筆測資格式有問題，全部塞在同一行，要再修改程式碼。

cnt = dict()  # 計數器，是否 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # AC 人數
n = int(input())  # n 筆資料
data = [input().split() for _ in range(n)]  # 先讀完所有的資料
for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
    if name not in cnt:  # 如果 name 不在 cnt 之中
        if state == "AC":  # 如果第一次就 AC
            fir += 1  # fir 加 1
            ac += 1  # ac 加 1
            cnt[name] = True  # cnt[name] 為 True
        else:  # 第一次沒有 AC
            cnt[name] = False  # cnt[name] 為 False
    elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
        ac += 1  # ac 加 1
        cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

使用時間約為 45 ms，記憶體約為 6.2 MB，通過測試。

import sys

cnt = dict()  # 計數器，是否第一次就 AC
fir = 0  # 第一次就 AC 的人數
ac = 0  # 全部 AC 的人數
for line in sys.stdin:  # 讀資料直到 EOF 為止
    data = line.split()  # 先試著分割資料
    if len(data) == 1:  # 如果只有一筆，是 n
        n = int(data[0])
        data = [input().split() for _ in range(n)]  # 先讀完所有的資料
        for name, state in data[::-1]:  # 反向讀取資料，先讀取時間較早的資料
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
    else:  # 為了測資 4 全部塞在一行的狀況
        n = int(data[0])
        for i in range(2*n, 0, -2):  # 反向讀取資料，先讀取時間較早的資料
            name, state = data[i-1], data[i]
            if name not in cnt:  # 如果 name 不在 cnt 之中
                if state == "AC":  # 如果第一次就 AC
                    fir += 1  # fir 加 1
                    ac += 1  # ac 加 1
                    cnt[name] = True  # cnt[name] 為 True
                else:  # 第一次沒有 AC
                    cnt[name] = False  # cnt[name] 為 False
            elif not cnt[name] and state == "AC":  # 如果之前已上傳答案但沒過，而且這次過了
                ac += 1  # ac 加 1
                cnt[name] = True  # cnt[name] 為 True
print(f"{fir*100//ac:d}%")

C++ 程式碼

使用時間約為 7 ms，記憶體約為 948 kB，通過測試。

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main () {
    ios::sync_with_stdio(0); cin.tie(0);
    unordered_map<string, bool> cnt;  // 計數器，是否第一次就 AC
    int fir = 0, ac = 0, n; // 第一次就 AC 的人數，全部 AC 的人數，n 筆資料
    cin >> n;
    string data[n][2];  // 資料
    for(int i=0; i<n; i++) {  // 讀取 n 行
        cin >> data[i][0] >> data[i][1];
    }
    for(int i=n-1; i>=0; i--) {  // 反向讀取資料，先讀取時間較早的資料
        string name = data[i][0], state = data[i][1];  // 名字，狀態
        if (cnt.count(name) == 0) {  // 如果 name 不在 cnt 之中
            if (state == "AC") {  // 如果第一次就 AC
                fir++;  // fir 加 1
                ac++;  // ac 加 1
                cnt[name] = true;  // cnt[name] 為 True
            } else {  // 其它狀態
                cnt[name] = false;  // cnt[name] 為 false
            }
        } else if (!cnt[name] && state == "AC") {  // 如果之前已上傳答案而且沒過，但這次過了
            ac++;  // ac 加 1
            cnt[name] = true;  // cnt[name] 為 true
        }
    }
    cout << fir*100/ac << "%\n";
    return 0;
}