2025牛客寒假算法营2
A题
知识点：模拟
打卡。检查给定的七个整数是否仅包含 1,2,3,5,6 即可。为了便于书写，我们可以反过来，检查这七个整数是否不为 4 和 7。 时间 O(1)；空间 O(1)。
#include <bits/stdc++.h>
using namespace std;
signed main() {
bool flag = true;
for (int i = 1; i <= 7; i++) {
int x;
cin >> x;
if (x == 4 || x == 7) {
flag = false;
}
}
cout << (flag ? "YES" : "NO") << "\n";
}
B题
#include <bits/stdc++.h>
using namespace std;
signed main() {
int n;
cin >> n;
vector<int> in(n + 1);
for (int i = 1; i <= n; i++) {
cin >> in[i];
}
sort(in.begin(), in.end());
cout << in[n / 2 + 1] - 1 << "\n";
}
G题
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 1e18;
signed main() {
int Task = 1;
for (cin >> Task; Task; Task--) {
int n, m;
cin >> n >> m;
i64 Min = 1e18, ans, now = 1;
for (int i = 1; i <= 32; i++) {
if (now >= inf / m) break;
now *= m;
if (abs(n - now) < Min) {
Min = abs(n - now);
ans = i;
}
}
cout << ans << '\n';
}
}
F题
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
signed main() {
int Task = 1;
for (cin >> Task; Task; Task--) {
i64 l, r;
cin >> l >> r;
cout << (r - l + 1) << "\n";
}
}
J题
#include <bits/stdc++.h>
using namespace std;
signed main() {
int n, h, m;
cin >> n >> h >> m;
string Date = to_string(h) + "-";
if (m < 10) {
Date += "0" + to_string(m);
}else {
Date += to_string(m);
}
set<string> A, B, C;
while (n--) {
string user, date, time;
cin >> user >> date >> time;
if (date.substr(0, 7) != Date) {
continue;
}
string h = time.substr(0, 2);
if (h == "07" || h == "08" || time == "09:00:00" ||
h == "18" || h == "19" || time == "20:00:00") {
A.insert(user);
}
if (h == "11" || h == "12" || time == "13:00:00") {
B.insert(user);
}
if (h == "22" || h == "23" || h == "00" || time == "01:00:00") {
C.insert(user);
}
}
cout << A.size() << " " << B.size() << " " << C.size() << "\n";
}
D题
#include <bits/stdc++.h>
using namespace std;
signed main() {
int n;
string s;
cin >> n >> s;
s = "#" + s;
int ans = 0;
for (int ch = 0; ch < 26; ch++) {
int pre = 0, net = 0;
for (int i = 1; i <= n; i++) {
if (s[i] - 'a' != ch) continue;
if (pre != 0) {
ans = max(ans, n - i + 1);
}
pre = i;
}
for (int i = n; i >= 1; i--) {
if (s[i] - 'a' != ch) continue;
if (net != 0) {
ans = max(ans, i);
}
net = i;
}
}
cout << (ans == 1 ? 0 : ans) << "\n";
}
代码的核心思路是针对每个小写字母，分别正向和反向遍历字符串，找出该字母至少出现两次时的最长连续子串长度，最后取所有字母对应的最长长度作为可爱度。不过要注意，此代码实现与题目要求的可爱度定义可能存在差异，因为它仅考虑了单个字母的情况，而没有对所有可能的子串和不连续子序列进行检查。
例子 1
5
ababa
- 分析过程：
- 代码开始遍历每个小写字母。当
ch为'a'时：- 正向遍历：
- 第一次遇到
'a'在位置1，此时pre从0变为1。 - 第二次遇到
'a'在位置3，此时pre不为0，计算n - i + 1 = 5 - 3 + 1 = 3，更新ans为3。 - 第三次遇到
'a'在位置5，计算n - i + 1 = 5 - 5 + 1 = 1，ans保持为3。
- 第一次遇到
- 反向遍历：
- 第一次遇到
'a'在位置5，net从0变为5。 - 第二次遇到
'a'在位置3，此时net不为0，计算i = 3，ans保持为3。 - 第三次遇到
'a'在位置1，计算i = 1，ans保持为3。
- 第一次遇到
- 正向遍历：
- 当
ch为'b'时：- 正向遍历：
- 第一次遇到
'b'在位置2，pre从0变为2。 - 第二次遇到
'b'在位置4，此时pre不为0，计算n - i + 1 = 5 - 4 + 1 = 2，ans保持为3。
- 第一次遇到
- 反向遍历：
- 第一次遇到
'b'在位置4，net从0变为4。 - 第二次遇到
'b'在位置2，此时net不为0，计算i = 2，ans保持为3。
- 第一次遇到
- 正向遍历：
- 最终
ans为3，输出结果为3。
- 代码开始遍历每个小写字母。当
例子 2
3
abc
- 分析过程：
- 当
ch为'a'时：- 正向遍历：只在位置
1遇到'a'，pre变为1，但由于只出现一次，不会更新ans。 - 反向遍历：同理，也不会更新
ans。
- 正向遍历：只在位置
- 当
ch为'b'时：- 正向遍历：只在位置
2遇到'b'，不会更新ans。 - 反向遍历：不会更新
ans。
- 正向遍历：只在位置
- 当
ch为'c'时：- 正向遍历：只在位置
3遇到'c'，不会更新ans。 - 反向遍历：不会更新
ans。
- 正向遍历：只在位置
- 对于其他字母也都只出现一次。最终
ans为0，输出结果为0。
- 当
例子 3
4
aaaa
- 分析过程：
- 当
ch为'a'时：- 正向遍历：
- 第一次遇到
'a'在位置1，pre变为1。 - 第二次遇到
'a'在位置2，此时pre不为0，计算n - i + 1 = 4 - 2 + 1 = 3，更新ans为3。 - 第三次遇到
'a'在位置3，计算n - i + 1 = 4 - 3 + 1 = 2，ans保持为3。 - 第四次遇到
'a'在位置4，计算n - i + 1 = 4 - 4 + 1 = 1，ans保持为3。
- 第一次遇到
- 反向遍历：
- 第一次遇到
'a'在位置4，net变为4。 - 第二次遇到
'a'在位置3，此时net不为0，计算i = 3，ans保持为3。 - 第三次遇到
'a'在位置2，计算i = 2，ans保持为3。 - 第四次遇到
'a'在位置1，计算i = 1，ans保持为3。
- 第一次遇到
- 正向遍历：
- 对于其他字母都未出现。最终
ans为3，输出结果为3。
- 当
K题
#include <bits/stdc++.h>
using namespace std;
// 定义长整型别名，在某些涉及较大整数运算时可使用
#define i64 long long
// 定义上下左右四个方向在 x 轴上的偏移量
int dx[4] = {-1, 1, 0, 0};
// 定义上下左右四个方向在 y 轴上的偏移量
int dy[4] = {0, 0, -1, 1};
// 解决问题的核心函数
void solve() {
int n, m;
// 读取矩阵的行数 n 和列数 m
cin >> n >> m;
// 定义一个字符串向量 s 来存储矩阵，索引从 1 开始，方便后续处理
vector<string> s(n + 1);
for (int i = 1; i <= n; i++) {
// 读取每一行的字符串
cin >> s[i];
// 在每行字符串前添加一个字符 '%'，使得字符串索引从 1 开始
s[i] = "%" + s[i];
}
// 用于存储每个蓝色极大连通块对应的需要敲碎的灰色砖块数量，初始大小为 m * n + 1
vector<int> g(m * n + 1);
// 记录当前蓝色极大连通块的编号
int idx = 0;
// 二维布尔数组 v，用于标记矩阵中每个位置是否已被访问过
vector<vector<bool>> v(n + 1, vector<bool>(m + 1, false));
// 二维数组 num，记录每个蓝色砖块所属的蓝色极大连通块编号
vector<vector<int>> num(n + 1, vector<int>(m + 1, 0));
// 定义一个递归的 lambda 函数 dfs，用于深度优先搜索蓝色极大连通块
auto dfs = [&](auto &&self, int x, int y, int id) -> void {
// 标记当前位置 (x, y) 的蓝色砖块属于编号为 id 的连通块
num[x][y] = id;
// 标记当前位置已被访问
v[x][y] = true;
for (int i = 0; i < 4; i++) {
// 计算相邻位置的 x 坐标
int nx = dx[i] + x;
// 计算相邻位置的 y 坐标
int ny = dy[i] + y;
// 检查相邻位置是否在矩阵范围内、未被访问且为蓝色砖块
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !v[nx][ny] && s[nx][ny] == '1') {
// 递归调用 dfs 函数继续搜索相邻的蓝色砖块
self(self, nx, ny, id);
}
}
};
// 遍历矩阵中的每个位置
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 如果当前位置未被访问且为蓝色砖块
if (!v[i][j] && s[i][j] == '1') {
// 蓝色极大连通块编号加 1
++idx;
// 调用 dfs 函数开始搜索该连通块
dfs(dfs, i, j, idx);
}
}
}
// 再次遍历矩阵，统计每个蓝色极大连通块周围的灰色砖块数量
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i][j] == '0') {
// 用于记录当前灰色砖块相邻的不同蓝色极大连通块编号
map<int, bool> ex;
for (int k = 0; k < 4; k++) {
// 计算相邻位置的 x 坐标
int nx = i + dx[k];
// 计算相邻位置的 y 坐标
int ny = j + dy[k];
// 检查相邻位置是否在矩阵范围内、为蓝色砖块且该连通块编号未被记录过
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && s[nx][ny] == '1' && !ex[num[nx][ny]]) {
// 对应连通块的需要敲碎的灰色砖块数量加 1
g[num[nx][ny]]++;
// 标记该连通块编号已被记录
ex[num[nx][ny]] = true;
}
}
}
}
}
// 对存储每个连通块对应灰色砖块数量的向量 g 进行排序，排序范围是从索引 1 到 idx
sort(g.begin() + 1, g.begin() + idx + 1);
// 输出需要敲碎的最少灰色砖块数量
cout << g[1];
}
int main() {
// 关闭输入输出流的同步，提高输入输出效率
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// 循环调用 solve 函数，这里 t 为 1，即只调用一次
while (t--) solve();
return 0;
}