FJUT寒假作业涨姿势题解

作业涨姿势题解"/>

FJUT寒假作业涨姿势题解

题意非常简单易懂，对于涨姿势0，数据非常小，比较容易想到的是直接循环暴力解题完成任务。把数据放入数组arr，循环i,j控制所有区间算和。结果记入vis.

到了涨姿势1，2,3，我们观察数据变化，发现数据变大，0的姿势就会超时。这是我们可以用前缀数组和处理。用sum[i]表示0~i项的和，那么区间i~j的和就可以用sum[j]-sum[i]直接运算得出。而sum数组可以在输入时就处理获得，避免了获得i~j时每次计算一次和造成的时间消耗。

构建sum数组

预处理，ans计数。

到了涨姿势2，去掉了每组大数据为1-2.虽然ai,qi减少。但是实际上sum容易溢出

这是我们就要继续优化算法。我们选择优化这一部分。我们利用前n项和是一个递增数列的特征想到了二分。详见编程时的笔记。

这样我们成功将两层for优化为一成，lower__bound是手写的二分下界函数。

涨姿势3，我们发现一个特点，就是问题特别多，那么我们在每个问题中处理复杂度就比较高了。我们又注意到一个细节数据范围是10^6，那么我们可以用数组标记的方法吧所有结果计算出来，数组标记用下标记入数据是比较经典的方法。有正负可以用两个数组，或者用一个较大数组，以本题为例，200 0000的数组，以第100 0000为分界。下标减去100 0000就是实际大小，下图TMP是数组最大大小，防越界

转载于:.html