前綴和與差分

• 前綴和
• • 鳴謝
  • 二維前綴和
  • 激光炸彈
• 差分
• • 求差分
  • 差分求區(qū)間修改
  • 增減序列
  • 最高的牛

前綴和

鳴謝

添加鏈接描述
和
添加鏈接描述

二維前綴和

激光炸彈

題目鏈接

解題思路：

解法思路：我們首先觀察題目，可以建立一個(gè)數(shù)組f[i][j]表示坐標(biāo)為(xi,yj)(xi,yj)上的權(quán)值，那么我們接著思考，因?yàn)轭}目上面說(shuō)了要求算出這個(gè)邊長(zhǎng)為r的正方形面積，而且整個(gè)題目中，只有查詢操作，沒(méi)有修改操作，且內(nèi)存只要略微省著用，就可以滿足O(n2)O(n2)的條件，所以我們可以確認(rèn)這一題可以使用二維前綴和。

代碼：

#include<stdio.h> #include<algorithm> using namespace std; int n,r; int g[5010][5010];int main(){scanf("%d%d",&n,&r);r = min(5001,r); // 變了這里for(int i=1;i<=n;++i){int x,y,w;scanf("%d%d%d",&x,&y,&w);x++,y++;g[x][y] += w;}for(int i=1;i<=5001;++i)for(int j=1;j<=5001;++j)g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];int res = 0;for(int i=r;i<=5001;++i)for(int j=r;j<=5001;++j) res = max(res,g[i][j] - g[i][j-r] - g[i-r][j] + g[i-r][j-r]);printf("%d\n",res);return 0; }

差分

求差分

求出a 的差分序列 b ，$b_1=a_1,b_i=a_i?a_{i?1}(2<=i<=n)$

代碼：

// a 從下標(biāo)一開(kāi)始存 // 如果用原來(lái)的 數(shù)組求差分序列，要從后向前 求，因?yàn)橐Ａ?a[i-1]for(int i = n ; i>1;--i)a[i] = a[i] - a[i-1];

差分求區(qū)間修改

把區(qū)間a[l ,r] 都加上一個(gè) 數(shù) d；
$$b[l]+=d,b[r+1]+=d$$

把區(qū)間a[l ,r] 都減去一個(gè) 數(shù) d；
$$b[l]?=d,b[r+1]+=d$$

增減序列

題目鏈接

解題思路：

首先明確 將所有的數(shù)一樣大，那么從2~n的差分序列都為0，b[1] 可以不為0.都與b[1] 一樣即可。在操作的時(shí)候我們采取貪心的思路，因?yàn)槊恳淮尾僮鞫际且徽回?fù)，至于為什么要是正負(fù)配對(duì)，因?yàn)槲覀兪且@個(gè)B序列2~n都要為0，所以這樣負(fù)數(shù)增加，正數(shù)減少，就可以最快地到達(dá)目標(biāo)為0的狀態(tài)。
至于那些無(wú)法配對(duì)的數(shù)BkBk可以選B1B1或者Bn+1Bn+1，這兩個(gè)不影響的數(shù)，進(jìn)行修改。

因此最小操作次數(shù)為:
$min(pos,neg)+abs(pos?neg)=max(pos,neg)$
種類(lèi)數(shù)：
$abs(pos?neg)+1$

代碼：

#include<stdio.h> #include<math.h> #include<algorithm> using namespace std;const int N = 1e5 + 10; typedef long long ll; int n; ll a[N]; ll psum,nsum; int main(){scanf("%d",&n);psum = nsum = 0;for(int i = 1;i<=n;++i)scanf("%lld",&a[i]);for(int i = n ; i>1;--i)a[i] = a[i] - a[i-1];for(int i = 2;i<= n ;++i)if(a[i] > 0)psum += a[i];else nsum -= a[i]; // 加負(fù)數(shù)的絕對(duì)值，那么直接減就好printf("%lld\n%lld\n",max(psum,nsum),abs(psum - nsum) + 1);return 0; }

最高的牛

題目鏈接

解題思路：

代碼：

#include<stdio.h> #include<stdlib.h> #include<map>using namespace std;const int N = 1e4 + 10; // 用map 和 pair 來(lái)記錄是否重復(fù) map <pair<int ,int>,bool> vis; int a[N],b[N]; int n,p,h,m; int x,y; int main(){scanf("%d%d%d%d",&n,&p,&h,&m);for(int i=1;i<= m ;++i){scanf("%d%d",&x,&y);if(x>y)swap(x,y);if(vis[make_pair(x,y)])continue;b[x+1]-- , b[y]++ ; // 所以不能 x++vis[make_pair(x,y)] = 1; // 因?yàn)檫@里還要用到 x }for(int i=1;i<=n;++i){a[i] = a[i - 1] + b[i];printf("%d\n",h+a[i]);}return 0;}

總結(jié)

以上是生活随笔為你收集整理的基本算法之前缀和与差分的是使用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。