HUST team contest #2 A An Industrial Spy ||poj 3842 (筛)
蠢了。
这道题显然可以搜。。
然后自己搜索的姿势果然还是不怎么地。。
最后是蔡大神过掉的。
他的思路是枚举素数，然后把素数的各位拆开，看这些数字是否在给出的字符串中出现过。
一开始TLE掉了。
后来又预处理出来一个标记数组，如果字符串中没有数字2，那么20w+的素数就可以直接跳过去，然后A掉了。
其实因为数字的位数最多才7位。。
暴力也不是不可以。。。。
STL中求全排列的那个函数我也不是没用过。。。比赛的时候怎么就没想到==
再开个map判重
然后素数打表部分。
队友是打了个30000+行的表。。。。
说起来。。。我好像还没用C++写过筛法求素数。。。
说来惭愧啊。。。。
pascal的时候倒是写过几次呢。
再复习下。。。
http://blog.csdn.net/dinosoft/article/details/5829550
写的是快速筛。
/*************************************************************************
> File Name: code/2015summer/0821/A.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月20日 星期四 22时17分14秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E7+7;
25using namespace std;
1bool not_prime[N];
2int prime[N],pri_num;
3map<int,bool> mp;
4int a[N];
5int ans;
6map<int,bool>::iterator it;
7char st[15];
8int len;
9void init()
10{
not_prime[0] =true;
not_prime[1] = true;
1 for(int i = 2;i < N; ++i)
2 {
3 if(!not_prime[i])
4 prime[++pri_num] = i;
5 for(int j = 1;j <= pri_num && i * prime[j] < N; j++)
6 {
1 not_prime[i * prime[j]] = true;
2 if(i % prime[j] == 0) break;
3 }
4 }
5}
void solve()
{
1 int res = 0;
2 for(int i = 1;i <= len; ++i)
3 {
1 res = res * 10 + a[i];
2// cout<<"res:"<<res<<endl;
3 if(!not_prime[res] && !mp[res])
4 {
5 mp[res] = true;
6 ans++;
7 }
8 }
9}
1int main()
2{
3 init();
4// for ( int i =2 ; i <= 1000 ; i++)
5// {
6// if (!not_prime[i])
7// {
8// cout<<i<<endl;
9// }
10// }
11 int T;
12 cin>>T;
13 while (T--)
14 {
1 ans = 0 ;
2 mp.clear();
3 scanf("%s",st+1);
4 len = strlen(st + 1);
5 for(int i = 1;i <= len; i++)
6 {
7 a[i] = st[i] - '0';
8 }
9 sort(a+1,a+len+1);
10 do
11 {
12 solve();
13 }while (next_permutation(a+1,a+len+1));
1 printf("%d\n",ans);
2 }
3 return 0;
4}
/*************************************************************************
> File Name: code/2015summer/0821/A.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月20日 星期四 22时17分14秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N=1E7+7;
25using namespace std;
1bool not_prime[N];
2int prime[N],pri_num;
3map<int,bool> mp;
4int a[N];
5int ans;
6map<int,bool>::iterator it;
7char st[15];
8int len;
9void init()
10{
not_prime[0] =true;
not_prime[1] = true;
1 for(int i = 2;i < N; ++i)
2 {
3 if(!not_prime[i])
4 prime[++pri_num] = i;
5 for(int j = 1;j <= pri_num && i * prime[j] < N; j++)
6 {
1 not_prime[i * prime[j]] = true;
2 if(i % prime[j] == 0) break;
3 }
4 }
5}
void solve()
{
1 int res = 0;
2 for(int i = 1;i <= len; ++i)
3 {
1 res = res * 10 + a[i];
2// cout<<"res:"<<res<<endl;
3 if(!not_prime[res] && !mp[res])
4 {
5 mp[res] = true;
6 ans++;
7 }
8 }
9}
1int main()
2{
3 init();
4// for ( int i =2 ; i <= 1000 ; i++)
5// {
6// if (!not_prime[i])
7// {
8// cout<<i<<endl;
9// }
10// }
11 int T;
12 cin>>T;
13 while (T--)
14 {
1 ans = 0 ;
2 mp.clear();
3 scanf("%s",st+1);
4 len = strlen(st + 1);
5 for(int i = 1;i <= len; i++)
6 {
7 a[i] = st[i] - '0';
8 }
9 sort(a+1,a+len+1);
10 do
11 {
12 solve();
13 }while (next_permutation(a+1,a+len+1));
1 printf("%d\n",ans);
2 }
3 return 0;
4}
v