文章目录
- 前言
- F、幻形之路
- G、直径与最大独立集
- H，树论函数
- M， 川陀航空学院
- 总结
前言
本次比赛，只能说太多没接触的知识了，还有太容易被题面吓住。
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;
}
总结
该沉淀了~~~~~~~~~~~~
