【暴力卡常】UVA10883
RainRecall
·
·
题解
拿到题发现 1\le n\le5\times10^4，于是想到暴力枚举。
暴力复杂度虽然为 O(n^2)，但我们仔细分析一下时间：
而实际循环每次 $j$ 枚举的都会少一次，所以只有 $\frac{n^2}{2}$ 的量级，也就是 $1.25\times 10^9$。
而题目时限 $3$ 秒，平均一秒要跑约 $4.16\times 10^8$，虽然不知道 UVA 机子的速度，但这个量级的小常数对于洛谷评测机是可以勉强过去的。
实测这样 $2.95$ 秒左右勉强卡过。
但是这样还是容易被 hack 掉，为了保险，我们采用卡常大法——循环展开。
顾名思义就是把循环拆开枚举，这样常数会减少很多。
这样就能优化到 $2.18$ 秒左右了。
### AC code
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n;
double a[50005];
int main(){
cin>>T;
for(int c=1;c<=T;++c){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lf",&a[i]);
for(int i=n-1;i>=1;--i){
int j;
for(j=1;j+5<=i;j+=5){
a[j]=(a[j]+a[j+1])/2.0;
a[j+1]=(a[j+1]+a[j+2])/2.0;
a[j+2]=(a[j+2]+a[j+3])/2.0;
a[j+3]=(a[j+3]+a[j+4])/2.0;
a[j+4]=(a[j+4]+a[j+5])/2.0;
}
while(j<=i)a[j]=(a[j]+a[j+1])/2.0,++j;
}
printf("Case #%d: %.3lf\n",c,a[1]);
}
return 0;
}
```