当前位置：首页 > news >正文

牛客小白月赛99题解(BFS、欧拉筛、完全背包、离散化、树状数组、二分查找)

news 来源：原创 2024/9/20 8:53:58

文章目录

牛客小白月赛99
- A. 材料打印（思维）
- B. %%%（思维，数论）
- C. 迷宫（BFS）
- D. 又是一年毕业季（欧拉筛）
- E. 多米诺骨牌(模拟)
- F.自爆机器人（思维、完全背包）
- G. 大鱼吃小鱼(离散化、树状数组、二分）

牛客小白月赛99

康复训练

A. 材料打印（思维）

注意到两种打印方式的价格的大小关系。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;int main(){int ncase;cin >> ncase;while(ncase--){ll a, b, x, y, res;cin >> a >> b >> x >> y;if(x < y) res = a * x + b * y;else res = (a + b) * y;cout << res << endl;}return 0;
}

B. %%%（思维，数论）

思路：

通过简单的思考，n % 2 = 0 or 1，n % 3 = 0，1，2 ，n % 4 = 0，1，2，3，…

观察上述规律，令 n = 2k + 1，则 n % (k+1) 时，取得最大值 k；令 n = 2k，则 n % (k+1)时，取得最大值 k-1。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;int main(){int ncase;cin >> ncase;while(ncase--){ll n;cin >> n;int count = 0;while(n){n = n % (n / 2 + 1);count++;}cout << count << endl;}return 0;
}

C. 迷宫（BFS）

思路：

如果没有超能力，简单BFS，判断从S是否可以到E。

考虑超能力的使用，假设从S出发可以到达 (x_S, y_S)，在使用超能力时，可以走到 x_S 行或 y_S列所在的所有点。

在从S出发BFS时，记录过程点所在的行和列。再从E出发BFS，判断是否可以走到第一遍BFS时记录的行或列。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;const int maxn = 1005;typedef struct Node{int x;int y;
} node;char ma[maxn][maxn];
int flag[maxn][maxn];
int row[maxn], column[maxn];int opx[5] = {0, 0, 0, 1, -1};
int opy[5] = {0, 1, -1, 0, 0};queue<node> qu;int main(){int n, m;cin >> n >> m;int ex, ey;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> ma[i][j];if(ma[i][j] == 'S'){qu.push({i, j});flag[i][j] = 1;}if(ma[i][j] == 'E'){ex = i;ey = j;}}}// 不需要超能力走到 1，需要为 2 int res = 0;while(!qu.empty()){ // 从S开始BFSnode now = qu.front();qu.pop();if(ma[now.x][now.y] == 'E'){res = 1;break;}if(now.x == ex || now.y == ey){res = 1;break;}row[now.x] = column[now.y] = 1; // 记录可以走到的行和列for(int i = 1; i <= 4; i++){int xx = now.x + opx[i];int yy = now.y + opy[i];if(xx < 1 || yy < 1) continue;if(xx > n || yy > m) continue;if(ma[xx][yy] == '#') continue;if(flag[xx][yy]) continue;flag[xx][yy] = 1;qu.push({xx, yy});}}qu.push({ex, ey});flag[ex][ey] = 2;while(res == 0 && !qu.empty()){ // 需要超能力的第二遍BFSnode now = qu.front();qu.pop();int x = now.x, y = now.y;for(int i = 1; i <= 4; i++){int xx = now.x + opx[i];int yy = now.y + opy[i];if(xx < 1 || yy < 1) continue;if(xx > n || yy > m) continue;if(flag[xx][yy] == 2) continue;if(row[xx] || column[yy]){ // 使用超能力联通了res = 1;break;}	if(ma[xx][yy] != '#'){qu.push({xx, yy});flag[xx][yy] = 2;}}}cout << (res ? "YES" : "NO") << endl;return 0;
}

D. 又是一年毕业季（欧拉筛）

思路：

找到没出现的最小的质数即可。

如果对欧拉筛有比较好的理解，是很容易理解的。从小到大，遍历a[i]，不能被a[i] 及其倍数覆盖的第一个数，一定是一个素数。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;const int maxn = 2e5 + 5;int a[maxn], b[maxn];map<int, int> V;int is_prime(int x){if(V[x] == 0){int flag = 1;for(int i = 2; i * i <= x; i++){if(x % i == 0){flag = -1;break;}}V[x] = flag;}return V[x] == 1;
}int main(){int ncase;cin >> ncase;while(ncase--){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];int m = 2*n+1;while(!is_prime(m)) m++;sort(a+1, a+1+n);for(int i = 1; i <= n; i++){int x = a[i];while(x <= m){b[x] = 1;x += a[i];}}int res = -1;for(int i = 2; i <= m; i++){if(b[i] == 0 && res == -1){res = i;}b[i] = 0;}cout << res << endl;}return 0;
}

E. 多米诺骨牌(模拟)

思路：

按照骨牌摆放位置x排序，每次推到最左边，统计会倒几个牌。排序取数量最多的前m个。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;const int maxn = 1e6 + 5;pair<int, int> a[maxn];int main(){int ncase;cin >> ncase;while(ncase--){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i].second;for(int i = 1; i <= n; i++) cin >> a[i].first;sort(a+1, a+1+n);vector<int> v;ll end = a[1].second + a[1].first, count = 1;for(int i = 2; i <= n; i++){ll len = a[i].second + a[i].first;if(a[i].first > end){v.push_back(count);end = len;count = 1;}else{end = max(end, len);count++;}}v.push_back(count); // 注意把最后一组放进去sort(v.begin(), v.end());int res = 0;for(int i = 1; i <= m; i++){if(i > v.size()) break;res += v[v.size()-i];}cout << res << endl;}return 0;
}

