基礎知識參考：

csp突擊前兩題常用算法代碼_ccf csp常用優化算法-CSDN博客

差分

什么是差分數組？

差分數組是原數組相鄰元素之間的差值構成的數組。對于原數組?a，其差分數組?b?定義為：

• b[1] = a[1]?(假設?a[0] = 0)

• b[i] = a[i] - a[i-1]?(對于 i > 1)

為什么差分數組有用？

差分數組的神奇之處在于：對原數組的區間加減操作可以轉化為對差分數組的兩個單點操作。

差分例題

一個長度為n的整數序列。
對其進行m次操作，每個操作包含三個整數l, r, c，表示將序列中[l, r]之間的每個數加上c。
請你輸出進行完所有操作后的序列。

###輸入格式
第一行包含兩個整數n和m。
第二行包含n個整數，表示整數序列。
接下來m行，每行包含三個整數l，r，c，表示一個操作。
###輸出格式
共一行，包含n個整數，表示最終序列。
###數據范圍
1≤n,m≤100000,
1≤l≤r≤n,
?1000≤c≤1000,
?1000≤整數序列中元素的值≤1000

如果用暴力做法每次都循環一遍區間的值然后操作的話時間肯定會超限
所以用一種巧妙地方法就是構造差分數組，
對區間[l,r]進行+c操作時只需要在差分數組里對b[l] += c,b[r+1] -= c
然后累和恢復數組時就可對區間內所有數+c

區間更新原理

當我們要對原數組?a?的區間?[l, r]?中每個元素加?c?時：

1. 對差分數組?b[l] += c：這使得?a[l]?及之后的所有元素都增加了?c

2. 對差分數組?b[r+1] -= c：這抵消了?a[r+1]?及之后元素的增加，使得只有?[l, r]?區間內的元素增加了?c

恢復原數組

通過計算差分數組的前綴和，我們可以恢復出更新后的原數組：

• a'[i] = b[1] + b[2] + ... + b[i]

或者下標直接從1開始比較好：

#include<iostream>
using namespace std;
int a[100010], b[100010];
int main(){int n, m;cin>>n>>m;for(int i = 1; i <= n; i ++){cin>>a[i];b[i] = a[i] - a[i - 1];	//構造差分數組}while(m --){int l, r, c;cin>>l>>r>>c;b[l] += c;	b[r + 1] -= c;}for(int i = 1; i <= n; i ++){b[i] = b[i] + b[i - 1];cout<<b[i]<<" ";}return 0;
}

第36次CCF認證-第四題

?參考題解：

CCF-CSP第36次認證第四題——跳房子【NA！巧妙利用BFS】_csp跳房子-CSDN博客

第36次ccf-csp題解（思維） - devoteeing - 博客園

? 應該屬于經典題，BFS尋找最短路徑，我還是不太熟悉，需要多多刷題啊。依稀記得當時有過短短的掙扎，然而確實是練少了，真的想不起來。（OK啊，后面我要系統練一下搜索算法了）

? 好吧，承認我讀完題目之后真的毫無頭緒，這種求最優解法的題目我真的束手無措。

BFS

參考資料：

BFS（圖論） - OI Wiki

第十三章 DFS與BFS（保姆級教學！！超級詳細的圖示！！）_dfs bfs-CSDN博客

BFS 全稱是?Breadth First Search，中文名是寬度優先搜索，也叫廣度優先搜索。

是圖上最基礎、最重要的搜索算法之一。

所謂寬度優先。就是每次都嘗試訪問同一層的節點。 如果同一層都訪問完了，再訪問下一層。

這樣做的結果是，BFS 算法找到的路徑是從起點開始的?最短?合法路徑。換言之，這條路徑所包含的邊數最小。

在 BFS 結束時，每個節點都是通過從起點到該點的最短路徑訪問的。

算法過程可以看做是圖上火苗傳播的過程：最開始只有起點著火了，在每一時刻，有火的節點都向它相鄰的所有節點傳播火苗。

例題1-走迷宮

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int map[N][N],mark[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},n,m,ans;
void bfs()
{memset(mark,-1,sizeof mark);queue<PII>q;q.push({0,0});mark[0][0]=0;while(!q.empty()){PII top=q.front();for(int i=0;i<4;i++){int nex=top.first+dx[i],ney=top.second+dy[i];if(nex>=0&&nex<n&&ney>=0&&ney<m&&mark[nex][ney]==-1&&map[nex][ney]==0){mark[nex][ney]=mark[top.first][top.second]+1;q.push({nex,ney});}}q.pop();}cout<<mark[n-1][m-1];
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&map[i][j]);}}bfs();
}

