问题描述
p1594原题链接:UVaOJ 1594 - Ducci Sequence
相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-2
解法一:集合去重
可以用集合来判断是否有重复,集合中存放的为 vector<int> 元素,或把其编码成某种 string 串:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector<int> num(n), temp(n); for (int i = 0; i < n; i++) cin >> num[i]; set<vector<int>> mem; while (1) { // Σヽ(゚Д ゚; )ノ Don't worry mem.insert(num); bool all_zero = true; for (int i = 0; i < num.size(); i++) { temp[i] = abs(num[i] - num[(i + 1) % num.size()]); if (temp[i] != 0) all_zero = false; } num = temp; if (all_zero) { cout << "ZERO" << endl; break; } if (mem.count(num)) { cout << "LOOP" << endl; break; } } } return 0; } |
1 |
#TODO |