Wannafly summer camp Day6 - D 区间权值
这道题实在是不该，我在化式子的时候，多此一举，把式子进行累加，导致自己当时化的式子是错的，这样导致自己卡了很久，也没想到好的思路，赛后重新分析一波，感觉巨™简单。。。难受的一逼。
这道题的关键在于，W这个东西，由于W序列是受L和R区间变化的，它的取值是由f(i,j)决定的，那么我们知道，肯定要把f(l,r)中 r-l+1相同的归到一处去，这是个思路，先不着急，我们可以先把表达式写出来。
f(1,1)+f(1,2)+f(1,3)+f(1,4)+f(1,5)
f(2,2)+f(2,3)+f(2,4)+f(2,5)
f(3,3)+f(3,4)+f(3,5)
f(4,4)+f(4,5)
f(5,5)
竖着看
w1 w2 w3 w4 w5
我们再把式子进行求和
w1 a1+a2+a3+a4+a5
w2 a1+2a2+2a3+2a4+a5
w3 a1+2a3+3a3+2a4+a5
w4 a1+2a2+2a3+2a4+a5
w5 a1+a2+a3+a4+a5
我们发现一个现象，似乎我们wi是一个对称的，并且我们的算法只支持O(n)复杂度，那么肯定由类似递推式子一样的东西，我们猜测，sum[i]=sum[i-1]+....每个wi对应的a也是对称的，在第一个和第二个之间仅仅是加了个区间和，是不是可以有
sum[i]=sum[i-1]+a[n-i+1]-a[i-1]
我们验证一下发现是这样的。
最后。。。求这个式子有可能被mod成小的数，里面有减号应该是sum[i]=(sum[i-1]+a[n-i+1]-a[i-1])%mod
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #define ll long long using namespace std; int a[300005]; int w[300005]; int sum[300005]; const int mod = 1e9+7; int main(){ int n; while(~scanf("%d",&n)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]=(a[i]+a[i-1])%mod; } for (int i=1;i<=n;i++){ scanf("%d",&w[i]); } for (int i=1;i<=n;i++){ sum[i]=((ll)sum[i-1]+a[n-i+1]-a[i-1]+mod)%mod; } ll ans=0; for (int i=1;i<=n;i++){ ans=(ans+(ll)sum[i]*w[i])%mod; } printf("%lld\n",ans); } return 0; }
查看12道真题和解析
加油！