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.
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!
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.
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
4
2 3 1 1 3 2 1 0
1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2
1 0 1 1 1 2 1 3
0
2 3 1 1 3 2 1 0
1 1 1 1 1 1 1 1
3 2 1 1 3 1 1 2
1 0 1 1 1 2 1 3
0
Sample Output
Case #1: 1 3 2 0
Source
Recommend
分析：大水题，，，要敢于分析。。。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map> #define N 1005
#define M 15
#define mod 1000000007
#define mod2 100000000
#define ll long long
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int cnt;
int p;
int i,j;
int a[N][N];
int c[N][N];
int cc[N];
int ans[N]; int main()
{
//ini();
//freopen("data.in","r",stdin);
//scanf("%d",&T);
//for(int cnt=1;cnt<=T;cnt++)
//while(T--)
cnt=;
while(scanf("%d",&p)!=EOF)
{
if(p==) break;
printf("Case #%d:",cnt);cnt++;
memset(c,,sizeof(c));
memset(cc,,sizeof(cc));
for(i=;i<p;i++)
{
for(j=;j<=p;j++){
scanf("%d",&a[i][*j-]);
cc[ a[i][*j-] ]++;
scanf("%d",&a[i][*j]);
cc[ a[i][*j] ]++;
}
} int ma=cc[];
int index=;
for(i=;i<p;i++){
if(cc[i]>ma){
ma=cc[i];index=i;
}
}
ans[]=index; memset(cc,,sizeof(cc)); for(i=;i<p;i++)
{
for(j=;j<=p;j++){
if(c[i][ a[i][*j-] ]==){
c[i][ a[i][*j-] ]=;
cc[i]++;
}
}
if(cc[i]==){
if(ans[]!=i) ans[]=i;
}
else{
ans[ cc[i] ]=i;
}
} for(i=;i<p;i++) printf(" %d",ans[i]);
printf("\n");
} return ;
}