zy还能再战

分类

/ 注册

全部文章（共14篇）

题解 | 变幻莫测（数学逆推）

#牛客春招刷题训练营# + 链接这题还比较有意思，主要使用逆推法由题目 x'=x+y, y'=x-y 可得 x=(x'+y')/2, y=(x'-y')/2显然目标状态是 (a, a)因为对换没有意义，倒数第一个状态只能是 (a, 0)对倒数第二个状态进行分类讨论，可以为 (0, a) 或者 (a/...

2025-05-20

2 44

题解 | 游游的字母翻倍（技巧模拟）

#牛客春招刷题训练营# + 链接显然最终的字母还是原串的字母，只是重复了很多遍维护一下原串每个字母每次操作后重复多少遍就好啦 #include <bits/stdc++.h> using namespace std; const int N = 1024; char s[N]; int...

2025-05-13

0 31

题解 | 墙壁划线（小学数学）

#牛客春招刷题训练营# + 链接首先将问题分解为 \型对角线加上 /型对角线，这两条线是有交点的，但需要注意交点有可能不在边界交点不在边界时，最终个数是其中一条个数的两倍；交点在边界时，最终个数是其中一条个数的两倍再减1于是可以只分析 \型对角线，此时通过约分 a 和 b 的最大公约数 g 继续分...

2025-05-07

2 45

题解 | 能量项链（区间dp）

#牛客春招刷题训练营# + 链接区间dp经典题啦先套路复制一遍解环，然后用dp[i][j]表示第i颗到第j颗聚合完之后的最优值，每次枚举最后是哪两段聚合就可以 #include <iostream> using namespace std; using ll = long long; ...

2025-04-29

0 36

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

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

2025-04-08

0 36

题解 | 小红的区间构造

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

2025-04-08

3 33

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

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

2025-04-01

0 124

题解 | 1or0（前缀和）

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

2025-03-31

3 52

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

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

2025-03-27

0 41

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

#牛客春招刷题训练营# + 链接假定染色后的气球形如 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 61