Ducci Sequence
Description
A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a1, a2, ... , an), the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:
Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with 8,11,2,7 takes 5 steps to reach the zeros tuple:
The 5-tuple sequence starting with 4,2,0,2,0 enters a loop after 2 steps:
Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.
Input
Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n(3n
15), which represents the size of a tuple in the Ducci sequences. In the following line, n integers are given which represents the n-tuple of integers. The range of integers are from 0 to 1,000. You may assume that the maximum number of steps of a Ducci sequence reaching zeros tuple or making a loop does not exceed 1,000.
Output
Your program is to write to standard output. Print exactly one line for each test case. Print `LOOP' if the Ducci sequence falls into a periodic loop, print `ZERO' if the Ducci sequence reaches to a zeros tuple.
The following shows sample input and output for four test cases.
Sample Input
4 4 8 11 2 7 5 4 2 0 2 0 7 0 0 0 0 0 0 0 6 1 2 3 1 2 3
Sample Output
ZERO LOOP ZERO LOOP
开始想着用 队列 做，然后用 map 判断是否重复 ， 然而 出现问题了， 猜测应该是在map中查找重复数列 有问题，代码如下
#include <iostream> #include <string> #include <queue> #include <cmath> #include <map> //vector判断是否重复 using namespace std; typedef queue<int> Queue; map<Queue,int> loop; queue<int> ling; int main() { int T; cin >> T; while(T--){ int n, a; queue<int> ducci; cin >> n; for(int i = 0;i < n; i++)ling.push(0); loop[ling] = 1; for(int i = 0;i < n; i++){ cin >> a; ducci.push(a); } int time = 0; bool flag = false; while(++time){ cout<<"----------------------------"<<endl; cout<<time<<endl; a = ducci.front(); cout<<a; ducci.pop(); int start = a,t; loop[ducci] = 1; for(int i = 1;i < n; i++){ t = ducci.front(); cout<<"--"<<t; ducci.pop(); ducci.push(abs(a-t)); a = t; } ducci.push(abs(start-t)); cout<<endl; for(int i = 0;i < time;i++){ cout<< "i "<<i<<endl; if(loop[ducci]!=0){ if(i == 0)cout << "ZERO" << endl; else cout << "LOOP" <<endl; flag = true; break; } } if(flag)break; } } // system("pause"); return 0; }
然后 用数组做吧
用map判定老出现问题，然后就真的不会用stl做了
#include <iostream> #include <cmath> using namespace std;
int ducci[1000][20];
int main() { int T; cin >> T; while(T--){ int n; cin >> n; for(int i = 0;i < n; i++)ducci[0][i] = 0; for(int i = 0;i < n; i++)cin >> ducci[1][i]; int time = 1; bool flag = false; while(++time){ //cout<<"----------------------------"<<endl; //cout<<time<<endl; int t; for(int i = 0;i < n - 1; i++){ ducci[time][i] = abs(ducci[time-1][i+1] - ducci[time-1][i]); //cout<<ducci[time][i]<<"--"; } ducci[time][n-1] = abs(ducci[time-1][0] - ducci[time-1][n-1]); //cout<<ducci[time][n-1]<<endl; for(int i = 0;i < time;i++){ int flag1 = 1; for(int j = 0;j < n;j++){ if(ducci[time][j] != ducci[i][j]){ flag1 = 0; break; } } if(flag1){ if(i == 0)cout << "ZERO" << endl; else cout << "LOOP" <<endl; flag = true; break; } } if(flag)break; } } // system("pause"); return 0; }
还是太不熟悉stl了
看别人的代码用stl做的
结构体 重载运算符什么的 都不熟唉
#include <cstdio> #include <cstring> #include <map> //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; }
还是强