牛客小白月赛100(思维、模拟、BFS、分块、三元环、并查集)
文章目录
- 牛客小白月赛100(思维、模拟、BFS、分块、三元环、并查集)
- A. ACM中的A题
- B. ACM中的C题
- C. ACM中的M题(思维)
- D. ACM中的AC题(模拟,BFS)
- E. ACM中的CM题(分块)
- F. ACM中的ACM题(三元环、并查集)
牛客小白月赛100(思维、模拟、BFS、分块、三元环、并查集)
A. ACM中的A题
根据题意,模拟翻倍即可。
不能只翻倍最短边(eg:2、5、10)。注意数据范围。
#include<bits/stdc++.h>
#define ll long long
using namespace std;int main(){ll a[3];for(int i = 0; i < 3; i++) cin >> a[i]; int flag = 0;for(int i = 0; i < 3; i++){vector<ll> v;for(int j = 0; j < 3; j++){v.push_back(i == j ? a[j]*2 : a[j]);} sort(v.begin(), v.end());if(v[0] + v[1] > v[2]) flag = 1;}cout << (flag ? "Yes" : "No") << endl; return 0;
}
B. ACM中的C题
通过简单思考,得到三种情况:
- n =1:res = -1
- n = 2k:两两交换即可
- n = 2k+1 && n > 1:两两交换会剩下最后一个,需要多交换一次
#include<bits/stdc++.h>
using namespace std;int main(){int n;cin >> n;if(n == 1) n = -3;cout << (n+1) / 2 << endl;return 0;
}
C. ACM中的M题(思维)
B题可以理解为所有数据为一组,C题只需要根据 b 数组对 a 数组进行分组,再分别判断即可。
#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5;map<int, int> v;int main(){int n;cin >> n;int x;for(int i = 1; i <= n; i++) cin >> x;for(int i = 1; i <= n; i++){cin >> x;v[x]++;}int res = 0;for(auto item : v){int val = item.second;if(val == 1){res = -1;break;}res += (val + 1) / 2;}cout << res << endl;return 0;
}
D. ACM中的AC题(模拟,BFS)
说一下我的处理方法:
从起点开始BFS,记录对于起点的相对位移(只记录正方向)。
比如,起点为(XS, YS),相对位移为(x, y),则 “我” 的坐标为(XS + x,YS + y),“另一个我”的坐标为(XS - x,YS - y)。
在BFS的过程中,会有三种情况:
- “我” 和 “另一个我” 都没走到传送门
- 只有 “我” 走到了传送门
- 只有 “另一个我” 走到了传送门
使用一个flag,记录三种状态,分别处理即可。
处理一点点细节就好了。
#include<bits/stdc++.h>
using namespace std;const int maxn = 2e3+5;int visited[maxn*2][maxn*2][3];
char mp[maxn][maxn];int idx[5] = {0, 0, 0, 1, -1};
int idy[5] = {0, 1, -1, 0, 0};typedef struct Node{int x, y; // 对于起点的相对位移 int flag; // 0:两个人都没进,1:正方向的人进了,2:负方向的人进了 int count; // 走了几步
} node;queue<node> qu;void push(node a){ // 进队if(visited[a.x+2001][a.y+2001][a.flag] == 0){ // 注意相对位移可能有负值,是否已经被BFS到qu.push(a);visited[a.x+2001][a.y+2001][a.flag] = 1;}
}int main(){int n, m, x, y;cin >> n >> m >> x >> y;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> mp[i][j];}}int res = -1;qu.push({0, 0, 0, 0}); // 枚举距离起点的相对位移 visited[0][0][0] = 1;while(!qu.empty()){int xx = qu.front().x;int yy = qu.front().y;int flag = qu.front().flag;int count = qu.front().count + 1; // 要走下一步了qu.pop();for(int i = 1; i <= 4; i++){int x1 = x + xx + idx[i], x2 = x - xx - idx[i]; // 下一步两个人的坐标int y1 = y + yy + idy[i], y2 = y - yy - idy[i]; // 下一步两个人的坐标if(flag == 0){ // 都没进 if(x1 < 1 || x1 > n || x2 < 1 || x2 > n) continue;if(y1 < 1 || y1 > m || y2 < 1 || y2 > m) continue; if(mp[x1][y1] == '#' || mp[x2][y2] == '#') continue;if(mp[x1][y1] == '@' && mp[x2][y2] == '@'){res = count; break;}else if(mp[x1][y1] == '@') push({xx + idx[i], yy + idy[i], 1, count});else if(mp[x2][y2] == '@') push({xx + idx[i], yy + idy[i], 2, count});else push({xx + idx[i], yy + idy[i], 0, count});}else if(flag == 1){ // 之前正方向已经进了传送门 if(x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue;if(mp[x2][y2] == '#') continue;if(mp[x2][y2] == '@'){res = count;break;}else push({xx + idx[i], yy + idy[i], 1, count});}else if(flag == 2){ // 之前负方向已经进了传送门 if(x1 < 1 || x1 > n || y1 < 1 || y1 > m) continue;if(mp[x1][y1] == '#') continue;if(mp[x1][y1] == '@'){res = count; break;}else push({xx + idx[i], yy + idy[i], 2, count});}}if(res != -1) break;}cout << res << endl;return 0;
}
E. ACM中的CM题(分块)
根据分块的思想: r e s < = 2 ∗ ( 2 e 5 ) res <= 2 * \sqrt(2e5) res<=2∗(2e5) ,证明:用 ( 2 e 5 ) \sqrt(2e5) (2e5) 的时间,把 m 提升到 ( 2 e 5 ) \sqrt(2e5) (2e5);再用 ( 2 e 5 ) \sqrt(2e5) (2e5)的时间,扫过全部的区间;
总耗时 2 ∗ ( 2 e 5 ) 2 * \sqrt(2e5) 2∗(2e5)。
故而,在一定范围内,枚举每个扫雷能力需要的时间取min即可。
#include<bits/stdc++.h>using namespace std;int main(){int n;cin >> n;vector<int> v;for(int i = 1; i <= n; i++){int x;cin >> x;v.push_back(x);}sort(v.begin(), v.end());int len = unique(v.begin(), v.end()) - v.begin();int res = len;for(int i = 2; i <= 2000; i++){int tmp = i-1, pos = 0;for(int j = 0; j < len; j++){if(pos >= v[j]){continue;}else{pos = v[j] + i - 1; // pos 每次加 i,调和级数,加的次数不多tmp++;}}res = min(res, tmp);}cout << res << endl;return 0;
}
F. ACM中的ACM题(三元环、并查集)
三元环模版题,参考出题人给的博客,传送门:不常用的黑科技——「三元环」 - 洛谷专栏 (luogu.com.cn)
枚举所有三元环,同一个三元环的边加入到同一个集合中,最后判断有几个集合。
用并查集维护集合。
代码详解。
#include<bits/stdc++.h>using namespace std;const int maxn = 2e5 + 5;typedef struct Node{int u, v;
} node;node edge[maxn];
vector<pair<int, int> > mp[maxn];
pair<int, int> visited[maxn];
int in[maxn], f[maxn];int find(int x){if(f[x] == x) return x;else return f[x] = find(f[x]);
}void join(int x, int y){int fx = find(x);int fy = find(y);if(fx != fy){f[fx] = fy;}
}int main(){int ncase;cin >> ncase;while(ncase--){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){ // 初始化in[i] = 0;mp[i].clear();}for(int i = 1; i <= m; i++){cin >> edge[i].u >> edge[i].v;in[edge[i].u]++;in[edge[i].v]++;f[i] = i; // 并查集初始化}for(int i = 1; i <= m; i++){int u = edge[i].u, v = edge[i].v;if(in[u] > in[v]) swap(u, v); else if(in[u] == in[v] && u > v) swap(u, v);mp[u].push_back({v, i}); // 转化为有向图,并记录边id}for(int u = 1; u <= n; u++){for(auto v : mp[u]) visited[v.first] = {u, v.second}; // 记录u可以到达的点 for(auto v : mp[u]){ // 枚举 u->v 中的 vfor(auto w : mp[v.first]){ // 枚举 v->w 中的 wif(visited[w.first].first == u){ // 判断是否构成闭环// 把在三元环的三条边放在一个集合中join(v.second, visited[w.first].second);join(w.second, visited[w.first].second);}}}}int res = 0;for(int i = 1; i <= m; i++){if(i == find(i)){ // 统计有几个集合res++; }}cout << (res == 1 ? "Yes" : "No") << endl;}return 0;
}