首页 > 代码库 > UVA 1594：Ducci Sequence (模拟 Grade E)
UVA 1594：Ducci Sequence (模拟 Grade E)
题意：
对于一个n元组(a0,a1,...)，一次变换后变成(|a0-a1|,|a1-a2|,...)
问1000次变换以内是否存在循环。
思路：
模拟，map判重
代码:
#include <cstdio>#include <cstring>#include <map>#include <cmath>#include <algorithm>using namespace std;struct Node{ int a[16]; int n; void read() { for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } } void ducci() { int tmp = a[0]; for (int i = 0; i < n-1; i++) { a[i] = abs(a[i]-a[i+1]); } a[n-1] = abs(a[n-1]-tmp); } bool operator <(const Node &b) const { for (int i = 0; i < n; i++) { if (a[i] != b.a[i]) return a[i]<b.a[i]; } return false; } bool iszero() { for (int i = 0; i < n; i++) { if (a[i] != 0) return false; } return true; }}lala;map<Node, bool>vis;int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &lala.n); lala.read(); vis.clear(); vis[lala] = true; bool isloop = false; for (int i = 0; i < 1010; i++) { lala.ducci(); if (vis[lala]) { isloop = true; break; } vis[lala] = true; } if (isloop && !lala.iszero()) puts("LOOP"); else puts("ZERO"); } return 0;}
UVA 1594：Ducci Sequence (模拟 Grade E)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。