牛客小白月赛99 ABCDE （fg挺典的，明天补）
A题：材料打印
思路
打印彩色的肯定要用y元一张的，黑白的选较便宜的一个即可
代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {LL a, b, x, y;cin >> a >> b >> x >> y;LL ans = b * y + a * min(x, y);cout << ans << endl;}return 0;
}B题：%%%
思路
感觉上来说，这个是单调的。那就尽可能的维持最大即可。
如何维持最大？每次mod x / 2 + 1
代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {LL n; cin >> n;LL ans = 0;while (n) {if (n & 1) n /= 2;else n %= (n / 2 + 1);ans += 1;}cout << ans << endl;}return 0;
}C题：迷宫
吐槽
怎么说呢，也可能是我菜的缘故。感觉应该把D和E放C前面
思路
bfs就是过不了，也欢迎在下面提供您的优秀做法
我是用连通块做的，这样复杂度最大1e9
对于终点，它旁边的"."和“#”如果被“打通”那么就可以到达终点
对于起点附近的所有.，我们观察能否使用超能力到终点附近，这个判断我们直接暴力
代码
#include <iostream>
#include <queue>
using namespace std;
using PII = pair<int, int>;
const int N = 1010;
char a[N][N];
int vis[N][N], ok[N][N];
int n, m;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int main() {cin >> n >> m;queue<PII> q, p;for (int i = 1; i <= n; i ++ ) {for (int j = 1; j <= m; j ++ ) {cin >> a[i][j];if (a[i][j] == 'S') q.push({i, j}), vis[i][j] = 1;if (a[i][j] == 'E') p.push({i, j}), ok[i][j] = 1;}}while (p.size()) {int x = p.front().first, y = p.front().second;p.pop();for (int i = 0; i < 4; i ++ ) {int xn = x + dx[i], yn = y + dy[i];if (xn < 1 || xn > n || yn < 1 || yn > m) continue;if (ok[xn][yn]) continue;if (a[xn][yn] == '#') ok[xn][yn] = 1;else {ok[xn][yn] = 1;p.push({xn, yn});}}}while (q.size()) {int x = q.front().first, y = q.front().second;if (ok[x][y]) return cout << "YES" << endl, 0;q.pop();for (int i = 0; i < 4; i ++ ) {int xn = x + dx[i], yn = y + dy[i];if (xn < 1 || xn > n || yn < 1 || yn > m) continue;if (vis[xn][yn]) continue;if (a[xn][yn] == '#') {int temp1 = xn, temp2 = yn;while (temp1 >= 1 && temp1 <= n && temp2 >= 1 && temp2 <= m) {if (ok[temp1][temp2]) return cout << "YES" << endl, 0;temp1 += dx[i], temp2 += dy[i];}continue;}vis[xn][yn] = 1;q.push({xn, yn});}}cout << "NO" << endl;return 0;
}D题： 又是一年毕业季
思路
如果没有2，那么直接选2
如果有了2的话，那么所有的偶数都不能选了
然后我们考虑奇数，如果这个奇数没有出现，并且是质数才可以选择
因为如果这个奇数是质数的话，说明其可以被之前遍历过的奇数给整除
代码
#include <iostream>
#include <map>
using namespace std;
int main() {int tt; cin >> tt;while (tt -- ) {int n; cin >> n;map<int, int> p;for (int i = 1; i <= n; i ++ ) {int x; cin >> x;p[x] += 1;}if (!p[2]) {cout << 2 << endl;continue;}for (int i = 3; ; i += 2) {if (p[i]) continue;bool flag = true;for (int j = 2; j * j <= i; j ++ ) {if (i % j == 0) {flag = false;break;}}if (flag) {cout << i << endl;break;}}}return 0;
}E题：多米诺骨牌
思路
我们先sort一边，然后观察每个位置上能够推倒多少个牌子，然后再从左往右遍历，维护每一个线段的最右边r（就是能推到的最远距离）。最后我们用优先队列取m个即可
代码
#include <bits/stdc++.h>
using namespace std;
using PLL = pair<long long, long long>;
using LL = long long;
int main() {int tt; cin >> tt;while (tt -- ) {int n, m; cin >> n >> m;vector<PLL> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i].second;for (int i = 1; i <= n; i ++ ) cin >> a[i].first;sort(a.begin() + 1, a.end());vector<LL> pos(n + 2);pos[n + 1] = (LL)1e18;for (int i = 1; i <= n; i ++ ) pos[i] = a[i].first;priority_queue<LL> q;vector<LL> add(n + 1);for (int i = 1; i <= n; i ++ ) {int id = upper_bound(pos.begin() + 1, pos.end(), a[i].first + a[i].second) - pos.begin();int num = id - i;add[i] = num;}LL r = 0;int len = 0;for (int i = 1; i <= n; i ++ ) {r = max(r, i + add[i] - 1);len += 1;if (i == r) {q.push(len);len = 0;}}m = min(m, (int)q.size());LL ans = 0;while (m -- ) {ans += q.top();q.pop();}cout << ans << endl;}return 0;
}