CSU 1581Clock Pictures Hash
来源：程序员人生 发布时间：2015-05-19 08:27:45 阅读次数：2655次
题目链接：点击打开链接
题意：
给出闹钟的n个指针当前所指的角度
求2个闹钟通过旋转后能否相同
思路：
先排个序保证偏序的关系，然后坐差，
枚举第2个串的哪1位和第1个串的第1字符匹配，然后hash判断
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? ⑴ : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
using namespace std;
const int N = 200105;
typedef long long ll;
const int MAGIC = 311, MOD = 1e9 + 7;
template <class T>
struct HASH{
ll h[N], base[N];
inline void init(T *s, int len) {
h[0] = 1;
for (int i = 1; i <= len; ++i) h[i] = (h[i - 1] * MAGIC % MOD + s[i - 1]) % MOD;
base[0] = 1;
for (int i = 1; i <= len; ++i) base[i] = (base[i - 1] * MAGIC) % MOD;
}
inline long long get(int l, int r) {
return (h[r] - h[l - 1] * base[r - l + 1] % MOD + MOD) % MOD;
}
};
HASH <int>A, B;
int a[N], b[N], n;
ll x[N], y[N];
int main(){
while (~scanf("%d", &n)){
for (int i = 0; i < n; i++)rd(a[i]);
for (int i = 0; i < n; i++)rd(b[i]);
sort(a, a + n);
sort(b, b + n);
a[n] = a[0];
b[n] = b[0];
for (int i = 0; i < n; i++){
a[i] = a[i + 1] - a[i]; if (a[i] < 0) a[i] += 360000;
b[i] = b[i + 1] - b[i]; if (b[i] < 0) b[i] += 360000;
}
// for(int i = 0;i < n; i++)cout<<a[i]<<" "; puts("");
// for(int i = 0;i < n; i++)cout<<b[i]<<" "; puts("");
A.init(a, n);
B.init(b, n);
bool ok = A.get(1, n) == B.get(1, n);
for (int i = 2; i <= n && ok == false; i++){
int len = n - i;
// printf("(%d,%d)-(%d,%d)
", 1,len+1,i,n);
// printf("(%d,%d)-(%d,%d)
", len+2,n,1,i⑴);
if (A.get(1, len + 1) == B.get(i, n) && A.get(len + 2, n) == B.get(1, i - 1))
ok = true;
}
if (ok)puts("possible");
else puts("impossible");
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
