首页 > 代码库 > 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 哈希