BFS模版

void bfs(int u) {while (!Q.empty()) Q.pop();Q.push(u);vis[u] = 1;d[u] = 0;p[u] = -1;while (!Q.empty()) {u = Q.front();Q.pop();for (int i = head[u]; i; i = e[i].nxt) {if (!vis[e[i].to]) {Q.push(e[i].to);vis[e[i].to] = 1;d[e[i].to] = d[u] + 1;p[e[i].to] = u;}}}
}void restore(int x) {vector<int> res;for (int v = x; v != -1; v = p[v]) {res.push_back(v);}std::reverse(res.begin(), res.end());for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);puts("");
}

其中，

圖的存儲方式（鏈式前向星）

head[u]?和?e[i]?是鏈式前向星（一種圖的鄰接表存儲方式）的關鍵部分：

• head[u]：存儲節點?u?的第一條邊的編號（索引）。

• e[i]：是一個結構體數組，存儲第?i?條邊的信息，通常包括：

  • e[i].to：這條邊指向的節點（終點）。

  • e[i].nxt：下一條與?u?相連的邊的編號（類似于鏈表中的?next?指針）

BFS應用

例題2-密室

問題 - 173B - Codeforces

一個n*m的圖，現在有一束激光從左上角往右邊射出，每遇到 '#'，你可以選擇光線往四個方向射出，或者什么都不做，問最少需要多少個 '#' 往四個方向射出才能使光線在第n行往右邊射出。

此題目正解不是 0-1BFS，但是適用 0-1BFS，減小思維強度，賽時許多大佬都是這么做的。

做法很簡單，一個方向射出不需要花費（0），而往四個方向射出需要花費（1），然后直接來就可以了。

#include <deque>
#include <iostream>
using namespace std;constexpr int INF = 1 << 29;
int n, m;
char grid[1001][1001];
int dist[1001][1001][4];
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
deque<int> q;  // 雙端隊列void add_front(int x, int y, int dir, int d) {  // 向前方加if (d < dist[x][y][dir]) {dist[x][y][dir] = d;q.push_front(dir);q.push_front(y);q.push_front(x);}
}void add_back(int x, int y, int dir, int d) {  // 向后方加if (d < dist[x][y][dir]) {dist[x][y][dir] = d;q.push_back(x);q.push_back(y);q.push_back(dir);}
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) cin >> grid[i];for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)for (int k = 0; k < 4; k++) dist[i][j][k] = INF;add_front(n - 1, m - 1, 3, 0);while (!q.empty()) {  // 具體搜索的過程，可以參考上面寫的題解int x = q[0], y = q[1], dir = q[2];q.pop_front();q.pop_front();q.pop_front();int d = dist[x][y][dir];int nx = x + fx[dir], ny = y + fy[dir];if (nx >= 0 && nx < n && ny >= 0 && ny < m)add_front(nx, ny, dir, d);  // 判斷條件if (grid[x][y] == '#')for (int i = 0; i < 4; i++)if (i != dir) add_back(x, y, i, d + 1);}if (dist[0][0][3] == INF)cout << -1 << endl;elsecout << dist[0][0][3] << endl;return 0;
}

習題

• 「NOIP2017」奶酪

雙端隊列 BFS：

• CF1063B. Labyrinth
• CF173B. Chamber of Secrets
• 「BalticOI 2011 Day1」打開燈泡 Switch the Lamp On