標題:
2022 D-亞馬遜寶藏
[打印本頁]
作者:
may
時間:
2025-3-26 12:14
標題:
2022 D-亞馬遜寶藏
D-亞馬遜寶藏
時間限制 5 秒 / 記憶體限制 2 G
傳說中亞馬遜的地下存在有大量寶藏，雖然我不是探險家但這聽起來很棒對吧？但要獲取這個寶藏前
要先解出一道謎題，必須要從整數序列中找出最長的子序列，此子序列必須滿足以下條件
[attach]20827[/attach]
1. 序列中任意兩個元素相減的絕對值必須為整數 的任一次方數，也就是 ，例如
，則 。
經過前面探險家的努力，他們已經發現這是個崇拜數字 的民族2ㄏ2ㄏ族所埋下的寶藏，因此這個整
數 一定是正整數 ，
你的任務是找出符合條件的最長子序列並輸出其長度即可。
● 輸入說明
第⼀⾏為一個正整數 ，代表整數序列的長度。
第二行有 個整數 ，代表整數序列中的每個元素，且中間用空白隔開。
, ( )
, ( ， )
● 輸出說明
輸出題目要求中最長子序列的長度，若不存在則輸出 。
範例輸入1
6
1 2 5 3 8 10
範例輸出1
3
範例輸入2
5
-1 2 5 11 14
範例輸出2
0
作者:
may
時間:
2025-3-27 12:27
回復
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
這些測資涵蓋：
基本測試
無法形成子序列的情況
可以形成長子序列
所有數字相同的極端情況
較大數字的測試
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
