51nod 1282 时钟
2024-09-03 04:25:27
有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 4
1 2
2 4
4 3
2 3
1 3
Output示例
4 思路:一直以为只要每一个输入的指针位置之差的差值序列相同才是同一对时钟,一直疯狂WA;
借鉴了大佬的博客:https://blog.csdn.net/luricheng/article/details/72993223 感谢大佬orz
一下子明白只要差值字典序最小的序列相同也是同一对时钟,也就是旋转后相同;
将输入的指针排好序,则指针的相对顺序不变,相邻指针差值也不变;比较每个差值序列的字典序最小序列是否相同来判断是不是同一个时钟
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<map>
using namespace std;
int n, m, p, a[][];
bool cmp(int x, int y) { return x < y; }
void solve()
{
map<deque<int>, int>imp;
for (int i = ; i < n; i++) {
int t = a[i][];
for (int j = ; j < m - ; j++)
a[i][j] = (a[i][j + ] - a[i][j]);
a[i][m - ] = p + t - a[i][m - ];
deque<int> ans,tmp;
ans.assign(a[i], a[i] + m);
tmp.assign(a[i], a[i] + m);
for (int j = ; j < m; j++) {
tmp.push_back(a[i][j]);
tmp.pop_front();
ans = min(ans, tmp);
}
imp[ans]++;
}
int ans = ;
for (auto c : imp)
ans += (c.second*(c.second - )) / ;
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n >> m >> p) {
for (int i = ; i < n; i++) {
for (int j = ; j < m; j++)
cin >> a[i][j];
sort(a[i], a[i] + m, cmp);
}
solve();
}
return ;
}
最新文章
- windows下C++高精度计时
- modelsim操作流程
- strstr函数的用法
- JavaScript写一个拼图游戏
- CLR via C#(09)-扩展方法
- July 26th, Week 31st Tuesday, 2016
- ASP.NET MVC 第六回 过滤器Filter
- python文件处理--笔记
- Android 5.1 Camera 架构学习之Camera初始化
- Hack 语言学习/参考---1.Hack 语言
- javascript插入before(),after()新DOM方法
- Spring MVC (JDK8+Tomcat8)
- Python 描述符 data 和 non-data 两种类型
- visual studio git for coding
- 5.JAVA基础复习——JAVA中的static关键字作用与用法
- Win10系列:C#应用控件进阶7
- Magic xpa 3.x很容易将数据导出到Excel中
- Swift学习笔记4
- java基础知识-算术运算符和赋值运算符
- gulp前端自动化环境搭建详解
热门文章
- 使用multiprocessing的问题总结
- odoo 内置协议说明列表
- thinkphp5.0 使用action()报Cannot redeclare app\home\controller\CheckSubstrs()错误
- sql —— group by
- 1月北上广P2P平台之最 平台数成交量现双降
- oracle函数 sqrt(x)
- day2_python之字符编码
- behavior planning——inputs to transition functions
- laravel 增加不存在数据库的字段
- 2019年ICPC南昌网络赛 J. Distance on the tree 树链剖分+主席树