51nod 1282 时钟-白红宇

51nod 1282 时钟

阅读量：6573 次

发布时间：2019-06-24

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

题目来源：

基准时间限制：1 秒空间限制：131072 KB 分值: 40

有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示例

5 2 41 22 44 32 31 3

Output示例

4 思路：一直以为只要每一个输入的指针位置之差的差值序列相同才是同一对时钟，一直疯狂WA； 借鉴了大佬的博客： 感谢大佬orz 一下子明白只要差值字典序最小的序列相同也是同一对时钟，也就是旋转后相同； 将输入的指针排好序，则指针的相对顺序不变，相邻指针差值也不变；比较每个差值序列的字典序最小序列是否相同来判断是不是同一个时钟

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
            6 using namespace std; 7 int n, m, p, a[505][505]; 8 bool cmp(int x, int y) { return x < y; } 9 void solve()10 {11     map
            
             
              , int>imp;12 for (int i = 0; i < n; i++) {13 int t = a[i][0];14 for (int j = 0; j < m - 1; j++)15 a[i][j] = (a[i][j + 1] - a[i][j]);16 a[i][m - 1] = p + t - a[i][m - 1];17 deque
              
                ans,tmp;18 ans.assign(a[i], a[i] + m);19 tmp.assign(a[i], a[i] + m);20 for (int j = 0; j < m; j++) {21 tmp.push_back(a[i][j]);22 tmp.pop_front();23 ans = min(ans, tmp);24 }25 imp[ans]++;26 }27 int ans = 0;28 for (auto c : imp) 29 ans += (c.second*(c.second - 1)) / 2;30 cout << ans << endl;31 }32 int main()33 {34 ios::sync_with_stdio(false);35 while (cin >> n >> m >> p) {36 for (int i = 0; i < n; i++) {37 for (int j = 0; j < m; j++)38 cin >> a[i][j];39 sort(a[i], a[i] + m, cmp);40 }41 solve();42 }43 return 0;44 }

转载于:https://www.cnblogs.com/wangrunhu/p/9438378.html

你可能感兴趣的文章