 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
字典树+详细的分类讨论+一堆剪枝=200行，写的我要吐了。。贴AC代码Source Code
Problem: 1165 User: yzhw
Memory: 804K Time: 47MS
Language: G++ Result: Accepted
Source Code
# include <iostream>
# include <cstring>
using namespace std;
class node
{
public:
node *next[10];
node()
{
for(int i=0;i<10;i++)
next[i]=NULL;
}
};
int total,first;
node *root;
void add(node *p,int num,int pos)
{
if(p->next[(num/pos)%10]==NULL)
p->next[(num/pos)%10]=new node();
if(pos==1) return;
else add(p->next[(num/pos)%10],num,pos/10);
}
void maketree()
{
bool tmp[100000];
root=new node();
memset(tmp,1,sizeof(tmp));
for(int i=2;i<=99999;i++)
{
if(tmp[i])
{
if(i>=10000&&i%10+(i/10)%10+(i/100)%10+(i/1000)%10+(i/10000)%10==total)
{
add(root,i,10000);
}
for(int j=2*i;j<=99999;j+=i)
tmp[j]=0;
}
}
}
int array[6][6];
void dfs(int pos)
{
if(pos==1)
{
for(int ii=first;ii<=first;ii++)
if(root->next[ii])
{
array[1][1]=ii;
node *p=root->next[ii];
for(int i=0;i<=9;i++)
if(p->next[i]&&root->next[i])
{
node *p1=p->next[i];
array[1][2]=i;
for(int j=0;j<=9;j++)
if(p1->next[j]&&root->next[j])
{
node *p2=p1->next[j];
array[1][3]=j;
for(int k=0;k<=9;k++)
if(p2->next[k]&&root->next[k])
{
array[1][4]=k;
node *p3=p2->next[k];
for(int l=0;l<=9;l++)
if(p3->next[l]&&root->next[l])
{
array[1][5]=l;
dfs(pos+1);
}
}
}
}
}
}
else if(pos==2)
{
node *p=root;
for(int j=1;j<pos;j++)
p=p->next[array[j][1]];
for(int i=0;i<10;i++)
if(p->next[i]&&root->next[i])
{
array[2][1]=i;
node *p1=root->next[array[1][1]],*p2=root->next[array[2][1]],*p3=root->next[array[1][2]];
for(int t1=0;t1<10;t1++)
if(p1->next[t1]&&p2->next[t1]&&p3->next[t1])
{
array[2][2]=t1;
node *p4=root->next[array[1][3]],*p5=p2->next[array[2][2]];
for(int t2=0;t2<10;t2++)
if(p4->next[t2]&&p5->next[t2])
{
array[2][3]=t2;
node *p6=p5->next[t2],*p7=root->next[array[1][4]];
for(int t3=0;t3<10;t3++)
if(p6->next[t3]&&p7->next[t3])
{
array[2][4]=t3;
node *p8=p6->next[t3],*p9=root->next[array[1][5]];
for(int t4=0;t4<10;t4++)
if(p8->next[t4]&&p9->next[t4])
{
array[2][5]=t4;
dfs(pos+1);
}
}
}
}
}
}
else if(pos==3)
{
node *p=root;
for(int j=1;j<pos;j++)
p=p->next[array[j][1]];
for(int i=0;i<10;i++)
if(p->next[i]&&root->next[i])
{
array[3][1]=i;
node *p1=root->next[array[3][1]],*p2=root->next[array[1][2]]->next[array[2][2]];
for(int t1=0;t1<10;t1++)
if(p1->next[t1]&&p2->next[t1])
{
array[3][2]=t1;
node *p3=root->next[array[1][1]]->next[array[2][2]],*p4=root->next[array[1][3]]->next[array[2][3]],*p5=p1->next[array[3][2]];
for(int t2=0;t2<10;t2++)
if(p4->next[t2]&&p5->next[t2]&&p3->next[t2])
{
array[3][3]=t2;
node *p6=p5->next[t2],*p7=root->next[array[1][4]]->next[array[2][4]];
for(int t3=0;t3<10;t3++)
if(p6->next[t3]&&p7->next[t3])
{
array[3][4]=t3;
node *p8=p6->next[t3],*p9=root->next[array[1][5]]->next[array[2][5]];
for(int t4=0;t4<10;t4++)
if(p8->next[t4]&&p9->next[t4])
{
array[3][5]=t4;
dfs(pos+1);
}
}
}
}
}
}
else if(pos==4)
{
node *p=root;
for(int j=1;j<pos;j++)
p=p->next[array[j][1]];
for(int i=0;i<10;i++)
if(p->next[i]&&root->next[i])
{
array[4][1]=i;
node *p1=root->next[array[4][1]],*p2=root->next[array[1][2]]->next[array[2][2]]->next[array[3][2]];
for(int t1=0;t1<10;t1++)
if(p1->next[t1]&&p2->next[t1])
{
array[4][2]=t1;
node *p4=root->next[array[1][3]]->next[array[2][3]]->next[array[3][3]],*p5=p1->next[t1];
for(int t2=0;t2<10;t2++)
if(p4->next[t2]&&p5->next[t2])
{
array[4][3]=t2;
node *p6=p5->next[t2],*p7=root->next[array[1][4]]->next[array[2][4]]->next[array[3][4]],*p3=root->next[array[1][1]]->next[array[2][2]]->next[array[3][3]];
for(int t3=0;t3<10;t3++)
if(p6->next[t3]&&p7->next[t3]&&p3->next[t3])
{
array[4][4]=t3;
node *p8=p6->next[t3],*p9=root->next[array[1][5]]->next[array[2][5]]->next[array[3][5]];
for(int t4=0;t4<10;t4++)
if(p8->next[t4]&&p9->next[t4])
{
array[4][5]=t4;
dfs(pos+1);
}
}
}
}
}
}
else if(pos==5)
{
node *p=root;
for(int j=1;j<pos;j++)
p=p->next[array[j][1]];
for(int i=0;i<10;i++)
if(p->next[i]&&root->next[i])
{
array[5][1]=i;
node *p1=root->next[array[5][1]],*p2=root->next[array[1][2]]->next[array[2][2]]->next[array[3][2]]->next[array[4][2]];
for(int t1=0;t1<10;t1++)
if(p1->next[t1]&&p2->next[t1])
{
array[5][2]=t1;
node *p4=root->next[array[1][3]]->next[array[2][3]]->next[array[3][3]]->next[array[4][3]],*p5=p1->next[t1];
for(int t2=0;t2<10;t2++)
if(p4->next[t2]&&p5->next[t2])
{
array[5][3]=t2;
node *p6=p5->next[t2],*p7=root->next[array[1][4]]->next[array[2][4]]->next[array[3][4]]->next[array[4][4]];
for(int t3=0;t3<10;t3++)
if(p6->next[t3]&&p7->next[t3])
{
array[5][4]=t3;
node *p8=p6->next[t3],*p9=root->next[array[1][5]]->next[array[2][5]]->next[array[3][5]]->next[array[4][5]],*p3=root->next[array[1][1]]->next[array[2][2]]->next[array[3][3]]->next[array[4][4]];
for(int t4=0;t4<10;t4++)
if(p8->next[t4]&&p9->next[t4]&&p3->next[t4])
{
array[5][5]=t4;
if(root->next[array[5][1]]&&root->next[array[5][1]]->next[array[4][2]]&&root->next[array[5][1]]->next[array[4][2]]->next[array[3][3]]&&root->next[array[5][1]]->next[array[4][2]]->next[array[3][3]]->next[array[2][4]]&&root->next[array[5][1]]->next[array[4][2]]->next[array[3][3]]->next[array[2][4]]->next[array[1][5]])
{
for(int o1=1;o1<=5;o1++)
{
for(int o2=1;o2<=5;o2++)
cout<<array[o1][o2];
cout<<endl;
}
cout<<endl;
}
}
}
}
}
}
}
}
int main()
{
cin>>total>>first;
maketree();
dfs(1);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
