UVA1594 【Ducci序列 Ducci Sequence】 题解

· · 题解

题意

有一个有 n 个元素的数组，每次操作将其中的每一个数变为它和下一个数的差的绝对值。判断在经过 1000 次操作后，数组中的元素是否会全变为 0。

思路

模拟这 1000 次操作。每一次操作用替身数组更新原数组的值，再将原数组更新为替身数组中的值，最后如果全变为 0，就输出 ZERO，否则输出 LOOP。

注意题目多测。

代码

#include <bits/stdc++.h>
using namespace std;
int T, n;
int a[20], b[20]; // b 数组为替身数组 
int main() {
    cin >> T;
    while(T--) {
        scanf("%d", &n);
        bool ok;
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for(int j = 1; j <= 1000; ++j) {
            for(int i = 1; i <= n; ++i) { // 进行一次操作 
                if (i != n) b[i] = abs(a[i] - a[i + 1]);
                else if (i == n) b[i] = abs(a[i] - a[1]);
            }
            for(int i = 1; i <= n; ++i) a[i] = b[i]; // 将 a 数组更新 
            ok = 1; // 判断是否全为 0 
            for(int i = 1; i <= n; ++i) {
                if (a[i] != 0) ok = 0;
            }
            if (ok) {
                puts("ZERO");
                break;
            }
        }
        if (!ok) puts("LOOP");
    }
    return 0;
}