回復 1# may - #include <bits/stdc++.h>
- using namespace std;
- int main(){
- int n, input, ans = 0; //n：數列長度。input：輸入的數字。ans：最長的合法子序列長度，初始化為 0。
- cin >> n;
- unordered_map<int, int> m;//鍵值（key）：數列中的某個數 x。對應的值（value）：x 為終點時，符合條件的最長子序列長度。
- for(int i = 0; i < n; i++) {//讀取數列並更新最長子序列長
- cin >> input; //遍歷輸入數列，每次讀取一個數字 input。
- for(int j = 0; j < 32; j++) { //嘗試所有 2^p（p 在 0~31 之間）來檢查是否能形成合法子序列。
- if(input - (1 << j) >= -1e9) { // 1 << j 代表 2^j，因為 1 << j 會將 1 左移 j 位，等同於 2^j。確保不會超出題目允許的數值範圍（-10^9）
- m[input] = max(m[input], m[input - (1 << j)] + 1);//如果 input - 2^j 已經出現過，那麼 input 可以接續該數，子序列長度 +1。
- }
- if(input + (1 << j) <= 1e9) { //確保不會超過 10^9
- m[input] = max(m[input], m[input + (1 << j)] + 1);//如果 input + 2^j 已經出現過，也可以接續該數，子序列長度 +1。max(m[input], m[input - (1 << j)] + 1)：確保 m[input] 為最長子序列長度。
- }
- }
- ans = max(ans, m[input]);//更新 ans，紀錄目前為止找到的最大子序列長度。
- }
- if(ans == 1) cout << 0 << endl;//如果 ans == 1，代表 所有數字都是獨立的，找不到符合條件的子序列，所以輸出 0。否則，輸出 ans，代表最長的合法子序列長度。
- else cout << ans << endl;
- return 0;
- }
--------------------------------------
測資:
測資00：基本測試（來自題目）
解釋：[1, 3, 5] 是符合條件的最長子序列，長度為 3
6
1 2 5 3 8 10
✅ 預期輸出：
3
測資01：無法形成子序列
解釋：沒有兩個數的差是 2^p，所以答案應該是 0
5
-1 2 5 11 14
✅ 預期輸出：
0
測資 02：所有數字皆可形成子序列
解釋：[2, 4, 6, 10] 是符合條件的最長子序列，長度為 4
6
2 4 6 10 16 18
✅ 預期輸出：
4
測資 03：所有數字相同
解釋：所有數字相同，無法形成有效子序列，因此答案為 0
5
7 7 7 7 7
✅ 預期輸出：
0
測資 04：較大數字測試
解釋：[100, 104, 108, 112] 是符合條件的最長子序列，長度為 4
7
100 104 108 112 120 130 140
✅ 預期輸出：
4
這些測資涵蓋：
基本測試
無法形成子序列的情況
可以形成長子序列
所有數字相同的極端情況
較大數字的測試 |
