【UVA-1594】Ducci Sequence【紫书】

【UVA-1594】Ducci Sequence【紫书】

问题链接:https://vjudge.net/problem/UVA-1594

Solution:

十分常见的方法,使用set进行判重,找循环节。

#include <iostream>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

set<vector<int> > vis;
vector<int> tv, tvv;

inline bool isZero(const vector<int> &v) {
    for (int i = 0; i < v.size(); i++) if (v[i]) return false;
    return true;
}

int main(void) {
    int t, n, tmp;
    scanf("%d", &t);
    while (t--) {
        vis.clear();
        scanf("%d", &n);
        tv.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d", &tmp);
            tv.push_back(tmp);
        }
        while (true) {
            tvv.clear();
            if (isZero(tv)) {
                printf("ZERO\n");
                break;
            }
            if (vis.find(tv) != vis.end()) {
                printf("LOOP\n");
                break;
            }
            vis.insert(tv);
            for (int i = 1; i < tv.size(); i++) {
                tvv.push_back(abs(tv[i - 1] - tv[i]));
            }
            tvv.push_back(abs(tv[tv.size() - 1] - tv[0]));
            tv = tvv;
        }
    }
    return 0;
}