首页 > 代码库 > hdu 4951

hdu 4951

2024-07-17 18:39:27   215人阅读

Multiplication table

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 435    Accepted Submission(s): 204

Problem Description
   Teacher Mai has a multiplication table in base p.
   For example, the following is a multiplication table in base 4:
*  0  1  2  3 0 00 00 00 00 1 00 01 02 03 2 00 02 10 12 3 00 03 12 21
   But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table.
   For example Teacher Mai only can see:
1*1=11 1*3=11 1*2=11 1*0=11 3*1=11 3*3=13 3*2=12 3*0=10 2*1=11 2*3=12 2*2=31 2*0=32 0*1=11 0*3=10 0*2=32 0*0=23
   Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into.
   It‘s guaranteed the solution is unique.
 
Input
   There are multiple test cases, terminated by a line "0".
   For each test case, the first line contains one integer p(2<=p<=500).
   In following p lines, each line contains 2*p integers.The (2*j+1)-th number x and (2*j+2)-th number y in the i-th line indicates equation i*j=xy in the shuffled multiplication table.
Warning: Large IO!
 
Output
   For each case, output one line.
   First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.
 
Sample Input
42 3 1 1 3 2 1 01 1 1 1 1 1 1 13 2 1 1 3 1 1 21 0 1 1 1 2 1 30
 
Sample Output
Case #1: 1 3 2 0
 
Source
2014 Multi-University Training Contest 8
 
Recommend
hujie   |   We have carefully selected several similar problems for you:  4955 4954 4953 4952 4950 
 
分析：大水题，，，要敢于分析。。。
详见题解：http://blog.sina.com.cn/u/1809706204

 

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 100511 #define M 1512 #define mod 100000000713 #define mod2 10000000014 #define ll long long15 #define maxi(a,b) (a)>(b)? (a) : (b)16 #define mini(a,b) (a)<(b)? (a) : (b)17 18 using namespace std;19 20 int cnt;21 int p;22 int i,j;23 int a[N][N];24 int c[N][N];25 int cc[N];26 int ans[N];27 28 int main()29 {30     //ini();31     //freopen("data.in","r",stdin);32     //scanf("%d",&T);33     //for(int cnt=1;cnt<=T;cnt++)34     //while(T--)35     cnt=1;36     while(scanf("%d",&p)!=EOF)37     {38         if(p==0) break;39         printf("Case #%d:",cnt);cnt++;40         memset(c,0,sizeof(c));41         memset(cc,0,sizeof(cc));42        for(i=0;i<p;i++)43        {44            for(j=1;j<=p;j++){45                 scanf("%d",&a[i][2*j-1]);46                 cc[ a[i][2*j-1] ]++;47                 scanf("%d",&a[i][2*j]);48                 cc[ a[i][2*j] ]++;49            }50        }51 52        int ma=cc[0];53        int index=0;54        for(i=0;i<p;i++){55             if(cc[i]>ma){56                 ma=cc[i];index=i;57             }58        }59        ans[0]=index;60 61        memset(cc,0,sizeof(cc));62 63        for(i=0;i<p;i++)64        {65            for(j=1;j<=p;j++){66                 if(c[i][ a[i][2*j-1] ]==0){67                     c[i][ a[i][2*j-1] ]=1;68                     cc[i]++;69                 }70            }71            if(cc[i]==1){72                 if(ans[0]!=i) ans[1]=i;73            }74            else{75                 ans[ cc[i] ]=i;76            }77        }78 79        for(i=0;i<p;i++) printf(" %d",ans[i]);80        printf("\n");81     }82 83 84 85     return 0;86 }

 


联系
我们