F.自爆机器人（思维、完全背包）

思路：

机器人造成的伤害与时间有关，走最多的时间即可。

根据题意，机器人行走的时间T = 机器人从起始位置到怪物的位置n + 机器人在墙之间碰撞的时间S。

第一部分 ”机器人从起始位置到怪物的位置n“ 的时间是固定的，如果机器人可以在时间t之内走到n的话。

第二部分，机器人在墙之间碰撞，可以认为 A -> B -> A 是一组碰撞，这样一组碰撞的时间为 2 * (X_B - X_A)，伤害为 2 * (X_B - X_A)。

显然，我们可以把m个墙，当作m-1个物品，每个物品的体积和价值均为 2 * (X_B - X_A)；背包的容量为 t - n；背包可以装得下的最大的价值即为 S。

ps：这里，由于所有的墙都在 1 ~ n，且每个位置只有一个墙，故而最多有根号n个物品是不同的，注意去重。

时间复杂度：根号n * （t - n）

#include<bits/stdc++.h>
#define ll long long 
using namespace std;const int maxn = 1e6 + 5;ll a[maxn];
bool dp[maxn];int main(){int ncase;cin >> ncase;while(ncase--){int n, m, t;cin >> n >> m >> t;for(int i = 1; i <= m; i++) cin >> a[i];if(n > t) cout << 0 << endl;else if(n == t) cout << n << endl;else{sort(a+1, a+1+m);set<ll> b;for(int i = 2; i <= m; i++) b.insert(2*(a[i] - a[i-1])); // 去重dp[0] = 1;for(auto x : b){for(int i = 0; i <= t-n; i++){dp[i] = dp[i] | dp[i - x];}}int flag = 1, res = n;for(int i = t-n; i >= 0; i--){if(flag && dp[i]){res += i;flag = 0;}dp[i] = 0;}cout << res << endl;}}return 0;
}

G. 大鱼吃小鱼(离散化、树状数组、二分）

思路：

需要枚举每一个鱼出现时刻的端点，维护当前所有出现的鱼的重量。如果是左端点，则需要再模拟吃鱼的过程。
对鱼的重量进行离散化处理，用树状数组存储当前出现的鱼的重量。每次二分找能吃的最大重量的鱼，区间求合维护新重量。循环这个过程，直到没得吃。
```
举个例子，如果当前x=10，池塘里有3，7，11，15....，==二分查找==小于等于x的第一个鱼，区间求和就可以得到当前能吃的鱼的最大总量
```

证明过程2的时间复杂度：

	1. 当于某一个时刻，设小鱼的重量为 x，有一条小鱼不能吃的大鱼的重量为x+1，有一条小鱼可以吃的小小鱼的重量为12. 如果这时小鱼完成了一轮吃食（吃掉了小小鱼），重量变为x+13. 这时，小鱼就可以吃掉大鱼，重量变为 (x+1) * 24. 综上，每一次小鱼通过吃食，可以吃掉大鱼时，其重量最少*2。故而，大约32轮左右的吃食，小鱼的重量就会超过1e9，即可以吃掉所有鱼。

其他细节参见代码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e5 + 10;map<int, int> ID;
int ids = 0;
vector<pair<int, int> > pi;
vector<int> a;ll tree[maxn];void init(){ID.clear();pi.clear();a.clear();ids = 0;
}int get_id(int x){	// 离散化if(ID[x] == 0) return ID[x] = ++ids;return ID[x];
}int lowbit(int x){	return x & (-x);
}void add(int x, int num){while(x < maxn){tree[x] += num;x += lowbit(x);}
}ll query(int x){ll sum = 0;while(x){sum += tree[x];x -= lowbit(x);}return sum;
}int main(){int ncase;cin >> ncase;while(ncase--){init();int n, x;cin >> n >> x;for(int i = 1; i <= n; i++){int l, r, k;cin >> l >> r >> k;pi.push_back({l, k});pi.push_back({r, -k});a.push_back(k);}sort(a.begin(), a.end());for(auto item : a) get_id(item); // 离散化sort(pi.begin(), pi.end());ll ans = 0;for(auto p: pi){						// 枚举每一个时刻int time = p.first, val = p.second;add(get_id(abs(val)), val);			// 维护池塘里现有的鱼if(val > 0){						// 有一个新鱼进入了 ll tmp = x;while(1){		// 循环这个过程int l = 0, r = a.size()-1, pos = -1;while(l <= r){				// 二分查找当前可以吃掉的最大的鱼int mid = l + r >> 1;if(a[mid] <= tmp){ 		l = mid + 1;pos = mid;}else{r = mid - 1;}}if(-1 == pos) break;		// 没有能吃的ll now_tmp = x + query(get_id(a[pos]));		// 区间求合if(now_tmp == tmp) break;	// 吃完没增加重量else tmp = now_tmp;}ans = max(ans, tmp);}}cout << ans << endl;}return 0;
}