首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
SACK 的引入是为了解决什么问题?
[问答题]
SACK 的引入是为了解决什么问题?
添加笔记
求解答(0)
邀请回答
收藏(1)
分享
纠错
2个回答
添加回答
0
hnust_zhangxin
这里需要用到二维数组的差分和前缀和
利用两个二维数组记录每个植物被施肥的次数(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)
0
牛客799469976号
解决冗余重传问题,精确的通知有哪些包没收到
发表于 2025-06-08 17:30:44
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
难度:
2条回答
1收藏
26浏览
热门推荐
相关试题
如图 1 表示使用快表(页表)的虚...
编程基础
评论
(1)
4.该校1997年男女教师的比例为...
资料分析
言语理解与表达
资料分析
评论
(1)
计算机在工作过程中,若突然停电,(...
计算机常识
普及
C++
Pascal
选择题
评论
(1)
来自
NOIP2008初赛普及组
MySQL中执行 SELECT I...
SQL
评论
(1)
订单表order_table全部记...
查找
数据库
数据分析
SQL
评论
(2)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题