?
🏝?專欄：?【藍橋杯備篇】
🌅主頁：?f狐o貍x
“OJ超時不是終點，是算法在提醒你該優化時間復雜度了！”
目錄
3.25?差分數組
一、一維差分
? ? ? ? 題目鏈接：
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 解題代碼：
二、海底高鐵
? ? ? ? 題目鏈接：
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 解題代碼：
三、二維差分
? ? ? ? 題目鏈接：
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 解題代碼：
四、地毯
? ? ? ? 題目鏈接：
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 解題代碼：
3.25?差分數組
? ? ? ? 我們直接用一道題來了解差分數組吧
一、一維差分
? ? ? ? 題目鏈接：
????????【模板】差分
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 還是可以用暴力枚舉來搞定，我們把整個數組遍歷一遍，再把對應位置加上x就行了，但是這樣絕對是會超時長滴，不然我干嘛用這個例題？
? ? ? ? 對于類似的題，我們就可以用差分算法，和前綴和數組類似，我們需要預處理一個差分數組出來
? ? ? ? 這個數組的好處就是當你要在 l ~ r 的區間加上 x 的時候（圖中用2~5）來表示，就只需要在差分數組中的 l 位置加上 x ，r + 1 位置減去 x?，再還原為原數組就行
? ? ? ? ?也就是：a[ l ] += x; a[ r + 1 ] -= x;
? ? ? ? 此時還有人要問：煮波煮波，那怎么還原數組呢？其實把差分數組做一個前綴和運算即可還原?證明如下：
? ? ? ? 解題代碼：
#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];int n, m;int main()
{cin >> n >> m;// 利用差分的性質預處理差分數組for(int i = 1; i <= n; i++){LL x;cin >> x;a[i] += x;a[i + 1] -= x;}// m次操作while(m--){LL l, r, x; cin >> l >> r >> x;a[l] += x;a[r + 1] -= x;}// 利用前綴和還原數組for(int i = 1; i <= n; i++){a[i] = a[i - 1] + a[i];cout << a[i] << " ";}return 0;
}二、海底高鐵
? ? ? ? 題目鏈接：
????????P3406 海底高鐵
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 這里我們只需要知道這個人每段鐵路一共坐了幾次，再判斷是直接買票劃算還是買卡劃算，最后累加輸出即可
? ? ? ? 解題代碼：
#include <iostream>using namespace std;const int N = 1e5 + 10;typedef long long LL;LL f[N];int n, m;int main()
{cin >> n >> m;int l, r; cin >> l;// 利用差分記錄每段鐵路經過的次數for (int i = 2; i <= m; i++){cin >> r;if (l <= r) f[l] += 1, f[r] -= 1;else f[r] += 1, f[l] -= 1;l = r;}// 還原數組for (int i = 1; i <= n; i++){f[i] = f[i - 1] + f[i];}LL ret = 0;for(int i = 1; i < n; i++){LL a, b, c; cin >> a >> b >> c;ret += min(a * f[i], c + b * f[i]);}cout << ret << endl;return 0;
}三、二維差分
? ? ? ? 題目鏈接：
????????【模板】二維差分
? ? ? ? 題目描述：
? ? ? ? 解題思路：
? ? ? ? 如圖所示我們需要對以下結果數組進行操作：
f[x1][y1] + k
f[x2 + 1][y1] -?k
f[x1][y2 + 1] -?k
f[x2 + 1][y2 + 1] -?k
? ? ? ? ?這樣我們累加起來以后就可以得到二維數組中區間+k的操作
? ? ? ? 解題代碼：
#include <iostream>using namespace std;typedef long long LL;const int N = 1010;LL f[N][N];int n, m, q;void insert(int x1, int y1, int x2, int y2, int x)
{f[x1][y1] += x;f[x2 + 1][y1] -= x;f[x1][y2 + 1] -= x;f[x2 + 1][y2 + 1] += x;
}int main()
{cin >> n >> m >> q;// 預處理二維齊差分數組for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){LL a; cin >> a;insert(i, j, i , j ,a);} }while(q--){LL x1, y1, x2, y2, a; cin >> x1 >> y1 >> x2 >> y2 >>a;insert(x1, y1, x2, y2, a);}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}四、地毯
? ? ? ? 題目鏈接：
????????P3397 地毯
? ? ? ? 題目描述：
????????
? ? ? ? 解題思路：
? ? ? ? 這題其實就是把地毯對應的區域全加上一，最后再輸出數組即可解決
? ? ? ? 解題代碼：
?
#include <iostream>using namespace std;const int N = 1010;int f[N][N];int n, m;void insert(int x1, int y1, int x2, int y2, int a)
{f[x1][y1] += a;f[x2 + 1][y1] -= a;f[x1][y2 + 1] -= a;f[x2 + 1][y2 + 1] += a;
}int main()
{cin >> n >> m;while (m--){int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;insert(x1, y1, x2, y2, 1);}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}? ? ? ? 今天就到這里吧，下一期我們將講解二分算法~886~
????????藍橋杯選手日常：
????????睡醒→看題→看不懂→搜題解→抄代碼→被卡常→怒刪重寫→提交→WA
