哈嘍 大家好！！身為一個大一學生的努力之旅，今天又到了前綴站點了，今天小編分享的題小編沒有接觸過，或許是我太菜了，刷題太少，遇到的題太少了，所以有些題扣了老久，，今天就分享一個題型，
一維的前綴and差分以及二維的前綴的應用，希望大家認真有耐心的看完！！！！！加油騷年
前綴與差分
- 一、一維陣列的前綴與差分
- 二、激光炸彈
- 輸入格式
- 輸出格式
- 關于小編
一、一維陣列的前綴與差分
我用一道題來解釋吧題目如下：
有一個1到6的序列 等差
計算2到第四個數的和
將2 到第四個數每個數都+5
我先科普一下 前綴就是該陣列前n項之和 差分就是從第m項到n項之和 下面看代碼嗷，我用代碼解釋（因為有些序列并不是等差的 所以我們用個通用的 Sn=An+Sn-1 ）這個了解了這個題就簡單了！！！
#include<bits/stdc++.h>
using namespace std;
int s[10],d[10];
int a[10]={0,1,2,3,4,5,6};
int main(){
for(int i=1;i<=6;i++){
s[i]=s[i-1]+a[i];
d[i]=a[i]-a[i-1];
cout<<s[i]<<" ";//計算前驅
}
cout<<endl;
int res = 0;
res=s[4]-s[2-1];
cout<<"區間和是："<<res<<endl;
//差分
d[2]+=5; //讓首項和前一項的差加五
d[4+1] -= 5;//就是讓第五項與第四項的差減五
cout<<"區間改值后序列為 ";
//一步好好理解哦
for(int i =1;i<=6;i++){
s[i] = s[i-1]+d[i];
cout<<s[i]<<" ";
}
return 0;
}
輸出的結果就是看下圖
第15行和第16行代碼一定要好好理解哦！！！！爭取能有進步！！！！！！
二、激光炸彈
這個是一個二維陣列的應用嗷，題就有些難度了 哦！！！ 但是還是劃分到了簡單 因為方法會了可能這個題就不算啥難題了，我就是方法都不會，廢人啊我；；卑微的我！
地圖上有 N 個目標，用整數 Xi,Yi 表示目標在地圖上的位置，每個目標都有一個價值 Wi，
注意：不同目標可能在同一位置，
現在有一種新型的激光炸彈，可以摧毀一個包含 R×R 個位置的正方形內的所有目標，
激光炸彈的投放是通過衛星定位的，但其有一個缺點，就是其爆炸范圍，即那個正方形的邊必須和 x，y 軸平行，
求一顆炸彈最多能炸掉地圖上總價值為多少的目標，
輸入格式
第一行輸入正整數 N 和 R，分別代表地圖上的目標數目和正方形的邊長，資料用空格隔開，
接下來 N 行，每行輸入一組資料，每組資料包括三個整數 Xi,Yi,Wi，分別代表目標的 x 坐標，y 坐標和價值，資料用空格隔開，
輸出格式
輸出一個正整數，代表一顆炸彈最多能炸掉地圖上目標的總價值數目，
我直接寫代碼吧 ！！!其實我代碼里面有注釋，相信各位大聰明們一看就能看得懂了
#include<bits/stdc++.h>
using namespace std;
const int N=5050;
int s[N][N];
int main()
{
int N,R;
cin>>N>>R;
int n=R,m=R;
for(int i=0;i<N;i++)
{
int x,y,w;
cin>>x>>y>>w;
x++,y++;
s[x][y]+=w;
n=max(n,x),m=max(m,y);//至少是R*R初坐標
}
//求二維前綴和
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
//求邊長為R的正方形的最大值
int res=0;
for(int i=R;i<=n;i++)
for(int j=R;j<=m;j++)
res=max(res,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
//這一步相信大家了解了 二維的前綴和計算方法就不難了
cout<<res<<endl;
return 0;
}
我在這里只介紹一下二維陣列的前綴的計算方法吧！因為這個題的核心思想就是二維陣列的前綴！！其實二維陣列的前綴可以理解為面積！！
我如果要求b的面積會怎么做呢（知道坐標）？
肯定嘚讓節點三的坐標減去節點4再減去節點2的坐標 ，起點均是以左上角開始 但是有沒有發現A的黃色這個區域多減了了一遍 所以嘚再加上節點1 怎么樣理解了嘛？
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
再來看這個代碼，是不是就很容易理解了呀？好啦，其他的應該也沒啥難度了，嘿嘿，今天的分享到此結束咯，用了一個兩個小時的時間，效率有點低，別怪嗷，我一直再努力，以后越來越強，一定會寫出更好的博客！！！！
關于小編
我只是一名普通職業本科的一名小白，現在說出我學校的名，別人都懷疑我是專科生，哎、或許以后面試作業也會這樣吧，所以努努力爭取大學拿一個四級證，參加點比賽，拿點獎項！！！
小編QQ:2206730228 大家可以加我好友 然后一起學習噠！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/273771.html
標籤：其他