f502 - 10036 - Divisibility
題目描述
題目給定一個整數序列，要求判斷是否能通過在數字之間插入加號或減號，使得最終的結果可以被 K 整除。
解題思路
這題的核心思想是利用動態規劃來追蹤所有可能的餘數。我們維護一個陣列 a，其中 a[i] 表示是否存在一種組合，使得其對 K 的餘數為 i。初始時，a[0] = 1，表示初始狀態的餘數為 0。對於每個數字，我們計算其絕對值對 K 的餘數 t。然後，我們更新 a 陣列，對於每個已知的餘數 j，我們計算 (j + t) % k 和 abs(j - t) % k，並將對應的 a 值設為 1。最終，我們檢查 a[0] 是否為 1，如果是，則表示存在一種組合可以被 K 整除，輸出 "Divisible"，否則輸出 "Not divisible"。
複雜度分析
- 時間複雜度: O(N * K)，其中 N 是數字序列的長度，K 是除數。因為對於每個數字，我們需要遍歷
a陣列，其大小為 K。 - 空間複雜度: O(K)，因為我們需要一個大小為 K 的
a陣列來儲存餘數信息。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,k,ca;
cin >> ca;
while(ca--){
cin >> n >> k;
int a[201]={0},t,s=0;
for(int i=0;i<n;++i){
cin >> t;
t=abs(t)%k;
if(i==0)
a[t]=1;
else{
int t2[201]={0};
for(int j=0;j<=200;++j)
if(a[j]){
t2[(j+t)%k]=1;
t2[abs(j-t)%k]=1;
}
for(int j=0;j<=200;++j)
a[j]=t2[j];
}
}
for(int i=0;i<=200;i+=k)
if(a[i]){
s=1;
break;
}
if(s)
cout << "Divisible\n";
else
cout << "Not divisible\n";
}
}