4 条题解

  • 33
    @ 2023-6-25 10:27:53
    朴素算法 既然是给一段区间加一个值，那使用差分数组就可以了。每次询问在差分数组d中修改海拔高度，d[j]就表示编号j和编号j-1地点的海拔高度差。使用cal函数来计算海拔高度变化d[j]，弹珠的速度会变化多少。把每一处地点上速度的变化都累加到变量ans，最终ans的值就是弹珠到达N号地点时的速度。 $\\$在计算速度变化的时候，如果d[j]的值为2，表示海拔高度增加了2，那么粪球的速度就要减少2*S。速度ans应该加上-2*S,也就是-d[j]*S。 $\\$如果d[j]的值为-3，表示海拔高度减少了3，那么粪球的速度就要增加3*T。速度ans应该加上3*T,也就是-d[j]*T。
    60分代码 
    
#include <iostream>
using namespace std;
long long a[200005], d[200005];
int N, Q;
long long S, T;
int L, R;
long long x, ans;
long long cal(long long d)
{
    if (d > 0)
    {
        return -d * S;
    }
    else
    {
        return -d * T;
    }
}
int main()
{
	cin >> N >> Q >> S >> T;
	for (int i = 0; i <= N; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= N; i++)
	{
		d[i] = a[i] - a[i - 1];
	}
	for (int i = 0; i < Q; i++)
	{
		cin >> L >> R >> x;
		d[L] += x;
		d[R + 1] -= x;
		ans = 0;
		for (int j = 1; j <= N; j++)
		{
			ans += cal(d[j]);
		}
		cout << ans << endl;
	}
	return 0;
}
    优化算法 朴素的程序时间复杂度为O(q*n)，在q和n比较大的时候，程序就会超时。 $\\$ 如果现在一共有6处地点，海拔高度分别是1 3 5 2 4 3，那么每一处和前一处的海拔高度差就分别是1 2 2 -3 2 -1。假如海拔高度都不变化，弹珠到坡底的速度就可以像这样用cal函数累加计算得出。如果地点2到4处的海拔高度都增加了2，每一处海拔高度差就分别变成了1 4 2 -3 0 -1，可以发现地点3和4这两处的高度差都不变，只有地点2和5这两处的高度差发生了变化，所以弹珠最终速度的计算式子中，也只有cal(2)和cal(5)的值发生了改变。 $\\$同理如果一共有N处地点，弹珠在N号地点的速度是累加1到N处的速度变化。假设现在要把L到R这段区间内所有地点的海拔高度都加上X，编号为L+1到R的所有地点各自与前一个地点的海拔高度差都没有变化，因此 cal(d[L+1])到cal(d[R])的值也都不变。变化的只有编号为L和编号为R+1这两个地点与各自前一个地点的海拔高度差，也就是说只有cal(d[L])和cal(d[R+1])的值发生了变化。 $\\$我们可以用变量ans表示当前弹珠到N号地点的速度，每次修改后只需要计算其中的cal(d[L])和cal(d[R+1])变化了多少。如果从cal(d[L])和cal(d[R+1])增加了多少，ans就增加多少的角度考虑，会比较容易出错。因为海拔高度改变后， d[L]和d[R+1]的值可能由负数变为正数，或者由正数变为负数。例如d[L]的值由2变为-1，此时如果直接把ans上加上cal(-3)的返回值3*T就是错误的。因为实际上cal(d[L])是由cal(2)的返回值-2*T，变为cal(-1)的返回值S，ans应该加上S+2*T。 $\\$可以使用“替换”的思想，先减去原来的cal(d[L])和cal(d[R+1])的值，在修改差分数组d之后，再加上变化后新的值。要注意如果R的值在小于N时，才需要更新cal(R+1)的值，因为不存在编号是N+1的地点。
    AC代码 
    
