zy还能再战

分类

/ 注册

全部文章（共10篇）

题解 | 【模板】01背包（动态规划）

#牛客春招刷题训练营# + 链接动态规划经典问题第0阶段只有0体积设置为0，其他都设置为负无穷即可。 #include <bits/stdc++.h> using namespace std; const int INF=1e9; int main() { ios::sync...

2025-04-08

0 16

题解 | 小红的区间构造

#牛客春招刷题训练营# + 链接简单的倍数知识，n个x的倍数最短是 (n-1)*x+1，最长是 (n+1)*x-1，分类讨论一下 #include <cstdio> #include <iostream> using namespace std; int main() { ...

2025-04-08

1 16

题解 | 活动安排（经典贪心）

#牛客春招刷题训练营# + 链接通过优先选择结束时间最早且与前一个选定活动不冲突的活动，来最大化可以安排的活动数量。1.将所有活动按结束时间升序排序。2.遍历每个活动，对于一个活动，如果它的开始时间晚于或等于上一个选中活动的结束时间，则安排此活动。复杂度：时间复杂度O(nlogn)，空间复杂度O(n...

2025-04-01

0 18

题解 | 1or0（前缀和）

#牛客春招刷题训练营# + 链接容易发现，只有全0的子串“自审值”才是0，因此计算全0子串的个数（res），从总数中减去顺序扫描的同时维护左侧最近的1的位置，扫描到0时作为右端点计算处理询问时，当第l位为0时res可能会包含左端点在区间外面的子串，需要特殊处理减去单次询问复杂度O(1) #inclu...

2025-03-31

2 33

题解 | 而后单调（平衡树）

#牛客春招刷题训练营# + 链接想了半天最终决定还是暴力题目没有保证输入不重复，先判重，重了肯定不能单调然后遍历抽出哪一段，不在该段的全都插到平衡树里面，移动时只需要插一个数删一个数，单次复杂度O(logn)每次遍历在平衡树中查询（最小数）和（最大数+1）的序号，如果相等则说明当前这段可以插入到排序...

2025-03-27

0 32

题解 | 气球谜题（全排列+前缀和）

#牛客春招刷题训练营# + 链接假定染色后的气球形如 xxxyyyzzz ，三个区间的右端点分别为i,j,n用 s(x,i) 表示前i个气球中所有原本是x色的染色费用和则有 cost=(s(y,i)+s(z,i))+((s(x,j)-s(x,i))+(s(z,j)-s(z,i)))+((s(x,n)...

2025-03-27

0 31

题解 | 隐匿社交网络（并查集+按位遍历）

#牛客春招刷题训练营# + 链接题意显然是并查集维护size，但是n平方复杂度是不对的从and考虑按位遍历，稍微注意下细节 #include <bits/stdc++.h> using namespace std; using ll = long long; const int MAX...

2025-03-27

0 16

题解 | 小红的01子序列构造（双指针）

#牛客春招刷题训练营# + 链接首先要理解题意（过于简洁以至于刚开始愣了）01子序列指的就是 "01" 这样两位，那就很显然了计数数组辅助双指针，直接over #include <iostream> using namespace std; using ll = l...

2025-03-26

0 16

题解 | 喜欢切数组的红（前缀和）

#牛客春招刷题训练营# + 链接1.区间和的条件不好处理，转换为总和的三分之一以及前缀和。2.区间内至少有一个正数，转换为下一个正数的索引。3.向后计数，转换为计数的后缀和。 #include <iostream> using namespace std; using ll = lon...

2025-03-24

0 27

题解 | 字符串通配符（简单dp）

#牛客春招刷题训练营# + 链接dp[i][j]表示s串前i个字符跟p串前j个字符是否匹配，简单处理一下'*'字符和'?'字符。比较坑的是s串前缀的'*'字符需要特殊考虑。 #include <bits/stdc++.h> using namespace std; const int ...

2025-03-23

0 22