做了一天. AC的速度还可以, 时间最长的 0.16s.
1. 开始做之前，要确定下搜索顺序, 这个很关键.
参考
http://starforever.blog.hexun.com/2319991_d.html2. 首先用筛法求出10000 - 99999的所有素数，然后对素数进行分类： 5位数中, 分成第一位是固定的； 第三位是固定的；第一和五位是固定的；第一、二、四位是固定的。注意搜索顺序3、6中，不能有0出现（题意要求）。这样减少枚举的次数。
3. 然后就7层DFS，
4. 最后对搜索结果进行排序，我用的是插入排序。
/**//*
ID: lorelei3
TASK: prime3
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cmath>
#include <memory.h>
using namespace std;
const int MAX = 99999;
const int DIV[6] = 
{0,10000, 1000, 100, 10, 1};
bool primes[MAX];
int n, sum;
int prime1[10][1000][6];
int nprime1[10];
int prime3[10][1000][6];
int nprime3[10];
int prime15[10][10][100][6];
int nprime15[10][10];
int prime124[10][10][10][100][6];
int nprime124[10][10][10];
void dfs1();
void dfs2();
void dfs3();
void dfs4();
void dfs5();
void dfs6();
void dfs7();
ifstream fin("prime3.in");
ofstream fout("prime3.out");
void addPrime(int s){
int i, k=1, tmp[6];
int num = s;
while(num!=0){
tmp[k] = num/DIV[k];
num = num%DIV[k];
k++;
}
int c =0;
for(i=1; i<=5; ++i)
c += tmp[i];
if(c == sum){
primes[s]=true;
for(i=1; i<=5; ++i){
int t = nprime1[tmp[1]];
prime1[tmp[1]][t][i] = tmp[i];
}
nprime1[tmp[1]]++;
for(i=1; i<=5; ++i){
int t = nprime3[tmp[3]];
prime3[tmp[3]][t][i] = tmp[i];
}
nprime3[tmp[3]]++;
bool flag=true;
for(i=1; i<=5; ++i){
if(tmp[i]==0){
flag=false;
break;
}
int t = nprime15[tmp[1]][tmp[5]];
prime15[tmp[1]][tmp[5]][t][i] = tmp[i];
}
if(flag)
nprime15[tmp[1]][tmp[5]]++;
for(i=1; i<=5; ++i){
int t = nprime124[tmp[1]][tmp[2]][tmp[4]];
prime124[tmp[1]][tmp[2]][tmp[4]][t][i] = tmp[i];
}
nprime124[tmp[1]][tmp[2]][tmp[4]]++;
}
}
int map[6][6];
int ans[1000][6][6];
int cnt=0;
bool inline larger_than(int a[6][6], int b[6][6]){
for(int i=1; i<=5; ++i)
for(int j=1; j<=5; ++j)
if(a[i][j]>b[i][j])
return true;
else if(a[i][j]<b[i][j])
return false;
else
continue;
return false;
}
void addResult(){
int p = ++cnt;
while(p!=0 && larger_than(ans[p-1], map)){
memcpy(ans[p], ans[p-1], sizeof(int)*36);
p--;
}
memcpy(ans[p], map, sizeof(int)*36);
}
int isPrime(int a){
int n = static_cast<int>(sqrt(a));
for(int i=2; i<=n; ++i)
if(!(a%i))
return 0;
return 1;
}
int d=0;
void initPrime(){
for(int i=10001; i<=99999; ++i)
if(isPrime(i))
addPrime(i);
}
bool check1(int r){
int i,sum=0;
for(i=1; i<=5; ++i)
sum = sum*10+map[r][i];
if(!primes[sum]) return false;
return true;
}
bool check2(int c){
int i,sum=0;
for(i=1; i<=5; ++i)
sum = sum*10+map[i][c];
if(!primes[sum]) return false;
return true;
}
void dfs1(){
int t = nprime1[map[1][1]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=2; j<=5; ++j)
map[j][j] = prime1[map[1][1]][i][j];
dfs2();
}
}
void dfs2(){
int t = nprime3[map[3][3]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=1; j<=5; ++j)
map[6-j][j] = prime3[map[3][3]][i][j];
dfs3();
}
}
void dfs3(){
int t = nprime15[map[1][1]][map[1][5]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=2; j<=4; ++j)
map[1][j] = prime15[map[1][1]][map[1][5]][i][j];
dfs4();
}
}
void dfs4(){
int t = nprime124[map[1][2]][map[2][2]][map[4][2]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=3; j<=5; ++j)
map[j][2] = prime124[map[1][2]][map[2][2]][map[4][2]][i][j];
dfs5();
}
}
void dfs5(){
int t = nprime124[map[1][4]][map[2][4]][map[4][4]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=3; j<=5; ++j)
map[j][4] = prime124[map[1][4]][map[2][4]][map[4][4]][i][j];
for(int k=1; k<=9; k+=2){
map[5][3]=k;
if(check1(5))
dfs6();
}
}
}
void dfs6(){
int t = nprime15[map[1][1]][map[5][1]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=2; j<=4; ++j)
map[j][1] = prime15[map[1][1]][map[5][1]][i][j];
for(int k=1; k<=9; k+=2){
map[3][5] = k;
if(check1(3))
dfs7();
}
}
}
void dfs7(){
int t = nprime124[map[2][1]][map[2][2]][map[2][4]];
if(t==0)
return;
else
for(int i=0; i<t; ++i){
for(int j=3; j<=5; ++j)
map[2][j] = prime124[map[2][1]][map[2][2]][map[2][4]][i][j];
for(int a=0; a<=9; ++a){
map[4][3]=a;
if(check2(3))
for(int b=1; b<=9; b+=2){
map[4][5] = b;
if(check1(4) && check2(5) )
addResult();
}
}
}
}
void output(){
for(int k=0; k<cnt-1; ++k){
for(int i=1; i<=5; ++i){
for(int j=1; j<=5; ++j)
fout<<ans[k][i][j];
fout<<endl;
}
if(cnt==1)
return;
fout<<endl;
}
for(int i=1; i<=5; ++i){
for(int j=1; j<=5; ++j)
fout<<ans[cnt-1][i][j];
fout<<endl;
}
}
int main(){
//input
fin>>sum>>map[1][1];
//init
for(int i=1; i<=5; ++i)
for(int j=1; j<=5; ++j)
ans[0][i][j] = 9;
initPrime();
//solve
dfs1();
//output
output();
return 0;
}posted on 2011-01-29 00:07
小阮 阅读(692)
评论(0) 编辑 收藏 引用 所属分类:
USACO