MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1594 - Ducci Sequence
AOAPC II

UVaOJ 1594 - Ducci Sequence

Chai
2021-11-24 0:00:00在线评测阅读 461

问题描述

p1594

原题链接:UVaOJ 1594 - Ducci Sequence

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-2

解法一:集合去重

可以用集合来判断是否有重复,集合中存放的为 vector<int> 元素,或把其编码成某种 string 串:

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz