首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
一只羊蝎子
获赞
113
粉丝
6
关注
8
看过 TA
3
男
哈尔滨理工大学
2024
Java
IP属地:浙江
一只羊蝎子!
私信
关注
拉黑
举报
举报
确定要拉黑一只羊蝎子吗?
发布(31)
刷题
一只羊蝎子
2021-02-17 11:36
哈尔滨理工大学 计算机类
NC50528 滑动窗口
题意 给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,找出窗口中的最大值和最小值,然后将窗口往后移动一位。 思路 找最大值和找最小值是一样的方法,这里以找最大值为例。每次窗口向右移动时,如果进来了一个比上一个值要大的数,则上一个值从此以后绝不可能成为窗口中的最大值,也就是说,当窗口的右端点从移动到时,如果,那么再也不可能是窗口中的最大值。同时,因为窗口的移动,窗口左端点上的数会离开窗口,不再被我们考虑。 这样,我们可以考虑使用双向队列,每次移动窗口时从后往前删除不再可能成为最大值的数,并且判断最前面的数是否已经离开窗口。为了判断最前面的数是否已经离开窗口...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-16 21:26
已编辑
哈尔滨理工大学 计算机类
NC16430 蚯蚓
题意 表示对向下取整第0秒,你有只蚯蚓,第只蚯蚓的长度为(长度均为非负整数,可以为0)。每过一秒找出最长的蚯蚓切成两条长度为和的蚯蚓,为0到1之间的有理数,同时其余的所有蚯蚓长度增加(非负整常数)。问秒内每一秒被切断的蚯蚓被切断前的长度和秒后所有蚯蚓的长度 思路 每秒都要找最长的蚯蚓切成两条,因为新增了蚯蚓,所以我们直接对数组进行这样的操作会浪费大量的时间在排序和插入上,这时候可以这么想:一条长度为的蚯蚓,切了以后变成长度为和的蚯蚓,因为是常数,所以很明显,和中有一个较大的值和一个较小的值(当然也可能一样大),并且和关于单调递增 所以我们可以用队列来处理蚯蚓的长度:第一个队列,从大到小记录原有...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-07 19:42
已编辑
哈尔滨理工大学 计算机类
NC14301 K-th Number
题意 在长度为的数组A中,找出所有子区间中第大的数放入数组B,求数组B中第大的数 思路 一看这题,对于放入数组B的数有明确的规定,那很显然我们能简单的模拟来实现这个目的,但是这么干的话运算量绝对是爆炸多的,所以我们可以考虑二分+检验来找出解 二分这个步骤很简单就不说了,难点在检验 我们记数组B中第大的数为,那么数组B中大于的数加上它自身就一共有个。这个数,对应了数组A中个子区间里第大的数。、也就是说,数组A中,区间里第大的数大于等于的区间有个。 那么我们在检验的时候只需要判断区间里第大的数大于等于的区间的个数与的大小关系即可。如果前者大于后者,说明我们下次二分可以把取更大进行判断,反之取小。...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-07 10:23
哈尔滨理工大学 计算机类
NC16564 借教室
题意 有天借教室信息,其中第天学校可以借出个教室。有份订单,每份订单由组成,表示租借者需要从第天到第天(闭区间)内每天向学校借个教室只需要考虑每天教室的数量能否满足当天订单,按照订单先后顺序借出教室,找到第一个无法被完成的订单(第天到第天至少有一天学校可借出教室数量少于则订单无法被完成) 思路 感觉说的不是很清楚,建议配合下方代码食用 判断一个订单能否被完成很简单:只需要判断从第天到第天学校每天需要向外借出的教室数量是否大于实际可向外借出的教室数量即可。 所以我们有一个最基本的枚举思路:按照先来后到的原则,我们从第一个订单开始枚举,判断学校剩下的可用教室数量能否满足当前订单即可,遇到第一个不能...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-06 22:51
已编辑
哈尔滨理工大学 计算机类
NC19916 CQOI2021 扑克牌
题意 你有种牌,第种牌的数量为,除此之外还有一种特殊的牌,他的数量为。你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌,请问最多能组成多少套牌 思路 看到这个题目我有一种俄罗斯方块的感觉,用joker或者原本的格子把一行填满,就组成了一套牌。但它有一条特殊的规则:一套牌中,joker最多只能代替一种牌出现例如:虽然有999张joker足以填满所有格子,但因为一套牌中,joker最多只能代替一种牌出现,这里最多只能组成套牌 那么如何正确的计算套牌的数量呢?我们仍可以按这个思路走(其实差的有点远) 我们从最下面的行开始,往每一行里继续塞格子(也就是...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-06 20:59
哈尔滨理工大学 计算机类
NC107382 POJ2785 4 Values whose Sum is 0
题意 给定n行4列的整数,从每一列各选择一个数加起来等于0的组合有多少种? 思路 这题很容易让人想到枚举,要让四个数字的和等于0,从前三列选择了三个数以后第四列要找的数就是确定的,可以不断地枚举找到答案,但这样时间复杂度为,这可不是我们负担的起的。所以在枚举的基础上可以加入二分,确定了前三列的数字以后,对第四列进行排序,之后再从第四列种二分查找判断有多少个我们要找的数即可。 但即使是这样,我们对四列数据的枚举仍会带来大量重复的计算,所以我们可以对第一、二列的数据两两求和,形成一个新的数组,对第三、四列进行一样的操作,这样我们就只剩下两个数组,每个数组的长度为。之后再对第二个数组排序,然后对第一...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-06 20:07
哈尔滨理工大学 计算机类
NC107701 POJ3104 Drying
题意 Jane有件带水没干衣服,每件带单位的水,自然状态下每分钟每件衣服会干掉一单位的水,为了让衣服更快的干掉,Jane决定使用吹风机吹衣服。Jane每分钟都可以选择其中一件衣服对其使用吹风机,在吹风机和自然环境的共同作用下,一件衣服每分钟可以干掉单位的水,问让衣服全部干掉最少需要多少分钟。 思路 二分+检验 对于这件衣服,我们记不用吹风机的情况下自然干需要分钟,很容易想到我们可以直接从到枚举,判断每种情况能否让衣服全部干掉。但是这样太耗费时间,所以我们可以做个优化,对干衣服的时间做一个二分查找,直到刚好能让全部衣服干掉为止。 如何判断能否在分钟内让衣服全部干掉? 首先,在自然环境的作用下,分...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-01 21:06
哈尔滨理工大学 计算机类
2021牛客寒假算法基础集训营1 | 括号
题意 构造一个非空括号字符串,要求正好包含k个合法括号对且字符串长度不能超过十万 * 思路 看到这个k的数据范围和字符串长度要求,我们知道不能一个劲怼括号,否则会超出长度限制 那么我们先来思考一个问题:一个长度为n的字符串,如何出现最多的括号对?(为了方便描述,我假定n为偶数)答案是把字符串一分为二,左边全是左括号,右边全是右括号,这样我们就得到了个括号对。 把上面这个过程反过来,我们需要正好个合法括号对,那么我们先令,字符串左边放入个左括号,右边放入个右括号,那么我们就得到了个括号对。因为是向下取整的,所以我们可能会漏掉一些括号对,这时候需要把漏掉的括号对补上。 我们需要补上个括号对,...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-01 20:08
哈尔滨理工大学 计算机类
NC207028 第k小数
思路 求第k小的数,第一时间就能想到和排序有关,但这个数据量用冒泡排序什么的肯定会很糟糕,所以用到了快速排序 在快速排序时,我们先选取一个基准值,然后把数组中所有比基准值小的数放到基准值左边,比基准值大的数放到基准值右边,等于基准值的数任意放在哪一边。每一次完成这样的操作以后,我们根据k和基准值的大小关系,选取左区间或右区间递归,直到区间里只剩一个数,那就是我们要的第k小数 代码 #include <iostream> using namespace std; int num[5000005]; inline int read() { int x = 0, f = 1;...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-02-01 10:33
哈尔滨理工大学 计算机类
第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 | Seek the Joker I
题意 威佐夫博弈_百度百科传送门每次芳乃先抽,在双方都做出最佳决策的情况下判断谁必胜 思路 拿到最后一张牌的人就输了,所以为了获胜,我们必须拿走倒数第二张牌。拿走倒数第二张牌以后,整个牌堆剩余(n-1)张牌。 每次每人只能抽取1~k张牌,所以先手抽完以后后手可以保证该回合抽的牌数为1+k(先手拿1张则后手拿k张,确保1+k)。既然后手可以保证拿1+k张牌,那我们只需判断(n-1)是否能被k+1整除即可,如果能被k+1整除,说明后手拿走了倒数第二张牌,后手必胜 代码 #include <iostream> using namespace std; int main() { ...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-01-31 17:24
已编辑
哈尔滨理工大学 计算机类
第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 | 小宝的幸运数组
题目 思路 其实我也不会,单纯解读一下别人的代码题目要求幸运子数组中所有数的和能被k整除由小学二年级数学知识我们知道: 所以我们只需要计算数组和的前缀和,然后把前缀和求余k,再看看何时出现了一样的余数或者被k整除即可 为了判断何时出现了一样的余数,我们声明一个数组pos来记录这个余数第一次出现的位置,-1表示未出现过,并且让pos[0]=0(被k整除的情况)。这样每次把数组和求余k以后判断pos是否为-1,如果是-1就记录余数第一次出现的位置,如果不是-1,则直接拿当前数的位置减去pos的位置,看看长度是否为最大即可 代码 #include <iostream> #incl...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-01-31 09:56
已编辑
哈尔滨理工大学 计算机类
第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 | 买花
题意 在15天内买完n朵花,且不能一天买完,第一天买的数量任意,之后每一天买花的数量为前一天的两倍如果能刚好买到n朵花,输出YE5(注意不是YES),否则输出N0(注意不是NO) 思路 假设第一天买了a朵花,那么第二天只能买2a朵,第三天只能买4a朵。观察到,总共买的花的数量永远是奇数倍的a,即总共买的花的数量能被某个奇数整除,且奇数满足一定的规律((1 << day) - 1,即在二进制上每一位都是1)。因为阳阳必须在15天内买完他要的花,所以那个奇数最大只能是32767,我们只需要枚举其中的每个奇数,看看能不能被整除即可。整除得到的商就是第一天买的花的数量 代码 #inclu...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-01-30 23:14
哈尔滨理工大学 计算机类
第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 | 上进的凡凡
题目 思路 签到题看看就好,反正难的题咱也不会 对于凡凡来说,只有非降序的数组才是nice的,如果数组长度为1,也是nice的 难么我们只需要统计这个数组中的每一段非降序数组的长度即可 统计了每一段的长度以后,由小学二年级知识我们知道长度为n的数组有 个子数组,再根据这个公式求出答案即可 代码 #include <iostream> using namespace std; int main() { int last = 0; int temp; int n; long long res = 0; long long count = ...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-01-30 22:42
哈尔滨理工大学 计算机类
NC14731 逆序对
题意 在长度为n的01串中,若第i位=1,第j位=0,i<j,则成这是一对逆序对,求所有的长度为n的01串中一共能出现多少逆序对 思路一 枚举逆序对出现位置的方案 以 为例,逆序对可能的存在方案有: 、 、 三种方案( ),每种方案中含一个 代表未知数字,这个未知数字又只能是0或1,所以共有 个逆序对 可能存在的疑惑只有我这种菜鸡会有这样的疑惑吧可能会想,在 、两个逆序对存在方案种,会存在某01串同时满足两种方案,比如这里的 ,这样计算会不会把一个逆序对计算两边呢? 其实 中的第一个1和0、第二个1和0各自是一个逆序对,分别对应了那两种逆序对存在方案,也就是说,一个逆序对存在方案只记录...
0
点赞
评论
收藏
转发
一只羊蝎子
2021-01-29 17:01
哈尔滨理工大学 计算机类
NC204383 中序序列
题意 给了一颗树的前序序列和后序序列,求中序序列如果某节点只有一个子节点,将其视为左节点 思路 为了按照中序序列“左、根、右”的顺序输出序列,我们需要用到递归,先递归左树、输出根、再递归右树。 以题目给出的示例一的树为例:由于给了前序序列,所以我们知道3是根节点,3后边的2是他左子树的根节点知道了左子树的根节点,题目又给了后序序列,所以我们可以去后序序列中找到那个左子树的根,再根据后序序列“左、右、根”的顺序确定左子树节点的个数和右子树节点的个数 知道了左右子树的长度就可以确定他们在前序序列和后序序列的区间,接下来只要以左树和右树为参数,分别递归调用自身,一直到区间里只剩一个节点(节点没有子节...
0
点赞
评论
收藏
转发
1
2
3
工具箱
TA的圈子
暂未加入圈子
TA的圈子
TA的笔记
暂无笔记
TA的笔记
登录
0
天
已登录
0
天
连续登录
0
人
今日访客
牛客网
牛客企业服务