CSU 1581Clock Pictures Hash
來源：程序員人生 發布時間：2015-05-19 08:27:45 閱讀次數：2824次
題目鏈接：點擊打開鏈接
題意：
給出鬧鐘的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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
