f711 - 12218 - An Industrial Spy
題目描述
題目給定一個包含若干數字的字串，要求找出可以由這些數字組成多少個不同的質數。可以重複使用數字，但數字的順序不同，組成的質數也不同。
解題思路
這題的核心是使用深度優先搜尋 (DFS) 產生所有可能的數字組合，然後檢查每個組合是否為質數。
- 質數篩選: 首先使用埃拉托斯特尼篩法預先計算出一定範圍內的質數，以便快速判斷。
- DFS 產生組合: 使用 DFS 遞迴地將輸入字串中的每個數字添加到當前組合中，直到組合形成一個完整的數字。
- 判斷質數: 對於每個生成的數字，檢查它是否在預先計算的質數列表中。
- 去重: 使用
map記錄已經生成的數字，避免重複計算。 - 處理前導零: 題目要求忽略前導零，因此在判斷質數之前，需要處理前導零的情況。
複雜度分析
- 時間複雜度: O(N * 10^L)，其中 N 是輸入字串的長度，L 是輸入字串的最大長度。 DFS 的時間複雜度與可能的組合數量有關，而每個組合的生成和質數判斷都需要一定的時間。
- 空間複雜度: O(10^L)，主要用於儲存質數篩選表和
map，其中map用於儲存已經生成的數字，避免重複計算。
程式碼
#include <iostream>
#include <map>
using namespace std;
map <string,int> ac;
map <int,int> bc;
int n,ans,al;
bool used[10],p[10000001]={1,1};
string a;
inline void dfs(string v){
if(ac[v])return;
ac[v]=1;
int tmp=0;
for(int i=0;i<v.length();++i){
tmp*=10;
tmp+=v[i]-'0';
}
if(p[tmp]==0&&bc[tmp]!=1)
++ans;
bc[tmp]=1;
for(int i=0;i<al;++i){
if(used[i]==0){
string tmp=v;
tmp+=a[i];
used[i]=1;
dfs(tmp);
used[i]=0;
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=3163;++i){
for(int j=i+i;j<10000001;j+=i){
p[j]=1;
}
}
cin >> n;
while(n--){
cin >> a;
ans=0;
ac.clear();
bc.clear();
al=a.length();
for(int i=0;i<al;++i){
string tmp;
tmp+=a[i];
used[i]=1;
dfs(tmp);
used[i]=0;
}
cout << ans << "\n";
}
}