UVA1594 Ducci序列 Ducci Sequence 题解
OoXiao_QioO
·
·
题解
前言
简单模拟题。
题意
# 思路
对于每组数据，我们先模拟个 $1000$ 次，对于每一次循环，定义一个 $b$ 数组，每一次的 $b_i$ 都为 $a$ 数组中相邻两个数的差的绝对值，所以 $b_i = |a_i-a_{i+1}|$。
但是第 $n$ 个数的时候呢？通过研究样例，发现 $b_n$ 为 $|a_n-a_1|$，更新完 $b$ 数组，比对一下是否都为 $0$ 即可。
提交上去，结果 $\verb!TLE!$ 了，考虑优化。
发现模拟 $1000$ 次实在是太浪费空间了，我们根据~~人类心理学~~概率学考虑一下，发现数据的强度使正正好好 $1000$ 次模拟后数组全为 $0$ 的几率还是太小了，最多大约是在 $70$ 左右，于是模拟 $70$ 次就可以了。
# 代码（核心部分）
```cpp
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=70;i++)//模拟 70 次足矣。
{
for(j=1;j<n;j++)
b[j] = abs(a[j]-a[j+1]);//b 数组储存相邻两个数的差的绝对值。
b[n] = abs(a[n]-a[1]);
for(j=1;j<=n;j++)
a[j] = b[j];//把 b 数组复制到 a 数组。
f = 1;//假设全为 0。
for(j=1;j<=n;j++)
{
if(a[j])//有一个数不符合，直接跳出循环、
{
f = 0;
break;
}
}
if(f)
{
puts("ZERO");
break;
}
}
if(!f)
puts("LOOP");
}
```