define_int_long_long

题解

2025牛客寒假算法基础集训营(6)

/ 注册

全部文章 / 题解（共11篇）

题解 | #智乃的最大子段和取模#

E题 | 智乃的最大子段和取模解题思路：为了求解区间和，本题需要先求前缀和并取模。用表示区间的和取模。在固定右端点的情况下，要想让区间和最大，有两种可能取值：要么尽可能小，要么刚好比大一点点（此时减为负数，需要加上一个p）。先说结论：对于每个，只需找第一个...

C++ 前缀和二分查找

2026-02-21

0 12

题解 | #智乃挖坑#

I题 | 智乃挖坑解题思路：答案具有单调性，因此可以二分答案。已知挖的坑都是三角形，因此可以对差分数组求两次前缀和来构建这种三角形。每次操作复杂度都是，每次的复杂度是。关于对差分数组求两次前缀和后的部分性质见下图（重点看 diff 和 pre2）：示例代码： int n...

C++ 前缀和差分

2026-02-21

0 11

题解 | #小L的扩展#

D题 | 小L的扩展解题思路：本质上是多源bfs题，不过要用优先队列，蓝色的点要么推迟时间，要么不产生任何影响。示例代码： typedef array<int, 3> pi3; const int dx[] = {0, 1, 0, -1}; const int dy[] = {1,...

广度优先搜索

2026-02-21

0 10

题解 | #真白的幻觉#

G题 | 真白的幻觉解题思路：暴力枚举每种数字出现的个数。由于最大取到，而，因此数字位数最多为。示例代码：这一部分是题目中的代码实现。其中可以不使用 unordered_map 缓存结果，也可以使用静态数组缓存（需要额外的边界检查）。 unordered_map<int,...

C++ 暴力

2026-02-10

2 27

题解 | #终于再见#

J题 | 终于再见解题思路：由于繁华度最多大概有种，因此我们可以从大到小对每种繁华度的点都执行一次多源BFS，更新最短路即可。示例代码： vector<int>adj[N]; // 邻接表存图 void solve() { int n, m, INF = LLONG_MAX;...

C++ 广度优先搜索最短路

2026-02-09

0 19

题解 | #权值计算#

H题 | 权值计算解题思路：我们观察题目给出的伪代码，发现任意一个子数组 () 的权值，是其每个前缀数组的数字种类数之和。对于子数组 1 2 3 2，所有前缀及对应种类数为： 1 => 种数字 1 2 => 种数字 1 2 3 => 种数字 1 2 3 2 =>...

C++ 数学

2026-02-08

0 24

题解 | #01矩阵#

E题 | 01矩阵解题思路：首先不考虑连通块数量的限制，考虑最简单的构造方法，每行每列的数量递增：我们发现对应的行和列已经确定：随后我们发现对应的行和列已经确定：随后我们又发现对应的行和列已经确定：发现规律了吗？确定了每行、每列的和后，矩阵就唯一确定了：对于矩...

C++ 构造

2026-02-08

0 30

题解 | #Inverted World#

C题 | Inverted World 解题思路：对于任意一个元素，其最终状态只和它的操作次数的奇偶性有关。操作奇数次会取反，偶数次则不变。也就是说，对于任意一位最多操作一次，即可符合题意。符合题意的最终字符串仅有两种形式：0101...... 和 1010......，我们只需对每个与最终字符...

C++ 贪心

2026-02-08

0 29

题解 | #Energy Synergy Matrix#

F题 | Energy Synergy Matrix 解题思路：手动模拟前几次博弈，不难发现每前进格必然导致次换行。不考虑换行，长度为的网格也得走步才能到终点。因此最小总步数为。示例代码： void solve() { int n; cin >> n; cou...

C++ 博弈

2026-02-08

0 27

题解 | #Blackboard#

H题 | Blackboard 本题解适合刚入门算法的同学，会比较注重细节（啰嗦），已经有算法基础的同学可以直接看官方题解和各位大佬的题解。解题思路：首先对于任意两个非负整数和，如果它们二进制形式的某位不同时为，则对于这一位来说，和操作是等价的。 0+0 == 0|0 == ...

C++ 动态规划前缀和

2026-02-06

3 36