牛客小白月赛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 中的 v
for(auto w : mp[v.first]){ // 枚举 v->w 中的 w
if(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;
}