回復 1# may - #include <bits/stdc++.h>
- //#include <iostream>
- //#include <vector>
- //#include <unordered_map>
- //#include <unordered_set>
- //#include <algorithm>
- using namespace std;
- int findLongestSubsequence(vector<int>& arr) {
- unordered_map<int, int> dp; // dp[x] 表示以 x 結尾的最長子序列長度
- unordered_set<int> numSet(arr.begin(), arr.end()); // 方便快速查找數字是否存在
- int maxLen = 0;
- // 遍歷所有數字，嘗試找出最大合法子序列
- for (int x : arr) {
- dp[x] = 1; // 最短長度至少為 1（只包含自己）
- for (int p = 0; p <= 29; p++) {
- int diff = 1 << p; // 2^p
- if (numSet.count(x - diff)) {
- dp[x] = max(dp[x], dp[x - diff] + 1);
- }
- }
- maxLen = max(maxLen, dp[x]);
- }
- return maxLen > 1 ? maxLen : 0; // 若 maxLen = 1，代表無法形成合法子序列
- }
- int main() {
- int n;
- cin >> n;
- vector<int> arr(n);
- for (int i = 0; i < n; i++) {
- cin >> arr[i];
- }
- cout << findLongestSubsequence(arr) << endl;
- return 0;
- }
用 unordered_map<int, int> 作為 DP 陣列
dp[x] 記錄以 x 為結尾的最大合法子序列長度。
遍歷 arr，對每個 x，檢查 x - 2^p 是否存在。
確保計算正確的子序列長度
只考慮 已出現過的數字，不會多算未來可能的子序列。
時間複雜度為 O(n log n)
O(n) 遍歷數列
O(log n) 嘗試不同的 2^p
--------------------------------------
測資:
測資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
這些測資涵蓋：
基本測試
無法形成子序列的情況
可以形成長子序列
所有數字相同的極端情況
較大數字的測試 |
