d357 - NOIP2002 2.选数
題目描述
題目要求從給定的 n 個整數中選取 k 個整數，計算所有可能的組合和，並統計其中為質數的組合數量。
解題思路
本題採用深度優先搜尋 (DFS) 搭配回溯法來產生所有可能的 k 個整數組合。對於每個組合，計算其和，然後判斷該和是否為質數。使用一個 map 來儲存已經計算過的組合和及其是否為質數的結果，避免重複計算。isPrime 函數用於判斷一個數字是否為質數。used 陣列用於追蹤哪些數字已經被選入當前組合，以避免重複使用。
複雜度分析
- 時間複雜度: O(C(n, k) * sqrt(max_sum))，其中 C(n, k) 是從 n 個元素中選取 k 個元素的組合數，max_sum 是所有組合和的最大值。sqrt(max_sum) 是
isPrime函數的複雜度。 - 空間複雜度: O(C(n, k))，主要用於儲存 map 中已經計算過的組合和。
程式碼
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
long long a[25],n,m,ans;
map <long long,bool> mp;
bool used[25];
bool isPrime(long long x){
if(x%2==0)return 0;
for(long long y=3;y<=sqrt(x);y+=2)
if(x%y==0)return 0;
return 1;
}
void dfs(int it,long long v,int k){
if(k==m){
if(mp.find(v)!=mp.end()){
ans+=mp[v];
}
else{
if(isPrime(v)){
mp[v]=1;
++ans;
}
else{
mp[v]=0;
}
}
return;
}
for(int i=it;i<n;++i){
if(used[i]==0){
used[i]=1;
dfs(i+1,v+a[i],k+1);
used[i]=0;
}
}
return;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a[i];
}
dfs(0,0,0);
cout << ans;
}