牛客小白月赛111

链接

A

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 10, INF = 0x3f3f3f3f;

int a[N], b[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(b, -0x3f, sizeof b);
    for (int i = 0; i < 3; ++i) cin >> a[i];
    for (int i = 0; i < 3; ++i) cin >> b[i];

    sort(b, b + 3);
    int res = 0;

    for (int i = 0; i < 3; ++i) {
   
        // 第一个大于a[i]的下标
        int u = upper_bound(b, b + 3, a[i]) - b;
        if (u < 3) {
   
            res++;
            b[u] = -INF;
        }
    }

    cout << (res >= 2 ? "Yes" : "No") << "\n";

    return 0;
}

B

贪心, 因为只有两个邪恶英雄合并有收益

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n;
string str;

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> str;

	int res = 0;
	for (char c : str) {
   
		if (c == 'y') res++;
	}
	
	for (int i = 1; i < n; ++i) {
   
		if (str[i] == 'n' && str[i - 1] == 'n') {
   
			res++, i++;
		}
	}
	
	cout << res << "\n";
	
	return 0;
}

C

滑动窗口, 建立一个$map$存储每个字符串出现的次数, 因为只能更改一次因此如果不满足条件就缩减窗口大小

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 1e6 + 10;

int n;
string s[N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> s[i];

	map<string, int> map;
	int l = 0, r = 0;
	int res = 0;

	while (r < n) {
   
		map[s[r]]++;
		while ((map.size() == 2 && min(map.begin()->second, map.rbegin()->second) > 1) || map.size() > 2) {
   
			map[s[l]]--;
			if (map[s[l]] == 0) map.erase(s[l]);
			l++;
		}

		if (map.size() == 2) res = max(res, r - l);
		else res = max(res, r - l + 1);
		r++;
	}
	
	cout << res << "\n";

	return 0;
}

D

数字三角形模型, 多加一些边界, 如果某位置在某时刻变为石头, 那价值就是$-inf$, 这样该位置一定无法到达

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 1010, INF = 0x3f3f3f3f;

int n, m, cnt;
int g[N][N];
LL f[N][N];
int tag[N][N];

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			cin >> g[i][j];
		}
	}
	memset(f, -0x3f, sizeof f);
	memset(tag, 0x3f, sizeof tag);

	cin >> cnt;
	for (int i = 0; i < cnt; ++i) {
   
		int u, v, w;
		cin >> u >> v >> w;
		tag[u][v] = w;
	}

	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			if (i - 1 + j - 1 >= tag[i][j]) g[i][j] = -INF;
		}
	}

	f[0][1] = 0;
	LL res = 0;
	for (int i = 1; i <= n; ++i) {
   
		for (int j = 1; j <= m; ++j) {
   
			f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
			res = max(res, f[i][j]);
		}
	}

	cout << res << "\n";

	return 0;
}

E

鸽了

F