retyrn - 个人主页动态 - 牛客网

发布(206) 刷题

05-26 21:39

浙江大学化工与制药类

题解 | #小苯的排列构造# 牛客周赛 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], 我们考虑将1到4和它们匹配, 即: i p[i] 7 1 8 2 9 3 10 4 如上述即为满足条件的构造 如果n为奇数, 则前一部分构造方式不变, 最后4个可以倒过来, 例如当n=11时 i p[i] 8 4 9 3 10 2 11 1 ...

0 点赞评论收藏

转发

05-26 21:42

已编辑

浙江大学化工与制药类

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

D 因子区间 首先，1e5之内的数最多拥有128个因子，所以可以从 1 ~ 128 枚举因子个数，分别计算。 对于每个因子数记录下来该因子数对应的原数组中每个数的下标，二分找到范围内的个数后利用组合数进行计算。时间复杂度 在这之前，可以 预处理1e5内每个数的因子个数. int n, q; void solve() { cin >> n >> q; vector<int> f(maxn, 0); // f[i] 数i的因子数 for (int i = 1; i <= 100000; i ++) { for (...

0 点赞评论收藏

转发

2023-09-05 10:18

浙江大学化工与制药类

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

知识点拓扑排序 dfs 全排列解题思路首先很明显要进行拓扑排序来确定拓扑关系以及检查是否有环。在拓扑排序过程中，没有相互制约关系的两个元素可以互换位置，所以在同一层，有a->b这样的制约关系的需要b在a的下一层里，层内进行全排列后加入答案，实现过程中可以用dfs实现。注意有环的时候没有合法解，返回空即可。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numFruits int整型 * @...

0 点赞评论收藏

转发

2023-08-16 09:28

浙江大学化工与制药类

题解 | #牛群跃迁# 贪心

知识点贪心思路我们发现，我们始终存在这一个可以到达的右边界r，因此我们可以维护这个右边界，并且从左到右遍历，一旦当前位置超出了右边界而且还没到末尾，说明不能满足条件，反之可以满足条件。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return bool布尔型 */ bool can_jump(vector<int&gt...

0 点赞评论收藏

转发

2023-08-16 09:28

浙江大学化工与制药类

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

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

0 点赞评论收藏

转发

2023-08-16 09:27

浙江大学化工与制药类

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

知识点哈希表思路用哈希表记录一下值和罗马数字的关系，因为存在减法的部分，所以我们预先处理好4,9,40这种特例，把它当做另外一种符号。之后我们遍历整个哈希表，从大到小贪心地取值即可。如果长度达到limit则翻转。AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型 * @param limit int整型 * @return string字符串 */ ...

0 点赞评论收藏

转发

2023-08-16 09:27

浙江大学化工与制药类

题解 | #农场的奶牛分组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]三部分传递过来。因此假设假设总和为m，时间复杂度为其中空间可以优化掉第一维。空间复杂度为n是200，每个数最大为100，因此总和，空间开级别也在左右，由于vector<bool>的每一位是1个bit，所以空间是正常的八分之一，空间不会超过6MB但是考虑计算时间约在 妥妥超时，但是没想到更好的办法。但是肯定比回溯的时间复杂...

0 点赞评论收藏

转发

2023-08-16 09:27

浙江大学化工与制药类

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

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

0 点赞评论收藏

转发

2023-08-16 09:27

浙江大学化工与制药类

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

知识点贪心思路由于每天都可以进行交易，我们可以只要第二天比第一天的段，而舍弃下降的段。因此只需要枚举相邻的两段，当第二天大于第一天，则可以更新答案。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ int max_profitv2(vector<int>& prices) ...

0 点赞评论收藏

转发

2023-08-16 09:27

浙江大学化工与制药类

题解 | #牛群的编码II# 模拟大整数减法

知识点模拟 大整数减法思路大整数减法板子题，我们可以从后往前模拟减法的“相减 借位”的过程，时间复杂度为题面说除了0以外无前导零，结果测试点还有前导零的情况。AC Code（C++） #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a string字符串 * @param b string字符串 * @return string字符串 */ ...

0 点赞评论收藏

转发

2023-08-16 09:26

浙江大学化工与制药类

题解 | #牛的回文编号III# 位运算双指针

知识点位运算 双指针思路我们维护一对反向双指针，每次左指针右移、右指针左移，如果出现不相等则不为回文串，反之则为回文串。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param x int整型 * @return bool布尔型 */ bool isPalindromeNumberIII(int x) { for (int i = 0, j = 31; i < j;...

0 点赞评论收藏

转发

2023-08-15 13:06

浙江大学化工与制药类

题解 | #找到满足条件的牛群组合# 双指针

知识点双指针思路首先排序，枚举第一个元素，用双指针来得到第二个和第三个元素。实现上如果当前元素和上一个元素相等的话可以跳过，因为当前的所有情况已经在上一个元素处枚举过了。时间复杂度 AC Code（c++） #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型...

0 点赞评论收藏

转发

2023-08-15 13:05

浙江大学化工与制药类

题解 | #牛群买卖计划II# 状态机DP

知识点状态机DP思路定义 f[i][j][st] 前i天完成j笔交易，手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态，就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @param k int整型 * @return int整型 */ ...

0 点赞评论收藏

转发

2023-08-15 13:04

浙江大学化工与制药类

题解 | #牛群买卖计划# 状态机DP

知识点状态机DP思路定义 f[i][j][st] 前i天完成j笔交易，手上股票持有状态为st 的价值最大值。状态转移可以分为当前股票保持或者卖出两种状态，就可以进行转移。答案为前n天手上持有状态为0的最大值。时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ const int INF = 0x3...

0 点赞评论收藏

转发

2023-08-15 11:34

浙江大学化工与制药类

题解 | #牛群买卖计划III# 贪心

知识点贪心思路由于可以在某一天卖出之前的所有牛，为了利益最大化，我们需要在价格最高的那天卖出之前的购入的所有牛，在价格次之的一天卖出之前的所有牛（排除之前已经卖出的）……因此我们可以对价格从高到低排序，每次从卖出日向前枚举找到没有卖出的一段卖出，累计答案。时间复杂度 AC Code (C++) #include <numeric> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector ...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务