HDU 4951 Multiplication table 阅读题

链接:http://acm.hdu.edu.cn/showproblem.php?pid=4951

题意:给一个P进制的乘法表。行和列分别代表0~p-1,第i行第j*2+1和第j*2+2列代表的是第i行的数x和第j列的数的乘积。只是这个乘法表被人弄乱了,原来的0~p-1被映射到了一个新的0~p-1的permutation(曾经在CF上看见的permutation表示1~P。所以稍有迷茫),分别代表了新的不同的数。乘法表上的数也都被映射了。如今要找出映射到了什么新的数。

思路:毫无疑问。出现最多的数一定原来是0,而(p-1)*(p-1) = p^2-2*p+1 = p*(p-2)+1,而且仅仅有(p-1)*(p-1)时,”十位“会出现p-2。其它相乘的”十位“数字最大也仅仅是p-3,所以相应着行列都是p-1的数的位置,”十位“代表的一定是p-2,然后递推着找(p-1)*(p-2)的"十位"是N-3,向下找就能找到全部数字的映射了。

(2进制须要特判,由于p-2=0)

代码:(C++过的)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-10
#define INF 0x7fffffff
#define maxn 10005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int a[505][1005];
int tt[505][2];
int main()
{
int T,t=0;
int M[505];
while(scanf("%d",&T))
{
t++;
if(T==0)
break;
memset(M,-1,sizeof(M));
memset(tt,0,sizeof(tt));
for(int i=0; i<T; i++)
for(int j=0; j<T; j++)
{
scanf("%d%d",&a[i][j*2+1],&a[i][j*2+2]);
tt[a[i][j*2+1]][0]++;
tt[a[i][j*2+2]][1]++;
}
printf("Case #%d:",t);
if(T==2)
{
if(tt[0][0]>tt[1][0])
printf(" 0 1\n");
else printf(" 1 0\n");
continue;
}
int all=0,pos=0;
for(int i=0; i<T; i++)
{
if(tt[i][0]+tt[i][1]>all)
{
all=tt[i][0]+tt[i][1];
pos=i;
}
}
M[0]=pos;
for(int i=0;i<T;i++)
{
if(tt[i][0]==1)
{
M[T-2]=i;
break;
}
}
for(int i=0;i<T;i++)
if(a[i][i*2+1]==M[T-2])
{
M[T-1]=i;
break;
}
for(int i=2;i<=T-1;i++)
M[T-i-1]=a[M[T-1]][2*M[T-i]+1];
for(int i=0;i<T;i++)
printf(" %d",M[i]);
printf("\n");
}
return 0;
}
上一篇:BZOJ 4159 [Neerc2009]Business Center


下一篇:SQL server学习(一)数据库的基本知识、基本操作(分离、脱机、收缩、备份、还原、附加)和基本语法