2017-8-3

題目描述

輸出長度為N的特殊質數，即前1至N項所表示的數均為質數

解答

用dfs求解即可

代碼

/* ID: 18795871 PROG: sprime LANG: C++ */ #include<iostream> #include<fstream> #include<cmath> using namespace std;ifstream fin("sprime.in"); ofstream fout("sprime.out");int cnt=1,N; long k=10;bool is_prime(long n){ //判斷n是否為質數if (n==0||n==1) return false;if (n==2||n==3) return true;long i;for (i=2;i<=sqrt(n);i++){if (n%i==0) return false;}return true; }void dfs(long n){if (!is_prime(n)||cnt>N) return ;if (cnt==N){fout<<n<<endl;return ;}for (int i=1;i<=9;i+=2){cnt++;n=n*k+i;dfs(n);n=(n-i)/k;cnt--;} }int main(){fin>>N;cnt=1;dfs(2);cnt=1;dfs(3);cnt=1;dfs(5);cnt=1;dfs(7); }

不難想出，直接枚舉出所有的情況，然后判斷是否是素數即可，然后呢？！超時了！于是我想著進行優化一下，那就是如果說第一位不是素數的話，就直接加m/10這么大，因為當最后到一位的時候，必須保證是素數；然后呢？還是超時！于是變成了前兩位必須是素數，還是超時！

/* ID: 18795871 PROG: sprime LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std;ifstream fin("sprime.in"); ofstream fout("sprime.out");typedef long long ll; const int N = 100; bool f[N+1]; int n; ll m;bool isprime(ll p){if (p<2) return false;for (ll i=2;i*i<=p;i++){if (p%i==0) return false;}return true; }bool res(ll p){ll q=p;while (q){if (!isprime(q)) return false; q/=10;}return true; }int main(){memset(f,true,sizeof(f));f[0]=f[1]=false;for (int i=2;i<=N;i++){if (f[i]){for (int j=2*i;j<=N;j+=i){f[j]=false;}}}while (fin>>n){m=1;while (n){m*=10;n--; }for (ll i=m/10;i<m;){if (!f[i*10/m]){if (m/10>0) i+=m/10;else i++;continue;}if (!f[i*100/m]){if (m/100>0) i+=m/100;else i++;continue;}if (res(i)) fout<<i<<endl;i++;}}return 0; }

上面是超時的代碼！

可能還是需要轉換一下思路：我們在進行深搜的時候，如果當前不滿足題意的話，可以立即return掉，不繼續往下了；那么在這里，我們從前往后走，如果說當前的值不滿足是素數的話，我們也沒有必要再繼續下去了！

/* ID: 18795871 PROG: sprime LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std;ifstream fin("sprime.in"); ofstream fout("sprime.out");typedef long long ll; const int N = 10; int n;bool isprime(ll p){if (p<2) return false;for (ll i=2;i*i<=p;i++){if (p%i==0) return false;}return true; }void dfs(int step,ll sum){if (!isprime(sum)) return ;if (step==n){fout<<sum<<endl;return ;}for (int i=1;i<N;i++){dfs(step+1,sum*10+i);} }int main(){while (fin>>n){dfs(1,2);dfs(1,3);dfs(1,5);dfs(1,7);}return 0; }

深搜剪枝的速度還是快啊！

總結

以上是生活随笔為你收集整理的USACO-Section1.6 Superprime Rib （枚举）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。