本文共 1957 字，大约阅读时间需要 6 分钟。

最小表示法

// 返回最小表示法的始端int get_min(int *s, int len){
       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) k++;        else {
               if (t > 0) i += k + 1;            else j += k + 1;            if (i == j) j++;            k = 0;        }    }    return i < j ? i : j;}

1282 时钟

题目

有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⁹, M <= P）。

输出

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

输入样例

5 2 4

输出样例

4

代码

#include 
   
    using namespace std;#define INF 0x3f3f3f3f#define LL long long#define MX 505const int hash_ = 133331;int n, m, p;int ans;int ke[MX];int cha[MX];map
    
      zz;int get_min(int *s, int len) //返回最小表示法的始端{
       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) k++;        else {
               if (t > 0) i += k + 1;            else j += k + 1;            if (i == j) j++;            k = 0;        }    }    return i < j ? i : j;}void calc() {
       sort(ke, ke + m);    for (int i = 1; i < m; i++)        cha[i - 1] = ke[i] - ke[i - 1];    cha[m - 1] = ke[0] + p - ke[m - 1];    int dex = get_min(cha, m);    LL has = 0, quan = 1;    for (int i = 0; i < m; i++) {
           has += cha[(dex + i) % m] * quan;        quan *= hash_;    }    ans += zz[has];    zz[has]++;}int main() {
       scanf("%d%d%d", &n, &m, &p);    ans = 0;    for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++)            scanf("%d", &ke[j]);        calc();    }    printf("%d\n", ans);    return 0;}
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108409452 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！