第四题如何确保前100位是正确的呢？就是如何确定要做多少次除法？
第十题我想动规，用二维数据记录区间是否满足要求。
必须吐槽下第八题。。。题目写输出最少的翻转次数，我还以为会有多种可能。。就想都没想就去穷举。。结果却是只有唯一解只需扫描一遍就行了。。

第四题虽然按原公式计算结果在是以黄金分割点精确值为轴线的附近振荡衰减的，但每奇数次（或偶数次）计算的结果是单调逼近的。当然两次计算的结果的差值小于要计算到位的结果精度时就可以停止计算了。

第十题看怎么用动规了，计录所有的区间是不可行的，64M的空间限制是不足以容纳50000的数据范围的。而且按你的想法，其效率并不比直接统计来的高。事实上我说的直接统计也包含了一定的动规思想，比如已知了[i,j]区间的最大值和最小值，则对于[i,j+1],可以通过对比j+1的值与[i,j]的最值而得到[i,j+1]的最值，从而判断[i,j+1]是否是连号区间。

关于这第十题目前我的另一个思路是，设f(a,b)是区间[a,b]的连号区间的数量，设 i = (a + b) / 2，则

f(a,b) = f(a,i) + f(i+1,b) + c(i, i+1)

其中c(i,i+1)表示在区间[a,b]中包含[i,i+1]的子区间中连号区间的数量

如果用普通方法计算c(i,i+1)，则这个算法模型并没有优势，现在我要做的是看能不能将c的计算复杂度降低，如果将c的计算时间复杂度降低到O(x)，则计算f(1,n)的时间复杂度就可以降低到O(log(n)*x)。呵呵，我再想想。

至于第八题，我希望你能证明一下某种翻转方式只需进行0或1次（当然也可以进行多次，但它是多余的）。

第八题我想的是错误的硬币必然是成对出现的，所以只能把错误的硬币移到相邻的位置一起翻转。
第十题如果按照第一种想法的话倒是比较好操作不过如果到了4、5W这样的数据量估计得超时。。。考试时我没看到题目写了输入的是连续的一堆数，结果又做了排序。。这复杂度。。跪了。。。
第七题才100个数据我却用了2个5W大小的数组做记录。。。暴汗中。。。
对了，请问一下一般情况下认为电脑1S可以做多少次非乘除操作呢？

一级够果然够辣, 我觉得一级够应该在Google吧, 如果不在的话Google也最适合你.

发错了,我以为是这个表情呢,呵呵

呵呵，好久不见。我倒想在google。如果我在google工作，我不一定是最优秀的员工，但我一定会非常快乐。

关于第十题至今还没有好的想法。实际测试了一下我上述的方案，使用一个50000的随机全排列计算它的连号区间数量

我的机器配置是联想Y470，酷睿i3虚拟4核处理器，4G内存，win7旗舰版操作系统，使用MinGW编译器编译，多次计算平均耗时在5500ms左右。

下面是测试代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int s[50000];

int f(int left, int right)
{
    int count, mid, i, j, max, min, tmax, tmin;
    
    if(left == right) return 1;
    
    mid = (left + right) >> 1;    
    count = f(left, mid) + f(mid + 1, right);
    max = min = s[mid];
    for(i = mid; i >= left; i--)
    {
        if(s[i] > max) max = s[i];
        if(s[i] < min) min = s[i];
        tmax = max;
        tmin = min;
        for(j = mid + 1; j <= right; j++)
        {
            if(s[j] > tmax) tmax = s[j];
            if(s[j] < tmin) tmin = s[j];
            if(tmax - tmin == j - i) count++;
        }
    }
    return count;
}

int main()
{
    int n, i;
    
    //test code
    int j, t, t0, t1;
    n = 50000;
    for(i = 0; i < n; i++) s[i] = i + 1;
    srand(time(NULL));
    for(i = 0; i < n; i++)
    {
        j = rand() % n;
        t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
    t0 = clock();
    t = f(0, n - 1);
    t1 = clock();
    printf("%d %d", t, t1 - t0);
    //test code end
    
    /*normal code
    for(scanf("%d", &n), i = 0; i < n; scanf("%d", &s[i++]));
    normal code end*/
    return 0;
}

说我吗？层主你认错人了吧一是在论坛里我从来没有过任何争持更不用说得罪人。。。二是我有时会看看论坛里大家的讨论，但比较少发帖和发言，你看我发帖记录里没有过任何不当言行吧。。。

啊。。。我还以为层主是在骂人呢。。。看了B版大神的回帖才知道原来。。。羞涩中

呵呵，误会了，他在说我。我们很早就认识，他一直管我叫一级购，因为我的头像

致飘在空中的小曹同学，该发表一下你的意见了吧，我很期待看看你的想法

继续测试最传统最简单方法，其效果似乎比我之前的方法耗时更短，平时时间在5100ms左右，看起来我之前的方法在效率上并没有什么改善，而递归本身消耗了额外的时间。

对比测试代码如下，其中f2既是传统统计方法。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int s[50000];

int f(int left, int right)
{
    int count, mid, i, j, max, min, tmax, tmin;
    
    if(left == right) return 1;
    
    mid = (left + right) >> 1;    
    count = f(left, mid) + f(mid + 1, right);
    max = min = s[mid];
    for(i = mid; i >= left; i--)
    {
        if(s[i] > max) max = s[i];
        if(s[i] < min) min = s[i];
        tmax = max;
        tmin = min;
        for(j = mid + 1; j <= right; j++)
        {
            if(s[j] > tmax) tmax = s[j];
            if(s[j] < tmin) tmin = s[j];
            if(tmax - tmin == j - i) count++;
        }
    }
    return count;
}

int f2(int n)
{
    int count = 0, i, j, max, min;
    for(i = 0; i < n; i++)
    {
        max = min = s[i];
        for(j = i; j < n; j++)
        {
            if(s[j] > max) max = s[j];
            if(s[j] < min) min = s[j];
            if(max - min == j - i) count++;
        }
    }
    return count;
}

int main()
{
    int n, i;
    
    //test code
    int j, t, t0, t1;
    n = 50000;
    for(i = 0; i < n; i++) s[i] = i + 1;
    srand(time(NULL));
    for(i = 0; i < n; i++)
    {
        j = rand() % n;
        t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
    t0 = clock();
    t = f(0, n - 1);
    t1 = clock();
    printf("%d %d\n", t, t1 - t0);
    t0 = clock();
    t = f2(n);
    t1 = clock();
    printf("%d %d\n", t, t1 - t0);
    //test code end
    
    /*normal code
    for(scanf("%d", &n), i = 0; i < n; scanf("%d", &s[i++]));
    printf("%d", f(0, n - 1));
    normal code end*/
    return 0;
}