首页 > 代码库 > hdu 4951 乘法表
hdu 4951 乘法表
http://acm.hdu.edu.cn/showproblem.php?pid=4951
依照我原先的想法是 先找出ans[0] 和ans[1]来，这个好找吧，要是有一行全部是相等的数组成那这行的序号就是ans[0], 要是有一[i,j]，i*j=ans[0] i ,那么ans[j]=1, 找到了ans[0]和ans[1] ，然后根据已知的遍历推算出其他的结果。
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 8 struct node 9 { 10 int x,y,zhi; 11 } p[505][505]; 12 13 bool vis[505]; 14 int ans[505]; 15 16 int get(int x,int y,int c) 17 { 18 int w[505],num=0; 19 do 20 { 21 w[num++]=y%10; 22 y/=10; 23 } 24 while(y); 25 26 do 27 { 28 w[num++]=x%10; 29 x/=10; 30 } 31 while(x); 32 33 int sum=0; 34 for(int i=0,jie=1; i<num; i++) 35 { 36 sum+=w[i]*jie; 37 jie*=c; 38 } 39 return sum; 40 } 41 42 void solve(int n) 43 { 44 int count1=2,coun=1; 45 while(1) 46 { 47 for(int i=0; i<n; i++) 48 for(int j=0; j<n; j++) 49 { 50 51 if(vis[p[i][j].x]&&vis[p[i][j].y]) 52 { 53 if(p[i][j].zhi==-1) 54 p[i][j].zhi=get(ans[p[i][j].x],ans[p[i][j].y],n); 55 if(p[i][j].zhi!=0) 56 { 57 if(vis[i]&&!vis[j]) 58 { 59 ans[j]=p[i][j].zhi/ans[i]; 60 vis[j]=true; 61 count1++; 62 } 63 else if(!vis[i]&&vis[j]) 64 { 65 66 ans[i]=p[i][j].zhi/ans[j]; 67 vis[i]=true; 68 count1++; 69 } 70 else if(!vis[i]&&i==j) 71 { 72 73 ans[i]=p[i][j].zhi/2; 74 vis[i]=true; 75 count1++; 76 } 77 if(count1>=n) 78 return ; 79 } 80 } 81 } 82 } 83 } 84 85 int main() 86 { 87 int n,i,j,a,b,c; 88 for(int i=0;i<55;i++) 89 { 90 scanf("%d%d%d",&a,&b,&c); 91 printf("get %d\n",get(a,b,c)); 92 } 93 94 while(~scanf("%d",&n),n) 95 { 96 memset(vis,false,sizeof(vis)); 97 for( i=0; i<n; i++) 98 for( j=0; j<n; j++) 99 {100 scanf("%d%d",&p[i][j].x,&p[i][j].y);101 p[i][j].zhi=-1;102 }103 for( i=0; i<n; i++)104 {105 for( j=0; j<n; j++)106 if(p[i][j].x!=p[i][j].y)107 break;108 if(j==n)109 {110 ans[p[i][0].x]=0;111 vis[p[i][0].x]=true;112 break;113 }114 }115 116 for( i=0; i<n; i++)117 {118 for( j=0; j<n; j++)119 if(!vis[i]&&!vis[j]&&ans[p[i][j].x]==0&&i*j==p[i][j].y)120 {121 if(i==p[i][j].y)122 {123 ans[j]=1;124 vis[j]=true;125 }126 else127 {128 ans[i]=1;129 vis[i]=true;130 }131 break;132 }133 if(j!=n)134 break;135 }136 137 solve(n);138 for( i=0; i<n; i++)139 printf("%d ",ans[i]);140 printf("\n");141 142 }143 return 0;144 }
上面的结果当然是错的， 起码每次找p[i][j].zhi 的时候就必须得用大数 = =
在网上看到一个很简洁的思路 膜拜一下~
http://www.cnblogs.com/yuiffy/p/3914595.html
1 #include <stdio.h> 2 #include<iostream> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 int a[505][1005],ans[505]; 7 bool vis[505]; 8 9 int main()10 {11 int i,j,n,cas=1;12 while(~scanf("%d",&n),n)13 {14 for(i=0;i<n;i++)15 for( j=0;j<2*n;j+=2)16 scanf("%d%d",&a[i][j],&a[i][j+1]);17 for(i=0;i<n;i++)18 {19 for(j=0;j<2*n;j+=2)20 if(a[i][j]!=a[i][j+1])21 break;22 if(j>=2*n)23 {24 ans[0]=i;25 26 break;27 }28 }29 for(i=0;i<n;i++)30 {31 if(i==ans[0])32 continue;33 memset(vis,false,sizeof(vis));34 int num=0;35 for(j=0;j<2*n;j+=2)36 {37 if(vis[a[i][j]]==false)38 {39 vis[a[i][j]]=true;40 num++;41 }42 }43 ans[num]=i;44 }45 printf("Case #%d: %d",cas++,ans[0]);46 for(int i=1;i<n;i++)47 printf(" %d",ans[i]);48 printf("\n");49 }50 return 0;51 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。