---

前言

本次比賽，只能說太多沒接觸的知識了，還有太容易被題面嚇住。

---

F、幻形之路

題目鏈接：幻形之路

解題思路：
對于這一題只需要，分別從起點和終點找到不經過障礙的點，然后在從當前點集，利用BFS找最短距離。

代碼如下：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) 
#define ll long long
#define endl '\n'const int N = 1010;  
const int INF = 0x3f3f3f3f;   // 表示無窮大
int dx[] = {0, 1, 0, -1};     // 四個方向的x偏移量
int dy[] = {1, 0, -1, 0};     // 四個方向的y偏移量
char s[N][N];           
bool va[N][N], vb[N][N];      // va: 從起點可達的點；vb: 從終點可達的點
int d1[N][N], d2[N][N];       // d1: 起點到各點的最短距離；d2: 終點到各點的最短距離
int n, m;        //從(sx,sy)出發進行BFS，標記所有可達的'.'格子
void bfs1(int sx, int sy, bool vis[N][N]) {queue<pair<int, int>> q;  // 定義隊列用于BFSq.push({sx, sy});         // 起點入隊vis[sx][sy] = true;       // 標記起點為已訪問while (!q.empty()) {      // 隊列不為空時循環int x = q.front().first;   // 取出隊首元素x坐標int y = q.front().second;  // 取出隊首元素y坐標q.pop();                  // 隊首元素出隊// 遍歷四個方向for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];  // 計算新坐標// 檢查邊界和是否可訪問if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (!vis[nx][ny] && s[nx][ny] == '.') {vis[nx][ny] = true;  // 標記為已訪問q.push({nx, ny});    // 新點入隊}}}
}// 從所有已標記的點出發進行BFS，計算到各點的最短距離，多源BFS 
void bfs2(queue<pair<int, int>>& q, int dist[N][N]) {while (!q.empty()) {      // 隊列不為空時循環int x = q.front().first;   // 取出隊首元素x坐標int y = q.front().second;  // 取出隊首元素y坐標q.pop();                  // 隊首元素出隊// 遍歷四個方向for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];  // 計算新坐標// 檢查邊界和是否已計算過距離if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (dist[nx][ny] == INF) {dist[nx][ny] = dist[x][y] + 1;  // 更新最短距離q.push({nx, ny});              // 新點入隊}}}
}
void solve() {cin >> n >> m;  for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> s[i][j];     va[i][j] = vb[i][j] = false; // 重置可達標記d1[i][j] = d2[i][j] = INF;   // 重置距離為無窮大}}bfs1(1, 1, va);  // 從起點(1,1)出發BFS，標記可達點// 如果終點可達，直接輸出0（不需要拆墻）if (va[n][m]) {cout << 0 << endl;return;}bfs1(n, m, vb);  // 從終點(n,m)出發BFS，標記可達點// 計算起點到各點的最短距離queue<pair<int, int>> q;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (va[i][j]) {          // 如果是起點可達的點d1[i][j] = 0;         // 距離初始化為0q.push({i, j});       // 加入隊列}}}bfs2(q, d1);  // BFS計算最短距離// 清空隊列，計算終點到各點的最短距離while (!q.empty()) q.pop();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (vb[i][j]) {          // 如果是終點可達的點d2[i][j] = 0;         // 距離初始化為0q.push({i, j});       // 加入隊列}}}bfs2(q, d2);  // BFS計算最短距離// 尋找需要拆除的最少墻數int ans = INF;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {// 如果是墻，且同時被起點和終點的BFS覆蓋if (s[i][j] == '#' && d1[i][j] != INF && d2[i][j] != INF) {ans = min(ans, d1[i][j] + d2[i][j] - 1); // 更新最小拆墻數}}}cout << ans << endl;
}int main() {IOS;int t;cin >> t;          while (t--) {solve();}return 0;
}

G、直徑與最大獨立集

題目鏈接：直徑與最大獨立集


解題思路：
通過手寫模擬，或者打表，會發現其實是有規律的。

注意當n等于2時也是有解的
代碼如下：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
signed main()
{IOS;ll t;cin>>t;while(t--){ll n;cin>>n;if(n==4)cout<<-1<<endl;else if(n==2)cout<<1<<" "<<2<<endl; else if(n==3){cout<<1<<" "<<2<<endl;cout<<2<<" "<<3<<endl;}else{ll t=(n+2)/3+2;if(n%3!=1){for(ll i=2;i<=t;i++)cout<<1<<" "<<i<<endl;for(ll i=t;i<n;i++)cout<<i<<" "<<i+1<<endl;}else{for(ll i=2;i<=t;i++)cout<<1<<" "<<i<<endl;for(ll i=t;i<n-1;i++)cout<<i<<" "<<i+1<<endl;cout<<3<<" "<<n<<endl;}}}return 0;
}

H，樹論函數

題目鏈接：樹論函數

解題思路，通過打表可以找到規律，就是每一個點都能相互到達，
主要難點就是對于題目的理解。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
signed main()
{IOS;ll t;cin>>t;while(t--){ll s,r,l;cin>>s>>l>>r;cout<<r-l+1<<endl;}return 0;
}

M， 川陀航空學院

題目描述： 川陀航空學院

解題思路：
這一就是對于并查集的考察，以及重邊與連通量的關系

代碼如下：

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
const ll N=1e6+1;ll n,m;
ll s[N];          // 并查集的父節點數組
ll h[N];          // 并查集的樹的高度，用于優化合并// 初始化并查集
void inset() {for(ll i=1;i<=n;i++)s[i]=i, h[i]=0;  // 每個節點的父節點初始為自己，秩初始為0
}// 查找節點x所在集合的根節點，并進行路徑壓縮
ll finds(ll x) {ll r=x;// 找到根節點rwhile(s[r]!=r)r=s[r];// 路徑壓縮：將x到根節點路徑上的所有節點直接連接到根節點rll i=x,j;while(i!=r) {j=s[i];    // 暫存i的父節點s[i]=r;    // 將i的父節點直接設為根節點ri=j;       // 處理下一個節點}return r;
}// 合并節點x和y所在的集合
void mset(ll x,ll y) {x=finds(x), y=finds(y);  // 先找到兩個節點的根節點if(x == y) return;      // 如果已經在同一集合，直接返回// 按秩合并：將高度小的樹合并到高度大的樹if(h[x]==h[y]) {h[x]++;      // 兩棵樹高度相同，合并后x的高度加1s[y]=x;      // 將y的根節點設為x} else {if(h[x]<h[y])s[x]=y;  // x的高度較小，將x的根節點設為yelses[y]=x;  // y的高度較小，將y的根節點設為x}
}signed main() {IOS;cin>>n>>m;inset();           // 初始化并查集// 處理每條邊，合并邊的兩個端點所在集合for(ll i=0;i<m;i++) {ll x,y;cin>>x>>y;mset(x,y);}// 統計連通分量的數量（根節點的數量）ll ans=0;for(ll i=1;i<=n;i++) {if(s[i]==i) ans++;  // 如果節點i的父節點是自己，它就是一個根節點}cout<<m-n+2*ans-1<<endl;return 0;
}

---

總結

該沉淀了~~~~~~~~~~~~