http://acm.hdu.edu.cn/showproblem.php?pid=4951
2014多校 第八题 1008
2014 Multi-University Training Contest 8
Multiplication tableTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 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 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 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. 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 Sample Output
Case #1: 1 3 2 0
Source
Recommend
|
大意：给出一个p进制数的乘法表，第i行第j组（一组有两个数）表示i*j结果的高位和低位，例如样例中：
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”表示0*0的结果为23，后面的“1 1”表示0*1的结果为11，依此类推。 这个乘法表不正确，是因为有熊孩子把数字打乱了，样例中，0被换成了1, 1被换成了3, 2被换成了2, 3被换成了0，第一行的0*0等于23其实是3*3=21（四进制）。
求各个数的映射。 题解：探寻乘法表的规律。
数字太大，不能暴搜，而且乘法表是有规律的，我们可以根据数字出现的种类数来判断数字。
样例中有一行全是1，我们可以想到1其实就是0,。
最后一行的高位全是1，我们根据10进制的乘法表来观察，什么时候高位会不变呢？只有0*x和1*x高位是不变的，2*x的时候高位就有0或者1了。所以这个高位全是1的行代表的数字是1。
然后探寻普遍的规律：高位出现了多少种数字，这一位就是多少。（0、1高位都只出现1位数字，需特殊判断两个低位是否相等，相等说明是0，不等是1） （这题有点碉，我是没想到这么好的判断方法，当时暴搜了起来，果然不得力） 代码（一秒多过，加了读入输出优化的话可以到三百多毫秒）：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usint unsigned int
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair int a[][][];
int c[];
int d[];
int p; void farm() {
int i,j;
memset(c,-,sizeof(c)); for(i=; i<p; i++) {
memset(d,,sizeof(d));
int cnt=;
for(j=; j<p; j++)
if(d[ a[i][j][] ]==) {
d[ a[i][j][] ]=;
cnt++;
}
if(cnt==) cnt= a[i][][]==a[i][][]?:;
//b[i]=cnt;
c[cnt]=i;
} for(i=; i<p; i++) {
printf(" %d",c[i]);
}
puts("");
} int main() {
int cas=, ans;
int i,j;
while(scanf("%d",&p)!=EOF) {
if(p==)break;
for(i=; i<p; i++) {
for(j=; j<p; j++) {
//scanf("%d%d",&a[i][j][1],&a[i][j][0]);
scanf("%d%d",&a[i][j][],&a[i][j][]);
}
}
printf("Case #%d:",cas++);
farm();
}
return ;
}