1282 时钟
- 1.0 秒
- 131,072.0 KB
- 40 分
- 4级题
有N个时钟，每个时钟有M个指针，P个刻度。时钟是圆形的，P个刻度均分整个圆。每个时钟每个指针指向整数刻度，并且每个时钟自身指针指向的数字都不同。你可以任意旋转时钟的表盘，但是你不能转指针。问最后有多少对时钟可以变成相同的状态。
例如：N = 5，M = 2，P = 4，5个时钟的数据如下{1, 2} {2, 4} {4, 3} {2, 3} {1, 3}
经过旋转后。 其中(1, 3), (1, 4), (2, 5) 和 (3, 4)是相同的。
给出所有时钟的数据，求有多少对时钟是相同的。
收起
输入
第1行：3个数N, M, P中间用空格分隔，其中N为时钟的数量，M为表针的数量，P为刻度的数量（1 <= M, N <= 500, 1 <= P <= 10^9, M <= P）。 第2 - N + 1行：每行M个数，对应一个时钟，M个指针的位置。
输出
输出有多少对时钟是相同的。
输入样例
5 2 4 1 2 2 4 4 3 2 3 1 3
输出样例
4
分析：
对于每个表，我们要进行哈希处理，即要把它映射为一个数字。如何哈希呢，题目要求表的相对位置相同即可，也就是说我们不能根据每个表头指向的数字来进行判断。我们用每个表头之间的差值。因为相对位置相同的表，它的每个表头之间的差值一定是一样的。对于当前表，我们先排好序，这样找差值才是正确的。我们计算出所有的差值。把差值放到一个数组当中。
这时我们要利用最小表示法，找到一个出发点坐标，从这个坐标的数开始的字符串是最短的。
得到一个字符便可以使用字符串hash了，具体原理：https://blog.csdn.net/sdz20172133/article/details/98859255
得到的hash值保存到map或unordered_map（快一点）即可。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
const int N=505;
const int P=131;int a[N][N];
int n,m,p;int get_minstring(int *s)
{// int len = strlen(s);int len=m;int i = 0, j = 1, k = 0;while(i<len && j<len && k<len){int t=s[(i+k)%len]-s[(j+k)%len];if(t==0)k++;else{if(t > 0)i+=k+1;elsej+=k+1;if(i==j) j++;k=0;}}return min(i,j);
}
unordered_map<ULL,int> mp;//比map快一点int main()
{scanf("%d%d%d",&n,&m,&p);LL ans=0;for(int i=1;i<=n;i++){for(int j=0;j<m;j++){scanf("%d",&a[i][j]);}sort(a[i],a[i]+m);a[i][m]=a[i][0]+p;for(int j=0;j<m;j++){a[i][j]=a[i][j+1]-a[i][j];}int beign=get_minstring(a[i]);ULL s=1;for(int j=0;j<m;j++){s=s*P+a[i][(beign+j)%m];}ans+=mp[s];mp[s]++;}printf("%lld\n",ans);
}