retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #小黑的区间# D 双指针

枚举可以选取的区间的最后一个数字，可以选取的的区间一定是以枚举的数字为末尾的一段，而且这一段内相同数字的下标之差<= k 因此当枚举的位置向右移动一位后，区间的的左端可能不变，也可能因为区间内划入了新加入的这个数导致左端必须向右移动，而无论哪种情况不会让左端左移，所以随着枚举位置右移，左端也是...

C++ 双指针

2024-06-03

0 187

题解 | #小苯的排列构造# 牛客周赛 Round 44 E

E 小苯的排列构造我们注意到当 n > 9 时可以有如下构造方法: 对于前面较小的数, p[i]为i+4 i p[i] 1 5 2 6 3 7 4 8 5 9 6 10 假设n为10, 那么还剩下7, 8, 9, 10还没有对应的p[i], 我们考...

C++ 枚举脑筋急转弯

2024-05-26

1 349

题解 | 牛客周赛 Round 44 D #因子区间#

D 因子区间首先，1e5之内的数最多拥有128个因子，所以可以从 1 ~ 128 枚举因子个数，分别计算。对于每个因子数记录下来该因子数对应的原数组中每个数的下标，二分找到范围内的个数后利用组合数进行计算。时间复杂度在这之前，可以预处理1e5内每个数的因子个数. int n, q; vo...

C++ 二分查找数学

2024-05-26

6 482

题解 | #牛牛吃水果的顺序# 拓扑排序 + 分层全排列

知识点拓扑排序 dfs 全排列解题思路首先很明显要进行拓扑排序来确定拓扑关系以及检查是否有环。在拓扑排序过程中，没有相互制约关系的两个元素可以互换位置，所以在同一层，有a->b这样的制约关系的需要b在a的下一层里，层内进行全排列后加入答案，实现过程中可以用dfs实现。注意有环的时候没有合法解，...

2023-09-05

1 464

题解 | #牛群跃迁# 贪心

知识点贪心思路我们发现，我们始终存在这一个可以到达的右边界r，因此我们可以维护这个右边界，并且从左到右遍历，一旦当前位置超出了右边界而且还没到末尾，说明不能满足条件，反之可以满足条件。时间复杂度 AC Code（C++） class Solution { public: /** *...

2023-08-16

0 289

题解 | #将单词均匀排列# 字符串模拟

知识点模拟思路样例给的很差，和描述不符同时我认为标程有问题，比如这个测试点["NiuNiu", "Nowcoder", "onto", "JK", "and", "eat", &q...

2023-08-16

0 453

题解 | #牛牛和罗马数字智力游戏# 哈希表

知识点哈希表思路用哈希表记录一下值和罗马数字的关系，因为存在减法的部分，所以我们预先处理好4,9,40这种特例，把它当做另外一种符号。之后我们遍历整个哈希表，从大到小贪心地取值即可。如果长度达到limit则翻转。AC Code (C++) class Solution { public: /...

2023-08-16

0 406

题解 | #农场的奶牛分组II# dp解法

知识点动态规划思路首先我们定义f[i][j][k]为前i个数，能否组成j, k, s - j - k 三个部分。其中s是前i个数的前缀和。这样我们根据当前的数w分在哪一个部分，可以由f[i-1][j-w][k]、f[i-1][j][k-w]、f[i-1][j][k]三部分传递过来。因此假设假设总和为...

2023-08-16

1 351

题解 | #三个牛群中位数# 分治解法

知识点递归分治思路这道题算上一题的强化版，三个有序数组，一个长度为n，一个长度为m，一个长度为p，找到三个数组归并后的中位数。根据中位数的定义，假如是奇数，那么需要找到第小的数作为答案；假如是偶数，那么需要找到第小的数和小的数的平均数作为中位数。因此我们需要实现一个函数find可以在log时间内...

2023-08-16

0 426

题解 | #牛群买卖策略优化# 贪心

知识点贪心思路由于每天都可以进行交易，我们可以只要第二天比第一天的段，而舍弃下降的段。因此只需要枚举相邻的两段，当第二天大于第一天，则可以更新答案。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指...

2023-08-16

0 313