題目鏈接：http://poj.org/PRoblem?id=3842
題意： 給你至多7個數字，問這些數字最多能組成多少個質數。
題解： gym里的題目都挺好的（個別除外），這道題即是。 首先我們不妨預處理一個prime[]數組，prime[i]反映第i個數是否為質數。 然后對這些數字排序……排序完了以后枚舉排列…… 然后就過了…… 代碼：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int size = 10000000;typedef long long LL;bool pm[size];void update() { for ( int i = 0; i < size; i ++ ) pm[i] = 1; pm[0] = pm[1] = 0; for ( LL i = 2; i < size; i ++ ) { if(pm[i] == 1) { for( LL j = i*i; j < size; j += i) pm[j] = false; } }}bool vis[size];char str[15];int ntr[15], re[size];int main() { update(); memset(vis, 0, sizeof(vis)); int tst; scanf("%d", &tst); while( tst -- ) { scanf("%s", str); int len = strlen(str); for ( int i = 0; i < len; i ++ ) ntr[i] = str[i]-'0'; int ans = 0, curs = 0; sort(ntr, ntr+len); do { int sum = 0; for ( int i = 0; i < len; i ++ ) { sum = sum*10+ntr[i]; if(vis[sum] == 0 && pm[sum] == 1) { ans ++; vis[sum] = -1; re[curs ++] = sum; } } } while(next_permutation(ntr, ntr+len)); printf("%d/n", ans); for ( int i = 0; i < curs; i ++ ) vis[re[i]] = 0; } return 0;}新聞熱點
疑難解答