#include <iostream>
using namespace std;
long long a[200005], d[200005];
int N, Q;
long long S, T;
int L, R;
long long X, ans;
long long cal(long long d)
{
    if (d > 0)
    {
        return -d * S;
    }
    else
    {
        return -d * T;
    }
}
int main()
{
    cin >> N >> Q >> S >> T;
    for (int i = 0; i <= N; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= N; i++)
    {
        d[i] = a[i] - a[i - 1];
        ans += cal(d[i]);
    }
    for (int i = 0; i < Q; i++)
    {
        cin >> L >> R >> X;
        ans -= cal(d[L]);
        d[L] += X;
        ans += cal(d[L]);
        if (R < N)
        {
            ans -= cal(d[R + 1]);
            d[R + 1] -= X;
            ans += cal(d[R + 1]);
        }
        cout << ans << endl;
    }
    return 0;
}
  • -6
    @ 2024-3-12 21:43:33

    AC代码

    #include <iostream> using namespace std; long long a[200005], d[200005]; int N, Q; long long S, T; int L, R; long long X, ans; long long cal(long long d) { if (d > 0) { return -d * S; } else { return -d * T; } } int main() { cin >> N >> Q >> S >> T; for (int i = 0; i <= N; i++) { cin >> a[i]; } for (int i = 1; i <= N; i++) { d[i] = a[i] - a[i - 1]; ans += cal(d[i]); } for (int i = 0; i < Q; i++) { cin >> L >> R >> X; ans -= cal(d[L]); d[L] += X; ans += cal(d[L]); if (R < N) { ans -= cal(d[R + 1]); d[R + 1] -= X; ans += cal(d[R + 1]); } cout << ans << endl; } return 0; }

    • -10
      @ 2023-12-15 20:32:34 
      
//作者温馨提示：千万不要抄代码！！！
//60分代码
#include <bits/stdc++.h>
using namespace std;
long long n,q,s,t,a[2OOOO1],b[2OOOO1];
void a61O9326(){
long long l,r,x;
cin>>l>>r>>x;
b[l]+=x;
b[r+1]-=x;
long long speed=O;
for(long long i=1;i<=n;i++){
if(b[i]>O)
{
speed-=b[i]*s;
}
else
{
speed-=b[i]*t;
}
}
cout<<speed<<endl;
}
int main()
{
cin>>n>>q>>s>>t;
cin>>a[O];
for(long long i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
for(long long i=1;i<=q;i++){
a61O9326();
}
}
//↑ 提交后发现60TLE超时了，于是便改进↓
//AC代码
#include <bits/stdc++.h>
using namespace std;
long long n,q,s,t,a[2OOOO1],b[2OOOO1];
int cal(int x){
if(x>O)
return -x*s;
else
return -x*t;
}
int main()
{
cin>>n>>q>>s>>t;
cin>>a[O];
for(long long i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i]-a[i-1];
}
long long speed=O;
for(long long i=1;i<=n;i++){
speed+=cal(b[i]);
}//计算弹珠原来在n号点的速度
for(long long i=1;i<=q;i++){
long long l,r,x;
cin>>l>>r>>x;
speed+=cal(b[l]+x)-cal(b[l]);
if(r<=n)
speed+=cal(b[r+1]-x)-cal(b[r+1]);//计算速度变化
b[l]+=x;
b[r+1]-=x;
cout<<speed<<endl;
}
return O;
}
/*再提示一下：千万不要抄代码！！！！！！！！！！！
！！！！！！！！！！！！！！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！              ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！  ！！！！！！  ！！！！！！！！！！！！
！！！！！！！！！！！！！！！！！！！！！！！！！*/
      • -21
        @ 2023-9-9 21:02:31

        `

        #include <iostream>
using namespace std;
int n, q;
long long s,t;
long long a[200005],d[200005];
int l,r;
long long x,ans;
long long cal(long long d)
{
	if(d > 0)
	{
		return -d * s;
	}
	else
	{
		return -d * t;
	}
}
int main()
{
	cin >> n >> q >> s >> t;
	for(int i = 0;i <= n;i++)
	{
	    cin >> a[i] ;
	}
	for(int i = 1;i <= n;i++)
	{
		d[i] = a[i] - a[i - 1];
	    ans += cal(d[i]);

	}
	for(int i = 0;i < q;i++)
	{
	    cin >> l >> r >> x;
		ans -= cal(d[l]);
		d[l] += x;
		ans += cal(d[l]);
		if(r < n)
		{
			ans -= cal(d[r + 1]);
			d[r + 1] -= x;
			ans += cal(d[r + 1]);
		}
		cout << ans << endl;
	}
	return 0;
}
      • 1

      【挑战题】弹珠

      信息

      ID
      230
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      (无)
      递交数
      861
      已通过
      449
      上传者
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      3. Worker 0, 15ms
      4. Powered by Hydro v4.9.24 Community, Modified by hetao