首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
偶尔刷刷题
获赞
68
粉丝
17
关注
0
看过 TA
2
保密
2008
算法工程师
IP属地:广东
暂未填写个人简介
私信
关注
拉黑
举报
举报
确定要拉黑偶尔刷刷题吗?
发布(37)
评论
刷题
偶尔刷刷题
关注TA,不错过内容更新
关注
2019-08-25 17:17
保密 算法工程师
2019-08-25
在牛客打卡7天,今天也很努力鸭!
0
点赞
评论
收藏
分享
2019-08-25 12:19
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组6-D-Bunny的聚会
题目大意:数轴上有n个点,在总代价不超过m的情况下,至多可以将多少个点移到一起?(代价:每个点移动的距离) 数据范围500万,递增输入,不需要排序,显然需要用O(n)做法才能满分,而且读入还可能被卡。 能走到一起的,必然是连续的若干个点:如果一个区间中有个点没有移动过去,那么终点要么在他左边,要么在他右边;如果在左边,他右边的点移动过去的代价比他大,没必要;另外的方向同理。 区间平移:至少1各点,区间至少为2才判断;从区间[i=1, j=2]开始,如果能移到一起,那么j加1,尝试让更多的点移到一起;如果不能移到一起,那么左端点无论如何都无法跟j以及j右边的点移到一起了,i加1;边界:i跟j相等...
0
点赞
评论
收藏
分享
2019-08-25 12:03
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组6-C-Bunny的修路工程
题目大意:n个点n-1条边的一棵树,有m个点是超市;现在每个点到超市的最短距离都不超过D,至多删除多少条边,还能够保证每个点到超市的最短距离都不超过D? 预处理:超市点的数量是x,非超市点是y,x+y = n。 1、对于不是超市的点,都需要1条边来连向超市,所以至少需要y条边,至多删除n-1 - y条边。 2、要想删边后每个点到超市的距离不超过D,可以用y条边就够了。超市不需要用边;非超市点,必有一条路连向超市,选距离最短的。不需要管怎么找到这条路,因为我们只需要知道是否可行就够。 #include <bits/stdc++.h> #define N 1000005 using n...
0
点赞
评论
收藏
分享
2019-08-25 12:03
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组6-B-Bunny的任务
题目大意:n个任务,给你t的时间,最多做多少个? 选出来的任务时间之后不超过t即可。 假设答案是k个任务,如果其他任务的时间更小,换一个时间更短的任务进来,不影响答案,且花时间只会更少、更好! 因此,我们可以选最短时间的k个任务。 排序,贪心选择即可。 注意:累加可能爆long long,用减法代替加法可避免此问题。 #include <bits/stdc++.h> using namespace std; long long n, m, i, j, k, a[1000005]; int main(){ scanf("%lld%lld", &m, &n); ...
0
点赞
评论
收藏
分享
2019-08-25 12:03
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组6-A-Bunny的平均数
题目大意:已知n个数的平均值m以及前n-1个数,请问第n个数是多少? #include <stdio.h> int n, m, i, j, k, s; int main(){ scanf("%d", &n); for(i=1; i<n; i++){ scanf("%d", &k); s += k; } scanf("%d", &m); printf("%lld\n", (long long)m*n-s); return 0; }
0
点赞
评论
收藏
分享
2019-08-25 14:08
已编辑
保密 算法工程师
NOIP暑期七天营-普及组5-D小w的Fibonacci数列
题目大意:从第三项开始,每一项等于前两项之和,已知第x项和第y项的值,输出第1项和第2项。 类似于斐波拉契数列,第一项是a,第二项是b,那么之后每一项都与a和b有关: 从第1项开始,a的数量是:1 0 1 1 2 3 5 8 13……从第1项开始,b的数量是:0 1 1 2 3 5 8 13 21…… 首先算出第x项有xa个a、xb个b,第y项有ya个a,yb个b。(需要用矩阵快速幂) xa * a + xb * b = sx(第x项的值)ya * a + yb * b = sy(第y项的值) 第一个式子乘以ya,第二个式子乘以xa,就可以消去a,算出b了!b = (sy - sx) / (b...
0
点赞
评论
收藏
分享
2019-08-24 16:21
保密 算法工程师
牛客NOIP暑期七天营-普及组5-C所以,然后是几点呢
题目大意:输入前一个时间和经过的分数数,输出当前时间。 s数组解释:将下列字符串转成一行,反斜杠转义,每行长度42,那么0就是0-2、42-45、84-86,其他字符以此类推。 ._....._.._....._.._.._.._.._......__..... |.|..|._|._||_||_.|_...||_||_|./\.|__||\/| |_|..||_.._|..|._||_|..||_|._|/--\|...|..| 1、预处理数字将每个数字的字符放到一个字符串里面,便于以后比较,b[i]存储第i个数据的字符串。(当然,直接跟s串比也行,不太舒服而已) 2、打印数字输出时,每个数...
0
点赞
评论
收藏
分享
2019-08-24 16:32
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组5-B小混沌的RYB树
题目大意:一棵树,相邻两点不能同色,现有红黄蓝以及各点涂各种颜色的价值,请问涂色后最大价值是多少? f[i][j]表示结点i涂颜色j子树的最大价值。如果i点图j色,那么儿子结点只能图另外2中颜色,取最大值即可。 最终答案是f[1][0]、f[1][1]、f[1][2]里面找。 #include <bits/stdc++.h> #define LL long long #define N 100005 using namespace std; LL n, m, i, j, k, a, b, ans; LL h[N], v[N][3], f[N][3], u[N]; struct AB...
0
点赞
评论
收藏
分享
2019-08-25 12:18
已编辑
保密 算法工程师
牛客NOIP暑期七天营-普及组5-A手术等级
题目大意:一个从1开始编号的数组的不完美度为,现在可以将数组分成两个从1开始编号的数组,请问分成的两个数组的不完美度之和最小是多少? 将一个数组分成两半,左半边的不完美度的没有任何变化的。 右半部分,假设是从i开始,区间是[i, n]:第i个元素由a[i]i变成了a[i]*1,第i+1个元素由a[i+1](i+1)变成了a[i+1]2,第j个元素由a[j]*j变成了a[j](j-i+1)……即这个区间多有元素都少加了i-1次! 枚举端口位置i,右边区间之和乘以i-1即可以减去的不完美度。 注意,整个区间加起来,极端情况下是1e51e51e9/2,约5e18,好像没爆long long。 #in...
0
点赞
评论
收藏
分享
2019-08-24 15:55
保密 算法工程师
2019-08-24
在牛客打卡6天,今天也很努力鸭!
0
点赞
评论
收藏
分享
2019-08-25 12:11
已编辑
保密 算法工程师
牛客OI周赛11-普及组-D凸包的交
题目大意:根据指定规则生成序列a,在所有长度不小于L的区间中,平均值最大是多少? 1、递推计算序列:根据题目公式计算即可。 2、预处理前缀和:区间平均值,用到区间和,区间和可以通过前缀和O(1)算出来。 3、平均值即斜率:区间i+1到j的平均值是(s[j]-s[i]) / (j-i),可以使用斜率优化! 平均值最大的区间,必有一个开头和结尾,即用对应的i和j的斜率。 枚举区间右端点,选择最好的左端点:右端点从长度c开始,选择左端点前,把最先的左端点i-c压入单调队列。 如何维护单调队列? 1、相邻3个起点x、y、z,斜率应递增,即xy的斜率应小于yz的斜率。 如果xy斜率大于yz的斜率,那么y...
0
点赞
评论
收藏
分享
2019-08-25 12:12
已编辑
保密 算法工程师
牛客OI周赛11-普及组-C-Colorful
题目大意:n个点,m条边,每条边有颜色,生成一棵树,要求边的颜色数最少,输出最小值。 边多、点少,稠密图,但不能直接去重边,因为颜色是很重要的。因为颜色数量不超过12,那就用二进制存储颜色,输出的结果也是1到12之间! 用邻接矩阵存储边,暴力枚举每种颜色是否选,时间复杂度,接着搜索判断是否连通。因为只需要知道能不能到达,不需要找最短路,搜过不需要再搜,时间复杂度跟Flood Fill是一样的,因为用邻接矩阵,所以是O(n*n)。总时间复杂度是可以接受。 #include <bits/stdc++.h> using namespace std; int t, n, m, s, i, ...
0
点赞
评论
收藏
分享
2019-08-25 12:12
已编辑
保密 算法工程师
牛客OI周赛11-普及组-B-GameWithNumbers
题目大意:判断2到m有多少个数字是合法的。 对于给定的n个数,是合法的;其他数字若是合法,那么必须存在2到n-1的约数,且这些约数都是合法的。 暴力求解:从小到大枚举2到m,如果约数都合法,标记该数字合法;如果遇到一个不合法的约数,则不标记合法。 需要从小到大确定是否合法,保证用到的约数都是更小的、已确定是否合法。时间复杂度: #include <stdio.h> #include <string.h> #define N 300005 int t, n, m, i, j, k, ans, f[N]; int main(){ scanf("%d", &t...
0
点赞
评论
收藏
分享
2019-08-25 12:12
已编辑
保密 算法工程师
牛客OI周赛11-普及组-A多项式
题目大意:给定一个多项式各校的系数和次幂,输出化简后的非零项数目。 排序,将次幂相同的排在一起;合并同类型,次幂相同累加系数,非零则统计。 (次幂非常大,不能用桶排序;需要哈希或者使用map;排序去重统计更方便。) #include <bits/stdc++.h> using namespace std; int n, m, t, i, j, k, ans; struct AB{ int a, b; bool operator < (const AB &A) const{ return a < A.a; } } d[100...
0
点赞
评论
收藏
分享
2019-08-23 09:16
保密 算法工程师
2019-08-23
在牛客打卡5天,今天也很努力鸭!
0
点赞
评论
收藏
分享
1
2
3
关注他的用户也关注了:
牛客网
牛客企业服务