Codeforces 100726A 或 POJ 3842

2019-11-10 20:18:29

字体：大中小

来源：转载

供稿：网友

题目链接：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;}

上一篇：二叉树

下一篇：leecode 解题总结：31. Next Permutation