2025牛客暑期多校训练营4

发布时间：2026/7/29 20:55:17

2025牛客暑期多校训练营4

B. Blind Alley

题意：在一个迷宫里，从\((1, 1)\)出发，只能向上向下和向右走，且不能走墙。目的是走到\((1, m)\)。如果走到了第\(j\)列，那么可以看到\([j, \min(j + k, m)]\)这些列的状态。求有没有一个位置，使得其不能到达终点，但从起点到这个点的路径上除了\((i, j)\)的所有点的视野都无法判断这个点不能到达终点。

记\(r[i][j]\)为\((i, j)\)可以到的最右边的列，那么如果\((i, j)\)可以从\((1, 1)\)到达，且\(r[i][j] \geq j + k\)。则可以走到\((i, j)\)这个位置，而不知道这个位置不能到终点。
\(r[i][j]\)可以预处理，从后往前\(dp\)就行。

点击查看代码 
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m, k;std::cin >> n >> m >> k;std::vector<std::string> s(n);for (int i = 0; i < n; ++ i) {std::cin >> s[i];}std::vector r(n, std::vector<int>(m));for (int i = 0; i < n; ++ i) {r[i][m - 1] = m - 1;}for (int j = m - 2; j >= 0; -- j) {for (int i = 0; i < n; ++ i) {r[i][j] = j;}for (int i = 0; i < n; ++ i) {if (s[i][j] == '0') {r[i][j] = std::max(r[i][j], r[i][j + 1]);}}for (int i = 1; i < n; ++ i) {if (s[i][j] == '0') {r[i][j] = std::max(r[i][j], r[i - 1][j]);}}for (int i = n - 2; i >= 0; -- i) {if (s[i][j] == '0') {r[i][j] = std::max(r[i][j], r[i + 1][j]);}}}std::vector f(n, std::vector<int>(m));for (int i = 0; i < n; ++ i) {f[i][0] = 1;}for (int j = 1; j + k - 1 < m; ++ j) {for (int i = 0; i < n; ++ i) {if (s[i][j] == '0') {f[i][j] |= f[i][j - 1];}}for (int i = 1; i < n; ++ i) {if (s[i][j] == '0') {f[i][j] |= f[i - 1][j];}}for (int i = n - 2; i >= 0; -- i) {if (s[i][j] == '0') {f[i][j] |= f[i + 1][j];	}}for (int i = 0; i < n; ++ i) {if (s[i][j] == '0' && f[i][j] && r[i][j] >= j + k && r[i][j] < m - 1) {std::cout << "Yes\n";return;}}}std::cout << "No\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}

D. Determinant of 01-Matrix

赛后补题
题意：构造一个行列式，使得它的值为\(n\)。

构造太难，而且线代早忘了。。。
参考题解，大意就是第一行作为符号，然后下面构造一些等于\(2\)和等于\(1\)的位置，就可以用二进制一位一位构造出\(n\)来。

