首页 > 试题广场 >

SACK 的引入是为了解决什么问题?

[问答题]
SACK 的引入是为了解决什么问题?
这里需要用到二维数组的差分和前缀和
利用两个二维数组记录每个植物被施肥的次数(tim[n+2][m+2]),还有每次施肥就在该植物加k*k(sum[n+2][m+2]),如果tim[i][j]*k*k==sum[i][j],表示该植物存活,因为一旦有一次施肥错误就会si亡。
至于为什么不是加k,是为了避免出现碰巧的情况,如:
该植物k=2,被k=1和k=3施肥了一次,施肥总次数为2,1+3=2*k*k。
代码如下:
#include<iostream>
#include<vector>
using namespace std;
int n,m;
void f(int x1,int y1,int x2,int y2,int k,vector<vector<long long int>> &add)
{
    add[x1][y1]+=k;
    add[x1][y2+1]-=k;
    add[x2+1][y1]-=k;
    add[x2+1][y2+1]+=k;
}
int main()
{
    int T;
    cin>>n>>m>>T;
    int a[n+1][m+1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    int x1,y1,x2,y2,k;
    vector<vector<long long int>> tim(n+2,vector<long long int>(m+2)),sum(n+2,vector<long long int>(m+2));
    while(T--){
        cin>>x1>>y1>>x2>>y2>>k;
        f(x1,y1,x2,y2,k,sum);
        f(x1,y1,x2,y2,1,tim);
    }int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            tim[i][j]=tim[i][j]+tim[i-1][j]+tim[i][j-1]-tim[i-1][j-1];
            if(tim[i][j]*a[i][j]!=sum[i][j]) ans++;
        }
    }cout<<ans<<endl;
}


发表于 2025-07-09 21:01:03 回复(0)
解决冗余重传问题,精确的通知有哪些包没收到
发表于 2025-06-08 17:30:44 回复(0)