ZeroJudge 解題筆記：e284. 放暑假了!!!!!

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


ZeroJudge 題目連結：e284. 放暑假了!!!!!

解題想法

這題主要考輸入、輸出優化，因為測資數量極大，如果沒有優化輸入、輸出會超時。在 Python 我習慣用 sys.stdin.readlines() 一次讀取所有的測資，並將所有的輸出存在串列 result 之中，最後再用 sys.stdout.write("".join(result)) 一次印出所有答案。在 C++ 如果要用 cin 及 cout，必須加上 ios::sync_with_stdio(0); cin.tie(0);，不然就是改用 scanf 及 printf。事先用字典或集合建表，儲存 $2^0$ 到 $2^31$ 對應的值，讀取測資之後再判斷這個數字是否在表格之中，這樣速度會比較快。但是經過實測之後發現，C++ 的 map 及 unordered_map 都很慢，要用 set 才能過關； Python 的 dict, defaultdict, set 都能過關。

Python 程式碼

用 dict 建表，使用時間約為 4.2 s，記憶體約為 413.6 MB，通過測試。

import sys

table = dict()
x = 1
for _ in range(32):
    table[x] = True
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

用 set 建表，使用時間約為 4.1 s，記憶體約為 418.2 MB，通過測試。

import sys

table = set()
x = 1
for _ in range(32):
    table.add(x)
    x <<= 1

result = []
lines = sys.stdin.readlines()
for line in lines:
    n = int(line)
    if n in table: result.append("Yes\n")
    else: result.append("No\n")
sys.stdout.write("".join(result))

C++ 程式碼

用 set 建表，使用時間約為 1.3 s，記憶體約為 368 kB，通過測試。

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 建表，2**0 ~ 2**31
    set<int> table;
    int b = 1;
    for(int i=0; i<32; i++) {
        table.insert(b);
        b <<= 1;
    }
    // 主要的解題過程，盡量減少輸入、輸出次數
    int n;
    while(cin >> n) {
        if (table.count(n) == 1) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

用 set 建表，將答案連接成一個很長的字串再輸出，使用時間約為 1 s，記憶體約為 29.7 MB，通過測試。

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 建表，2**0 ~ 2**31
    set<int> table;
    int b = 1;
    for(int i=0; i<32; i++) {
        table.insert(b);
        b <<= 1;
    }
    // 主要的解題過程，盡量減少輸入、輸出次數
    string results = "";
    int n;
    while(cin >> n) {
        if (table.count(n) == 1) results += "Yes\n";
        else results += "No\n";
    }
    cout << results;
    return 0;
}

用 set 建表，用 puts 輸出，使用時間約為 0.9 s，記憶體約為 248 kB，通過測試。

#include <cstdio>
#include <set>
using namespace std;

int main() {
    // 建表，2**0 ~ 2**31
    set<int> table;
    int b = 1;
    for(int i=0; i<32; i++) {
        table.insert(b);
        b <<= 1;
    }
    // 主要的解題過程，盡量減少輸入、輸出次數
    int n;
    while(scanf("%d", &n) != EOF) {
        if (table.count(n) == 1) puts("Yes");
        else puts("No");
    }
    return 0;
}