总结
题单（问题A06～A10／B06～B09）
前缀和、差分
A08 - Two Dimensional Sum
标准的二维前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void solve()
{
int h,w;
cin>>h>>w;
vector<vector<int>> a(h+5,vector<int>(w+5));
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin>>a[i][j];
}
}
vector<vector<int>> pr(h+5,vector<int>(w+5));
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
pr[i][j]=pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1]+a[i][j];
}
}
int q;cin>>q;
while(q--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<pr[x2][y2]-pr[x1-1][y2]-pr[x2][y1-1]+pr[x1-1][y1-1]<<'\n';
}
}
|
A09 - Winter in ALGO Kingdom
标准二维差分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve()
{
int h,w,n;
cin>>h>>w>>n;
vector<vector<int>> a(h+5,vector<int>(w+5));
for(int i=1;i<=n;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
a[x1][y1]++;a[x2+1][y1]--;a[x1][y2+1]--;a[x2+1][y2+1]++;
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
cout<<a[i][j]<<" \n"[j==w];
}
}
}
|
A10 - Resort Hotel
求去掉一个区间后的剩余区间的最大值，做“累最大”操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve()
{
int n;cin>>n;
vector<int> a(n+5);
for(int i=1;i<=n;i++) cin>>a[i];
vector<int> pr(n+5),suf(n+5);
for(int i=1;i<=n;i++){
pr[i]=max(pr[i-1],a[i]);
}
for(int i=n;i>=1;i--){
suf[i]=max(suf[i+1],a[i]);
}
int q;cin>>q;
while(q--){
int l,r;
cin>>l>>r;
cout<<max(pr[l-1],suf[r+1])<<"\n";
}
}
|
B09 - Papers
不能从$(1,1)$开始，要从$(0,0)$开始做前缀和，注意去除越界的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve()
{
int n;cin>>n;
vector<vector<int>> a(N+5,vector<int>(N+5));
for(int i=1;i<=n;i++){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
a[x1][y1]++;a[x2][y1]--;a[x1][y2]--;a[x2][y2]++;
}
ll ans=0;
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
if(i-1>=0&&j-1>=0) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
else if(i-1>=0) a[i][j]+=a[i-1][j];
else if(j-1>=0) a[i][j]+=a[i][j-1];
if(a[i][j]>=1) ans++;
}
}
cout<<ans<<'\n';
}
|