【題解】ZeroJudge d123: 11063 – B2-Sequence

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d123

【作法-1】array

  • 每個數值 bi 皆為整數,且 bi ≤ 10000。所有的 bi + bj (i <= j)皆 ≤ 20000。
  • 宣告一個陣列 sum[maxn] 來紀錄 bi + bj 出現的次數。如果有某個值重複出現,則此數列不是「B2數列」。
#include <iostream>
using namespace std;
#define maxn 20005

int main() {
    int n, Case = 1;
    while (cin >> n) {
        int b[n], sum[maxn];
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        for (int i = 0; i < maxn; i++) {
            sum[i] = 0;
        }
        bool flag = true;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int x = b[i] + b[j];
                if (sum[x]) {
                    flag = false;
                    break;
                } else {
                    sum[x] = 1;
                }
            }
            if (!flag) break;
        }
        if (flag) cout << "Case #" << Case++ << ": It is a B2-Sequence.\n\n";
        else cout << "Case #" << Case++ << ": It is not a B2-Sequence.\n\n";
    }
    return 0;
}

【作法-2】set

  • 使用set紀錄出現過的數字和,遇到重複的話,就可以判定不是B2-Sequence。
#include <iostream>
#include <set>
using namespace std;

int main() {
    int N;
    int Case = 1;
    while (cin >> N){
        int a[N];
        for (int i = 0; i < N; i++){
            cin >> a[i];
        }
        set <int> st;
        bool flag = true;
        for (int i = 0; i < N-1; i++){
            for (int j = i; j < N; j++){
                int tmp = a[i] + a[j];
                if (st.count(tmp)) {
                    flag = false;
                    break;
                }
                st.insert(tmp);
                
            }
            if (!flag) break;
        }
        cout << "Case #" << Case++;
        if (flag) cout << ": It is a B2-Sequence.\n\n";
        else cout << ": It is not a B2-Sequence.\n\n";
    }
}

Python code (credit: Amy Chou)

TC = 1

while True:
    try:
        N = int(input())
        a = list(map(int, input().split()))
        st = set()
        flag = True
        for i in range(N):
            for j in range(i, N):
                tmp = a[i] + a[j]
                if tmp in st:
                    flag = False
                    break
                st.add(tmp)
            if not flag:
                break
        
        print(f"Case #{TC}: It is ", end="")
        if not flag:
            print("not ", end="")
        print("a B2-Sequence.")
        print()
        TC += 1
    except:
        break
分享本文 Share with friends