51 Nod 1282 时钟 (循环中的最小表示+哈希)

1282 时钟

题目来源： Codility

基准时间限制：1 秒空间限制：131072 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)是相同的。

给出所有时钟的数据，求有多少对时钟是相同的。

Input

第1行：3个数N, M, P中间用空格分隔，其中N为时钟的数量，M为表针的数量，P为刻度的数量（1 <= M, N <= 500, 1 <= P <= 10^9, M <= P）。
第2 - N + 1行：每行M个数，对应一个时钟，M个指针的位置。

Output

输出有多少对时钟是相同的。

Input示例

Output示例


#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
int n,m,p;
int a[505];
int b[505];
int c[505];
unordered_map<string,int>mp;
int getmin(int *s,int len){
    int n=len;
    int i=0,j=1,k=0,t;
    while(i<n && j<n && k<n){
        t=s[(i+k)%n]-s[(j+k)%n];
        if (!t) k++;
        else{
            if (t>0) i+=k+1;
            else j+=k+1;
            if (i==j) j++;
            k=0;
        }
    }
    return i<j?i:j;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d%d%d",&n,&m,&p);
    string ss;
    while(n--)
    {
        for(int i=0;i<m;++i)scanf("%d",&c[i]);
        sort(c,c+m);
        for(int i=0;i<m-1;++i)
        {
            a[i]=c[i+1]-c[i];
        }
        a[m-1]=c[0]+p-c[m-1];

        int pos=getmin(a,m);


        int pp=0;
        for(int i=pos;i<m;i++)
            b[pp++]=a[i];
        for(int i=0;i<pos;i++)b[pp++]=a[i];

        /*
        for(int i=0;i<m;i++)cout<<a[i]<<" ";
        cout<<endl;
        for(int i=0;i<m;i++)cout<<b[i]<<" ";
        cout<<endl;*/

        ss="";
        for(int i=0;i<m;i++)
            ss+=std::to_string(b[i]);
       // cout<<ss<<endl;
        mp[ss]++;
    }
    ll ans=0;
    unordered_map<string,int>::iterator it=mp.begin();
    int tmp;
    while(it!=mp.end())
    {
        tmp=it->second;
        if(tmp<=1){it++;continue;}
        else ans+=(tmp*(tmp-1))/2,it++;
    }

    cout<<ans<<endl;
    return 0;

}