点击查看代码 
#include <bits/stdc++.h>using i64 = long long;const int N = 29;
int a[210][210];void solve() {for (int i = 0; i < N; ++ i) {a[4 * i + 1][4 * i] = 1;a[4 * i + 1][4 * i + 1] = 1;a[4 * i + 2][4 * i + 1] = 1;a[4 * i + 2][4 * i + 2] = 1;a[4 * i + 3][4 * i] = 1;a[4 * i + 3][4 * i + 2] = 1;a[4 * i + 3][4 * i + 3] = 1;a[4 * i + 4][4 * i + 3] = 1;a[4 * i + 4][4 * i + 4] = 1;}int n;std::cin >> n;for (int i = 0; i <= N; ++ i) {if (n >> i & 1) {a[0][4 * i] = 1;}}std::cout << 4 * N + 1 << "\n";for (int i = 0; i <= 4 * N; ++ i) {for (int j = 0; j <= 4 * N; ++ j) {std::cout << a[i][j] << " \n"[j == 4 * N];}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}

F. For the Treasury!

题意：一个数组取前\(k\)个数的和为价值。你每次可以移动相邻两个数，代价为\(c\)，求可以得到的最大价值。

如果想让第\(i\)个数移动后面去，让\(j\)从后面进来，可以看作\(j\)移动到\(k+1\)，然后\(i\)也移动到\(k+1\)。那么记原本价值为\(sum\)，对于\(i\leq k\)，移动第\(i\)个数代价为\(a[i] + (k-i+1)\times c\)；对于\(i>k\)，贡献为\(a[i] - (i-k+1）\times c\)。我们每次选一对交换，选前面代价最小的和后面贡献最大的。

点击查看代码 
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;i64 c;std::cin >> n >> k >> c;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::vector<i64> A, B;i64 ans = std::accumulate(a.begin(), a.begin() + k, 0ll);for (int i = 0; i < k; ++ i) {A.push_back(a[i] + (k - i) * c);}for (int i = k; i < n; ++ i) {B.push_back(a[i] - (i - k) * c);}std::ranges::sort(A);std::ranges::sort(B, std::greater<>());i64 sum = ans;for (int i = 0; i < A.size() && i < B.size(); ++ i) {sum += -A[i] + B[i];ans = std::max(ans, sum);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}

G. Ghost in the Parentheses

赛后补题。
题意：一个括号序列，每个位置可能变成未知的，对于未知的地方随便填，求有多少情况只能填出来原序列这一种合法的括号序列。

经典技巧是把'('看作\(1\)，')'看作\(-1\)，那么一个合法括号序列的充要条件是，每一个前缀都大于等于\(0\)且总和为\(0\)。
考虑有哪些位置未知只能填出原序列。
满足条件的序列有两个条件：

  1. 左边若干个'('和右边若干个')'组成
  2. 交换最后的'('和最前的')'会使得没有括号序列合法。

如果不满足条件一，则交换一个')'和在它左边的'('，只会使得一些前缀和变大，那么得到的序列依然合法，也就是可以得到其它合法的序列。
考虑条件二的情况是\(((((...))))\)的情况，只要交换最后的')'和最前的'('非法，则只能填出原序列。因为拿一个更前的'('来交换，影响的前缀更多，更容易出现不合法的情况，而我们考虑的是有没有一种方式导致这个序列合法，也就是会有导致合法序列出现，那么希望观察影响前缀最小的情况，如果这个情况也无法产生其它的合法序列，则只能填出来原序列。
有人可能不懂为什么要交换两个括号，因为我们希望选出来的序列随便填也只能得到原序列一种，那么显然左括号右括号个数和原来不一样的填法肯定不合法，那么如果个数还是和原来一样，就可以看作有些括号进行了交换，显然交换相同括号没有意义，所以我们讨论交换左右括号的贡献。
那么对于交换的一对\(i, j\)，\(i\)的位置本来贡献是\(1\)，现在贡献是\(-1\)，那么\([i, j)\)这一段的前缀和都要减\(2\)，则只需要存在一个\(k\in [i, j)\)，满足\(sum[k] < 2\)就行。
实际实现中，我们只需要枚举\(k\)就行了，那么记\(pre, suf\)分别为前缀左括号个数和后缀右括号个数，则有\(2^{pre_k} \times 2^{suf_{k+1}}\)中选法，但发现不同的\(k\)会重复计算一些区间，可以记\(pre\_cnt\)为上一个\(k\)的左括号的个数，\(now\)为上一个\(k\)到当前\(k\)之间的左括号的个数，然后我们不计算全不选的情况，贡献为\(2^{pre\_cnt} \times (2^{now}- 1) \times 2^{suf_{k+1}}\)。最后我们这里是没有计算全是右括号的情况的，已经需要加上不选的情况，那么需要再加上\(2^{\frac{n}{2}}+1\)。
代码省略取模类。

点击查看代码 
constexpr int P = 998244353;
using Z = MInt<P>;void solve() {std::string s;std::cin >> s;int n = s.size();std::vector<int> sum(n + 1);for (int i = 0; i < n; ++ i) {sum[i + 1] = sum[i] + (s[i] == '(' ? 1 : -1);}std::vector<int> suf(n + 2);for (int i = n - 1; i >= 0; -- i) {suf[i + 1] = suf[i + 2] + (s[i] == ')');}std::vector<Z> p(n + 1);p[0] = 1;for (int i = 1; i <= n; ++ i) {p[i] = p[i - 1] * 2;}Z ans = 0;int pre = 0, now = 0;for (int i = 1; i <= n; ++ i) {now += s[i - 1] == '(';if (sum[i] < 2) {ans += p[pre] * (p[now] - 1) * p[suf[i + 1]];pre += now;now = 0;}}ans += p[n / 2];std::cout << ans / p[n] << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}

I. I, Box

题意：推箱子，不过箱子可以自己左右移动。

无解的情况就是一个联通块里箱子和目标个数不一样。
然后就是暴力模拟了，我是用三个\(set\)分别存没到目标的箱子的位置、没有箱子的目标位置、有箱子的目标位置。
然后每次从第二个集合里拿一个\(bfs\)找第一个集合里最近的。记录路径然后模拟，如果遇到第三个集合的位置，则总体往前推，再从最后一个箱子继续推。

点击查看代码 
#include <bits/stdc++.h>using i64 = long long;struct DSU {std::vector<int> fa, cnt;DSU();DSU(int n) {init(n);}void init(int n) {fa.assign(n + 1, 0);cnt.assign(n + 1, 1);std::ranges::iota(fa, 0);}int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}bool merge(int x, int y) {int u = find(x), v = find(y);if (u == v) {return false;}fa[v] = u;cnt[u] += cnt[v];return true;}bool same(int u, int v) {return find(u) == find(v);}int size(int u) {return cnt[find(u)];}
};const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int st[55][55];
std::pair<int, int> pre[55][55];void solve() {int n, m;std::cin >> n >> m;std::vector<std::string> s(n);for (int i = 0; i < n; ++ i) {std::cin >> s[i];}std::set<std::pair<int, int>> a, b, c;DSU dsu(n * m);for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {if (s[i][j] == '@') {a.emplace(i, j);} else if (s[i][j] == '*') {b.emplace(i, j);} else if (s[i][j] == '!') {c.emplace(i, j);}if (s[i][j] == '#') {continue;}for (int k = 0; k < 4; ++ k) {int x = i + dx[k], y = j + dy[k];if (x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#') {continue;}dsu.merge(i * m + j, x * m + y);}}}if (a.empty()) {std::cout << 0 << "\n";return;}{auto get = [&](const std::pair<int, int> & a) -> int {return a.first * m + a.second;};std::vector<int> cnta(n * m), cntb(n * m);for (auto & it : a) {++ cnta[dsu.find(get(it))];}for (auto & it : b) {++ cntb[dsu.find(get(it))];}for (int i = 0; i < n * m; ++ i) {if (cnta[i] != cntb[i]) {std::cout << -1 << "\n";return;}}}std::vector<std::tuple<int, int, char>> ans;auto work = [&](int sx, int sy) -> void {std::queue<std::pair<int, int>> q;memset(st, 0, sizeof st);pre[sx][sy] = {-1, -1};st[sx][sy] = 1;q.emplace(sx, sy);int tx, ty;while (q.size()) {auto [x, y] = q.front(); q.pop();if (a.count({x, y})) {tx = x, ty = y;break;}for (int i = 0; i < 4; ++ i) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '#' || st[nx][ny]) {continue;}pre[nx][ny] = {x, y};st[nx][ny] = 1;q.emplace(nx, ny);}}std::vector<std::pair<int, int>> path;a.erase({tx, ty});while (tx != sx || ty != sy) {path.emplace_back(tx, ty);auto & [nx, ny] = pre[tx][ty];tx = nx;ty = ny;}path.emplace_back(sx, sy);auto getop = [&](const std::pair<int, int> & a, const std::pair<int, int> & b) -> char {int x = a.first - b.first, y = a.second - b.second;if (x == -1 && y == 0) {return 'D';} else if (x == 1 && y == 0) {return 'U';} else if (x == 0 && y == -1) {return 'R';} else {return 'L';}};for (int i = 0; i + 1 < path.size(); ++ i) {if (c.count(path[i + 1])) {int j = i + 1;while (c.count(path[j + 1])) {++ j;}for (int k = j; k >= i; -- k) {ans.emplace_back(path[k].first, path[k].second, getop(path[k], path[k + 1]));}i = j;} else {ans.emplace_back(path[i].first, path[i].second, getop(path[i], path[i + 1]));}}c.emplace(sx, sy);b.erase({sx, sy});};while (b.size()) {auto & [x, y] = *b.begin();work(x, y);}std::cout << ans.size() << "\n";for (auto & [x, y, op] : ans) {std::cout << x + 1 << " " << y + 1 << " " << op << "\n";}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}

相关新闻

花指令汇总

花指令汇总

花指令 BR介绍:在ARM架构下,通过控制对寄存器的赋值,BR到寄存器的值对应地址,来调控程序执行 主要:CMP W0, #0 /* */ CSEL W16, W9, W10, EQ /*W16与X8进行运算 */ BR X8anti-Debug windowsNtGlobalFlag32位;通过获取fs寄…

2026/7/24 2:10:03
第十篇

第十篇

今天是7月24号 烦烦烦，今天被人给举报了，说我上班玩手机我真是一肚子火，我就点了个外卖让他撞见了，说我上班玩手机，有苦说不出，说下次逮到了还要扣我一千块钱工资，服了。

2026/7/28 6:52:02
4. 记录css滚动吸附效果

4. 记录css滚动吸附效果

CSS 滚动吸附的关键属性 在定义滚动吸附前，需要在滚动容器上启用滚动。通过确保滚动容器指定了尺寸且启用 overflow 可启用滚动。 然后可以在滚动容器上使用下列关键属性定义滚动吸附：可滚动容器属性：scroll-snap-type——使用这个属性可定义滚动式视口是否可被吸附、必须还…

2026/7/29 17:25:00

最新新闻

一次谐振频率异常偏高的排查过程（一）

一次谐振频率异常偏高的排查过程（一）

做220kV电缆耐压的时候&#xff0c;按电缆长度和截面算好谐振频率大概在45Hz左右。接好线开始自动扫频&#xff0c;变频电源从20Hz往上扫&#xff0c;锁定的谐振点在68Hz左右&#xff0c;比算出来的高了不少。当时以为是电抗器组合方式选错了&#xff0c;重新组合了一遍再试&am…

2026/7/29 20:54:29
云连锁社区核销小程序开发全攻略：从零到一构建高效核销系统

云连锁社区核销小程序开发全攻略：从零到一构建高效核销系统

编辑&#xff1a;SJ520it黄华一、项目背景与核心价值在连锁零售、社区团购、会员服务等场景中&#xff0c;核销是连接线上营销与线下履约的关键环节。“云连锁社区核销小程序”旨在为拥有多家门店或社区网点的品牌&#xff0c;提供一个统一、高效、可扩展的线上核销解决方案。它…

2026/7/29 20:54:29
零频抑制技术：原理、实现与应用场景解析

零频抑制技术：原理、实现与应用场景解析

1. 零频抑制的基本概念零频抑制&#xff08;Zero-Frequency Suppression&#xff09;是信号处理领域中的一项关键技术&#xff0c;主要用于消除或减弱信号中的直流分量&#xff08;0Hz频率成分&#xff09;。这个概念听起来可能有些抽象&#xff0c;但它在实际应用中无处不在&a…

2026/7/29 20:54:29
计算机毕业设计之基于ECharts的电脑销售信息可视化平台设计与实现

计算机毕业设计之基于ECharts的电脑销售信息可视化平台设计与实现

本研究旨在设计并实现一个基于ECharts的电脑销售信息可视化平台&#xff0c;以应对电商平台日益增长的数据处理和分析需求。系统利用Hadoop、Python和大数据的分布式存储和并行计算能力&#xff0c;结合Hive、HBase、Spark等组件&#xff0c;ECharts可视化技术、实现了对海量电…

2026/7/29 20:54:29
如何提升材料采购效率，减少库存占用？

如何提升材料采购效率，减少库存占用？

引言&#xff1a;工厂采购与库存的“两难困境” 在制造业工厂的日常运营中&#xff0c;物料采购与库存管理就像一对“跷跷板”&#xff0c;常常让管理者陷入两难&#xff1a; 采购少了&#xff1a;生产线随时可能因缺料而停摆&#xff0c;订单交付延误&#xff0c;客户满意度骤…

2026/7/29 20:54:29
高性价比！济南高空清洗、玻璃幕墙石材维保，哪家技术更胜一筹？ - GrowthUME

高性价比！济南高空清洗、玻璃幕墙石材维保，哪家技术更胜一筹？ - GrowthUME

在济南这个现代化城市中，高楼大厦鳞次栉比，玻璃幕墙和石材外立面的建筑随处可见。因此，高空清洗和玻璃幕墙石材维保的需求日益增长。然而，面对众多的服务企业，哪家技术更胜一筹，且具有高性价比呢？今天，我们就来…

2026/7/29 20:53:49

日新闻

自律同行，突破无界！NANK南卡正式官宣曾舜晞成为品牌代言人

自律同行，突破无界！NANK南卡正式官宣曾舜晞成为品牌代言人

近日&#xff0c;国际专注开放式技术研发的声学品牌Nank南卡&#xff0c;正式官宣实力艺人曾舜晞担任品牌代言人。消息一经发出便轰动全网。为什么耳机品牌不选择流量明星、老牌歌手&#xff1f;而且是选择曾舜晞&#xff1f;让我们一起来探索一下&#xff01;比起短期的流量&a…

2026/7/29 0:00:42
【RT-DETR多模态创新改进】CVPR 2025 | 独家特征融合创新改进篇 | 引入RLAB残差线性注意力模块，有效融合并强调多尺度特征，多种改进点，适合红外与可见光融合目标检测任务，有效涨点

【RT-DETR多模态创新改进】CVPR 2025 | 独家特征融合创新改进篇 | 引入RLAB残差线性注意力模块，有效融合并强调多尺度特征，多种改进点，适合红外与可见光融合目标检测任务，有效涨点

一、本文介绍 🔥本文在RT-DETR多模态融合目标检测中引入RLAB残差线性注意力模块，可在不同模态特征交互阶段进行多次残差细化，使可见光、红外等特征在尺度、语义和空间位置上更好对齐；随后将细化特征与解码器输出拼接并生成Q、K、V，通过线性注意力自适应强化关键通道、目…

2026/7/29 0:00:42
AI编程系列02：合并知识功能，给 AI 问数和 RAG 场景打基础

AI编程系列02：合并知识功能，给 AI 问数和 RAG 场景打基础

AI编程系列02&#xff1a;合并知识功能&#xff0c;给 AI 问数和 RAG 场景打基础 在上一期「AI编程系列」中&#xff0c;我们学习了如何构建一个基础的 AI 问答系统&#xff0c;通过简单的输入输出让模型回应问题。但现实世界中的 AI 应用往往需要处理更复杂的场景&#xff1a;…

2026/7/29 0:00:42

周新闻

Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex英雄目标检测数据集 深度学习框架YOLO如何训练APEX数据集

Apex检测数据集数据集详情检测类别&#xff1a; allies enemy tag图片总量&#xff1a;7247张训练集&#xff1a;5139张验证集&#xff1a;1425张测试集&#xff1a;683张标注状态&#xff1a;全部已标注&#xff0c;即拿即用数据格式&#xff1a;支持YOLO格式及其他格式&#…

2026/7/29 11:47:07
智慧飞行 大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 从航线规划、自动飞行、AI识别到数据管理，一个平台全搞定

智慧飞行 大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 从航线规划、自动飞行、AI识别到数据管理，一个平台全搞定

智慧飞行-大疆无人机一站式智能管控平台/支持大疆机场/私有化部署 企业级全域智能无人机一体化管控平台源码&#xff01; 专为电力巡检、安防监控、应急救援、测绘勘察等行业打造&#xff0c;让您的无人机舰队实现 “无人化、自动化、智能化” 管理&#xff01; &#x1f3af; …

2026/7/29 11:47:11
揭秘ChatGPT+Mathematica协同教学：为什么92%的初学者在72小时内建立函数直觉？

揭秘ChatGPT+Mathematica协同教学：为什么92%的初学者在72小时内建立函数直觉？

更多请点击&#xff1a; https://codechina.net 第一章&#xff1a;AI帮助理解数学概念 人工智能正以前所未有的方式重塑数学学习的路径。通过自然语言处理与符号计算的深度融合&#xff0c;AI不仅能解析抽象定义&#xff0c;还能将定理、证明和几何直觉转化为可交互、可验证的…

2026/7/29 11:47:11

月新闻

[C++]内存管理：串顺序存储的内存回收

[C++]内存管理：串顺序存储的内存回收

在串&#xff08;字符串&#xff09;的顺序存储中&#xff0c;内存回收的方式取决于字符串的存储方式以及所使用的编程语言和相关库。以下以 C 为例进行说明&#xff0c;因为 C 对内存管理有较为直接的控制。 1. 基于 char 数组的串顺序存储 如果使用普通的 char 数组来存储字…

2026/7/29 2:28:15
移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试实战：电流、功率、亮度和场景对比

移动端游戏功耗测试：先控制变量，再比较优化是否真的省电 摘要：功耗测试最容易犯的错误，是拿两次不同温度、不同亮度、不同场景的平均功率直接比较。本文给出一套可复现的游戏功耗测试方法，覆盖引擎特性验证、版本回归和黑盒体验测试，并说明如何把功耗与帧率、温控、CPU/G…

2026/7/29 2:28:16
足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

足球口袋教练 HarmonyOS 离线应用实战（03/20）：ArkUI 首页仪表盘搭建

本文是“足球口袋教练 HarmonyOS 离线应用实战”系列第 3 篇。示例项目是一个 HarmonyOS / ArkTS / ArkUI 编写的离线足球训练助手&#xff0c;围绕真实页面、真实截图和可复现操作展开。 本篇要解决的问题 训练 App 的首页不能只展示欢迎语&#xff0c;它要解决“我现在该点哪…

2026/7/29 12:06:51