首页 > 代码库 > uva 1594 Ducci Sequence 哈希
uva 1594 Ducci Sequence 哈希
用了一个滚动数组
转化为字符串哈希问题
复杂度不是很大所以用set直接搞
如果数据规模大一点的话考虑用vector实现链地址法
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <set>#include <queue>#include <stack>#include <map>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> P;const int maxn = 20;const ull b = 9973;int main(){ // freopen("in.txt", "r", stdin); int T; scanf("%d", &T); int a[2][maxn]; while(T--) { set<ull> check; int cur = 0; int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[cur][i]); } ull e = 0; for(int i = 0; i < n; i++) { e = e*b + a[cur][i]; } check.insert(e); bool ans = true; for(int k = 0; k < 1010; k++) { for(int i = 0; i < n; i++) { a[cur^1][i] = abs(a[cur][i] - a[cur][(i+1)%n]); } cur ^= 1; e = 0; for(int i = 0; i < n; i++) { e = e*b + a[cur][i]; } if(e == 0) { ans = false; break; } else if(check.count(e)) { ans = true; break; } } if(ans) printf("LOOP\n"); else printf("ZERO\n"); } return 0;}
uva 1594 Ducci Sequence 哈希
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。