d396 - 00524 - Prime Ring Problem
題目描述
題目要求找出一個由 1 到 n 的整數組成的環，其中 n 為偶數，且環中相鄰兩個數字的和必須是質數。環的第一個數字固定為 1，並要求按照字典順序輸出所有可能的環。
解題思路
這題使用 backtracking (回溯法) 解決。首先預處理出小於等於 n+n 的質數，並用一個布林陣列 prime 標記。然後，從 1 開始，遞迴地嘗試將 2 到 n 的數字填入環中的剩餘位置。在每次填入數字之前，檢查它與前一個數字的和是否為質數，以及該數字是否已被使用。如果滿足條件，則將該數字填入環中，並遞迴地填入下一個位置。如果所有位置都已填滿，則輸出該環。回溯時，將該數字標記為未使用，以便嘗試其他可能的組合。
複雜度分析
- 時間複雜度: O(n!)，因為最壞情況下需要嘗試所有可能的排列組合。
- 空間複雜度: O(n)，主要用於儲存環中的數字
a和used陣列。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
char p,ca,a[18]={1},prime[34],used[18]={1,1};
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x<10)
putchar_unlocked(x+'0');
else{
putchar_unlocked(x/10+'0');
putchar_unlocked(x-10+'0');
}
}
inline void bfs(int it){
if(it==p){
if(prime[a[p-1]+1])return;
for(int i=0;i<p;++i){
write(a[i]);
putchar_unlocked(' ');
}
putchar_unlocked('\n');
return;
}
for(int i=2;i<=p;++i){
if(!used[i]&&!prime[i+a[it-1]]){
a[it]=i;
used[i]=1;
bfs(it+1);
used[i]=0;
}
}
}
int main(){
for(int i=2;i<=6;++i)
for(int j=i+i;j<34;j+=i)
prime[j]=1;
while(p=read()){
putchar_unlocked('C');
putchar_unlocked('a');
putchar_unlocked('s');
putchar_unlocked('e');
putchar_unlocked(' ');
write(++ca);
putchar_unlocked(':');
putchar_unlocked('\n');
for(int i=2;i<=p;++i){
used[i]=0;
a[i]=0;
}
bfs(1);
putchar_unlocked('\n');
}
}