书上具体所有题目：http://pan.baidu.com/s/1hssH0KO
代码：（Accepted，20 ms）
//UVa1594 - Ducci Sequence #include<iostream> #include<algorithm> #include<cmath> #include<vector> using namespace std; int T,N; bool is_zero(vector<int> &d) { for (const auto &i : d) if (i) return false; return true; } int main() { //freopen("in.txt", "r", stdin); scanf("%d", &T); while (T--) { scanf("%d", &N); vector<int> D(N); for (auto &i : D) scanf("%d", &i); int i = -1; while (++i<200) { int D0 = D[0]; for (int i = 0;i < N-1;++i) D[i] = abs(D[i] - D[(i + 1)]); D[N - 1] = abs(D[N - 1] - D0); if (is_zero(D)) break; } printf(i==200?"LOOP\n": "ZERO\n"); } return 0; }题意：一个数组每次做一定变换，问最后他是循环了还是数据全都变成0了。
分析：模拟每一步，没什么思路。但是纯模拟量很大。 一开始我直接无限模拟每一步，看是不是全变成0了，还是有没有进入循环。 用了set来存储每一步的结果，用set的count函数来判断是不是进入循环了。代码如下：
//UVa1594 - Ducci Sequence #include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<set> using namespace std; int T,N; bool is_zero(vector<int> &d) { for (const auto &i : d) if (i) return 0; return 1; } int main() { //freopen("in.txt", "r", stdin); scanf("%d", &T); while (T--) { scanf("%d", &N); vector<int> D(N); set<vector<int> > P; for (auto &i : D) scanf("%d", &i); P.insert(D); while (1) { vector<int> D2(N); for (int i = 0;i < N;++i) D2[i] = abs(D[i] - D[(i + 1) % N]); if (is_zero(D2)) { printf("ZERO\n"); break; } if (P.count(D2)) { printf("LOOP\n"); break; } D = D2; P.insert(D); } } return 0; }但是结果把我从椅子上吓得掉下去：“Time: 520 MS”！一口老血喷了出来（与上面最终提交的结果差了十万八千里！）。想了想，问题在哪里呢？于是去网上看了大神们的做法：他们都没有做数据是否循环的检查。原来如此，虽然set的检查已经很快了，但是如此庞大的检查量还是不敢恭维。直接不检查，1000次循环，要么出现全0，否则就是循环了，题目给你保证了不过1000的。现在知道了，原来还可以这么玩！ 于是我又去除set的循环检查又提交一遍，100ms。那么与别人的40ms、50ms又差在哪儿呢？一看，人家只循环了500次甚至更少。为什么呢？我试了200，依然AC。想找点规律会不会保证它在200之内必有结果，没找出来。或许是题目的数据太水了原因。（本来猜想只要有一半的数字是一样的就应该是loop，想提交试试的，但是想想加个这样的判断并不合算）所以100ms差不多了。像我这样算是钻空子了。
转载于:https://www.cnblogs.com/xienaoban/p/6798093.html
