Ducci Sequence UVA 1594

ゞ浴缸里的玫瑰 2024-02-17 18:48 39阅读 0赞

本题用了两种解法：解法一是直接通过数组，当所有元素为0时，退出循环

解法二则是为了练习STL中容器的使用，利用set容器元素不重复的特点，当元素不同时向set中插入元素，(count()方法判断)有相同时 即为循环；

解法一：

1.  \#include<cstdio>
2.  \#include<cstdlib>
3.  const int len=20;
4.  int a\[len\];
5.  int solve(int n)\{ 
6.   for(int i=0;i<n;i++)\{ 
7.   if(a\[i\])return 0;
8.   \}
9.   return 1;
10. \}
11. int main()\{ 
12.  int T;
13.  scanf("%d",&T);
14.  while(T--)\{ 
15.  int n;
16.  scanf("%d",&n);
17.  for(int i=0;i<n;i++)\{ 
18.  scanf("%d",&a\[i\]);
19.  \}
20.  int temp=1000;
21.  int fg=1;
22.  while(temp--)\{ 
23.  int t=a\[0\];
24.  int i=0;
25.  for(;i<n-1;i++)
26.  a\[i\]=abs(a\[i\]-a\[i+1\]);
27.  a\[i\]=abs(t-a\[i\]);
28.  int flag=solve(n);
29.  if(flag)\{ 
30.  printf("ZERO\\n");
31.  fg=0;
32.  break;
33.  \}
34.  \}
35.  if(fg)printf("LOOP\\n");
36.  \}
37.  return 0;
38. \}

解法二：

1.  \#include<cstdio>
2.  \#include<set>
3.  \#include<cstdlib>
4.  \#include<vector>
5.  using namespace std;
6.  vector<int>vec;
7.  set<vector<int> >set1;
8.  int main()\{ 
9.   int T;
10.  scanf("%d",&T);
11.  while(T--)\{ 
12.  int n;
13.  scanf("%d",&n);
14.  for(int i=0;i<n;i++)
15.  \{int temp;
16.  scanf("%d",&temp);
17.  vec.push\_back(temp);
18.  \}
19.  set1.insert(vec);
20.  int t=1000;
21.  while(t--)\{ 
22.  int i;
23.  for(i=0;i<n;i++)
24.  if(vec\[i\]==0);
25.  else break;
26.  if(i==n)\{ 
27.  printf("ZERO\\n");
28.  break;
29.  \}
30.   
    
31.  int temp=vec\[0\];
32.  for(i=0;i<n-1;i++)
33.  vec\[i\]=abs(vec\[i\]-vec\[i+1\]);
34.  vec\[i\]=abs(temp-vec\[i\]);
35.  if(!set1.count(vec))set1.insert(vec);
36.  else \{ 
37.  printf("LOOP\\n");
38.  break; \}
39.  \}
40.  vec.clear();
41.  set1.clear(); //每一组数据结束都需要清空容器
42.  \}
43.  return 0;
44. \}