首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
平凡的小白
获赞
487
粉丝
18
关注
14
看过 TA
37
男
咖喱炖小学
2023
行政专员/助理
IP属地:江西
虽然中奖机会小,还是再想中一次
私信
关注
拉黑
举报
举报
确定要拉黑平凡的小白吗?
发布(113)
评论
刷题
平凡的小白
关注TA,不错过内容更新
关注
2020-05-05 11:53
已编辑
咖喱炖小学 行政专员/助理
【每日一题】Removeal
戳我传送 题意: 题目描述:Bobo有整数s1,s2,...,sn,其中1 ≤ si ≤ k。删除m个后问有多少种序列,然后对(1e9 + 7)取模。 输入描述: 输入包含多个测试用例,并以文件结尾终止。 每个测试用例的第一行包含三个整数n,m和k。 第二行包含n个整数s1,s2,...,sn。输出描述: 对于每个测试用例,请打印一个表示结果的整数。 思路: 计数类dp。 表示前i个数字删掉j个元素的序列数。如果不考虑重复,状态转移方程就是 , 表示取第i个数, 表示不取第i个数。看数据就知道大部分案例一定会有很多重复的数字,接下来考虑重复的情况:……1,4,7,8,5,11.这一段删除...
每日一题
0
点赞
评论
收藏
分享
2020-05-04 22:06
已编辑
咖喱炖小学 行政专员/助理
【每日一题】合并回文子串
戳我传送题意:思路:区间dp, 表示a串的第i个字符到第j个个字符和b串第k个字符到第l个字符组成的串能否构成回文串,求法通过分解代码的形式分析,因为这个思路对我来说有点难。 for(int len1=0;len1<=n;++len1) for(int len2=0;len2<=m;++len2) for(int i=1;i+len1-1<=n;++i) for(int k=1;k+len2-1<=m;++k) 这里是枚举区间长度和起点,然后根据区间长度和起点可以退出终点,len1<=n很好理解,因为终点j=i+len1-1不能大于n,所以i+len1-1<...
每日一题
0
点赞
评论
收藏
分享
2020-05-04 16:16
已编辑
咖喱炖小学 行政专员/助理
【每日一题】换个角度思考
戳我传送题意:思路:离线+值域树状数组,保存每个点和每次询问的编号,每个点按照值的大小升序排序,每次询问按照k值大小升序排序。原理:1.处理k1的答案时(k最小的询问),树状数组中小于k1的位置都会被1标记,k1的答案就是树状数组 [l,r] 中1的个数。2.处理k2时(k2>=k1),之前被1标记的位置的数都是小于等于k2的,不需要从头标记,只要继续找还有没有小于等于k2的数,标记它的位置就可以了。3.后面每次询问重复1、2步骤,最多只要标记n个点。4.每个点升序排序方便找小于等于k的数。5.复杂度 。Code: #include <iostream> #include &...
每日一题
0
点赞
评论
收藏
分享
2020-05-04 13:11
咖喱炖小学 行政专员/助理
【每日一题】Rinne Loves Edges
戳我传送题意:这个题意是关键,首先n个点n-1条无向边边,接触过树的同学应该都知道这是一颗树,而度就是与这个点相连的边的数量,度为1就是叶子结点了,现在问题就变成了:在以S为根的树上删掉权值之和尽量小的一些边使得根和每一个叶子节点都不连通。思路:这是一个典型的树型dp,而树型dp本质上可以说是个搜索——遍历这棵树,在返回的时候维护相关的值。不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的,我们要分析的大问题就是使s和所有的叶子都不联通的最小代价是多少,小问题就是s的儿子和子树上的叶子都不联通的最小代价是多少。因为s可以选择断掉和儿子的边,或者让儿子与子树的叶子结点不连通,所以转移...
每日一题
0
点赞
评论
收藏
分享
2020-05-03 23:33
咖喱炖小学 行政专员/助理
【每日一题】城市网络
戳我传送题意:给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询(此时v是u的父亲),问你从u->v的最长上升子序列长度。思路:倍增+dfs题目表明v一定在u去网1的最短路径上,如果从u一直往上走到v,再去判断到达的每一个城市,需不需要购买。这种算法的极端情况,形成了一条长为n的链,时间复杂度达到了O(nq),后面数据加强就会超时了。正确的做法是用倍增,f[i][k]表示i结点的第 个比i大的父亲的位置(是那个结点),这个理解清楚看代码得看半天。不难得出状态转移方程f[i][k]=f[...
每日一题
0
点赞
评论
收藏
分享
2020-05-03 09:47
咖喱炖小学 行政专员/助理
【每日一题】tokitsukaze and Soldier
戳我传送题意:在一个游戏中,tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。第i个士兵的战力为v[i],团的战力是团内所有士兵的战力之和。但是这些士兵有特殊的要求:如果选了第i个士兵,这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵,就没有这个限制。)tokitsukaze想知道,团的战力最大为多少。前备知识:手写小根堆的实现: int heap[N],sz=0; void push(int x){ int i=sz++; while(i>0){ int p=(i-1)/2; if(heap[p]<=x)...
每日一题
0
点赞
评论
收藏
分享
2020-05-03 00:25
咖喱炖小学 行政专员/助理
【每日一题】3月27日数学考试
戳我传送 题意: 思路 求两个不连续的区间的最大和,很容易想到前缀和,[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点,另一个指针枚举右区间的起点,两层循环复杂度 (n^2),应该会超时。枚举右区间的起点时,可以发现左区间的起点不需要从1开始找,此时的最优解一定是左区间最大,而此时右区间左边全部的左区间已经出现过了,只要一直保存最大的左区间起点,在枚举右区间的起点时就可以 (1)的找到最优左区间起点。总复杂度 (n)。 Code; #include<bits/stdc++.h> #define ll long long using...
每日一题
0
点赞
评论
收藏
分享
2020-05-02 22:56
已编辑
咖喱炖小学 行政专员/助理
【每日一题】3月30日滑动窗口
戳我传送 题意: 给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,每次窗体向右移动一位,你的任务是找出窗体在各个位置时的最大值和最小值。思路:就和邓老师说的那样,每次滑动一个区间,区间从[l,r]到[l+1,r+1],只是增加了a[r+1]减少了a[l],所以完全没有必要重新扫一遍区间。以最大值为例:1.将新进入区间的这个元素往双端队列里放,但放进来之前需要判断队尾(也就是还有可能成为最大值的最后一个元素)是不是小于他小于他,如果是,就把这个队尾删掉(r- -),一直到前一个元素大于等于它为止。这样得出来的队列实际是单调递减的。2.可以输出时先判断队...
每日一题
0
点赞
评论
收藏
分享
2020-05-02 18:24
已编辑
咖喱炖小学 行政专员/助理
【牛客练习赛62】
A、牛妹的游戏 题目描述: 在二维空间上有若干个点,有两队(蓝方和绿方),每队都可以占边。而当有其中一队占的边有可能有三条首尾相连就输出"yes",否则输出"no"。思路:1.拉姆塞结论--点数超过5的图或者对应补图必有度数为3的环.不会证明(只会举例子)2.由1知当n大于5时输出“yes”,只要判断n<=5的情况,数据较小,可以直接爆搜,任取三条边判断是否成环。3.成环的依据就是如果三条边都别蓝方占领,那么就会形成蓝色三角形,如果都没被蓝方占领,那么就有可能被绿方占领,形成绿边。Code: #include<bits/stdc++.h&...
0
点赞
评论
收藏
分享
2020-05-29 09:31
已编辑
咖喱炖小学 行政专员/助理
牛客算法周周练4
闲话A、B看了这位大佬的博客看懂的 传送门,B题我想化简,结果出了问题求助这位大佬,然后同学发现我多算了一个 ,大佬也很快发现了,我自己找了半天,QAQ。戳我传送 [SDOI2016]齿轮 题意: n个齿轮m条链,链上两点u、v的转述比为x:y,若不同链条的传动比不相容,则有些齿轮无法转动,就输出no,反之yes。思路: 若不同链条的传动比不相容,则有些齿轮无法转动,意思是确定一个点后沿着链,根据题目输入的转速比确定其它点,当形成环时,会再次推到起点,若有矛盾就是不相容。真的题意后,就会想到以前的每日一题边的染色 (我的博客)和它的思路非常相似。1.链式向前星存图。2.对于任一连通块,...
0
点赞
评论
收藏
分享
2020-04-28 15:00
咖喱炖小学 行政专员/助理
【每日一题】边的染色
戳我传送 思路: 1.链式向前星存图后,dfs跑一遍判读是否自身矛盾。2.dfs再跑一遍,对每个联通块的元素个数sum-1求和k。3.dfs再跑一遍,对每个涂了颜色的边组成的连通块的元素个数sum-1求和,再用k减去总和,ans=2^k。 原理 1.边的值可以看作两个端点的异或值。2.对每个涂了颜色的边组成的连通块,假设一个点为1,其余的点的值也随之确定了。比如1-3边的值为1,3-2边的值为0,如果给1取1,那么可以得到3=0,2=0。(这个联通快如果不是环,就不会自身矛盾,如果是环才有可能自身矛盾)如果又涂回到了起点(即这个连通块是圆),如果颜色和原来的一致就不矛盾,如果此时应该涂...
每日一题
0
点赞
评论
收藏
分享
2020-04-23 17:34
已编辑
咖喱炖小学 行政专员/助理
【每日一题】子序列
戳我传送 思路: 传送门看这位大佬的题解看懂了,太秀了。子序列首先我们会想到动态规划,状态dp[i]表示以a[i]结尾符合条件的子序列个数。状态转移方程不难写出是dp[i]=1+ 。建议仔细看清楚a的上下标,a[i]的上标是j,a[i]的下标是i,如果像我一样没看清楚的话,真不知道题目在说什么。接着是判断 是不是成立,比较常用的是做差法和做商法,当遇到最差的情况100^100显然做差法是不现实的,会直接溢出,取余也不行,可以考虑做商法,K= ,(假设 ),如果如果y>=x, 一定不成立,接着就是考虑y<x的时候,y/x<1可以先求出y/x的幂然后乘y到K>1结束,...
每日一题
0
点赞
评论
收藏
分享
2020-09-03 18:37
已编辑
咖喱炖小学 行政专员/助理
【每日一题】K-th Number
中文题意这个大佬博客有翻译 戳我。 思路: 如果遍历每一个大于等于k的区间找第k大的数,复杂度不敢想, (n^2)级别。所以这时候就要用到尺取法了,专栏的办法太秀了。其实我们不在乎第m大的数以外是什么,只要知道第m大的数是什么,所以我们可以二分答案把求值变成验证,再用尺取法找到符合要求的区间数。原理:1.居然是找B中第m大的数,那么B中有至少有m个数且至少有m个数大于等于第m大的数。2.(m个数大于等于第m大的数),这m个数都是A中区间第k大数,也就是第K大数大于B中第m大的数的区间至少有m个。3.第k大的数大于B中第m大的数的区间,说明区间至少有k个数大于等于k,找到一个符合要求的区间,...
每日一题
0
点赞
评论
收藏
分享
2020-04-22 20:07
已编辑
咖喱炖小学 行政专员/助理
牛客算法周周练3
戳我传送 A、 题意:Nancy往六个方向走,会吃掉'.',遇到'*'就返回,问他能吃到多少糖果,他想少吃表明到了终点后就不会在找了,三维迷宫。 思路: 明显的BFS,题目描述的很明确了,开个结构体记录当前坐标以及吃的果冻数量,再用队列去BFS模拟一遍。刚开始没懂题意用了DFS,又超时又wa。 Code: #include <bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; int read(){ int x=0;char...
0
点赞
评论
收藏
分享
2020-05-29 09:12
已编辑
咖喱炖小学 行政专员/助理
糖糖别胡说,我真的不是签到题目
戳我传送题意:n个糖糖排成一排,每个糖糖有一个能力值,第i秒第i个糖糖就会杀死前面能力比他小的人,进行m次区间加的操作,每次输入ci,表示第ci秒1~ci的糖糖能力值加一,输出最后有多少糖糖存活。 思路: 前m次操作可以用前缀和模拟区间加,得到每个糖糖的新能力值后从后往前维护每个队伍的最大值,当前糖糖的能力值如果大于后面敌对队伍糖糖的最大值,也就是比后面的糖糖都强,那么他存活,反之白给。复杂度 (n)。如果从前往后判断第i糖糖能不能存活,还要搜索后面i-1个糖糖,复杂度 (n^2)。刚开始没看懂题目看大佬博客,整了一个后缀和,一下愣是没看懂,看了2个多小时才看懂,你信?,大佬还提到扩展到n个队...
每日一题
0
点赞
评论
收藏
分享
1
3
4
5
6
7
8
关注他的用户也关注了:
牛客网
牛客企业服务