偶尔刷刷题
偶尔刷刷题
全部文章
分类
题解(32)
归档
标签
去牛客网
登录
/
注册
OI博客
学习、做题、总结、发题解
全部文章
(共32篇)
牛客NOIP暑期七天营-普及组6-D-Bunny的聚会
题目大意:数轴上有n个点,在总代价不超过m的情况下,至多可以将多少个点移到一起?(代价:每个点移动的距离) 数据范围500万,递增输入,不需要排序,显然需要用O(n)做法才能满分,而且读入还可能被卡。 能走到一起的,必然是连续的若干个点:如果一个区间中有个点没有移动过去,那么终点要么在他左边,要么在...
区间平移
分配律
单调性
区间和
单调递增
数学
前缀和
2019-08-25
2
968
牛客NOIP暑期七天营-普及组6-C-Bunny的修路工程
题目大意:n个点n-1条边的一棵树,有m个点是超市;现在每个点到超市的最短距离都不超过D,至多删除多少条边,还能够保证每个点到超市的最短距离都不超过D? 预处理:超市点的数量是x,非超市点是y,x+y = n。 1、对于不是超市的点,都需要1条边来连向超市,所以至少需要y条边,至多删除n-1 - y...
方案无关
贪心
分类讨论
思维
证明
2019-08-25
4
1008
牛客NOIP暑期七天营-普及组6-B-Bunny的任务
题目大意:n个任务,给你t的时间,最多做多少个? 选出来的任务时间之后不超过t即可。 假设答案是k个任务,如果其他任务的时间更小,换一个时间更短的任务进来,不影响答案,且花时间只会更少、更好! 因此,我们可以选最短时间的k个任务。 排序,贪心选择即可。 注意:累加可能爆long long,用减法代替...
排序
细节
贪心
2019-08-25
3
873
牛客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++){ ...
模拟
数学
2019-08-25
1
892
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…...
矩阵快速幂
扩展欧几里得
解方程
数学
思维
逆元
斐波拉契数列
2019-08-24
2
973
牛客NOIP暑期七天营-普及组5-C所以,然后是几点呢
题目大意:输入前一个时间和经过的分数数,输出当前时间。 s数组解释:将下列字符串转成一行,反斜杠转义,每行长度42,那么0就是0-2、42-45、84-86,其他字符以此类推。 ._....._.._....._.._.._.._.._......__..... |.|..|._|._||_||_....
细节
模拟
字符串
分类讨论
思维
2019-08-24
0
876
牛客NOIP暑期七天营-普及组5-B小混沌的RYB树
题目大意:一棵树,相邻两点不能同色,现有红黄蓝以及各点涂各种颜色的价值,请问涂色后最大价值是多少? f[i][j]表示结点i涂颜色j子树的最大价值。如果i点图j色,那么儿子结点只能图另外2中颜色,取最大值即可。 最终答案是f[1][0]、f[1][1]、f[1][2]里面找。 #include &l...
树
记忆化搜索
枚举
树形DP
2019-08-24
5
901
牛客NOIP暑期七天营-普及组5-A手术等级
题目大意:一个从1开始编号的数组的不完美度为,现在可以将数组分成两个从1开始编号的数组,请问分成的两个数组的不完美度之和最小是多少? 将一个数组分成两半,左半边的不完美度的没有任何变化的。 右半部分,假设是从i开始,区间是[i, n]:第i个元素由a[i]i变成了a[i]*1,第i+1个元素由a[i...
模拟
查找
枚举
数学
前缀和
2019-08-24
0
874
牛客OI周赛11-普及组-D凸包的交
题目大意:根据指定规则生成序列a,在所有长度不小于L的区间中,平均值最大是多少? 1、递推计算序列:根据题目公式计算即可。 2、预处理前缀和:区间平均值,用到区间和,区间和可以通过前缀和O(1)算出来。 3、平均值即斜率:区间i+1到j的平均值是(s[j]-s[i]) / (j-i),可以使用斜率优...
区间
斜率优化
数形结合
斜率
递推
思维
前缀和
2019-08-23
0
879
牛客OI周赛11-普及组-C-Colorful
题目大意:n个点,m条边,每条边有颜色,生成一棵树,要求边的颜色数最少,输出最小值。 边多、点少,稠密图,但不能直接去重边,因为颜色是很重要的。因为颜色数量不超过12,那就用二进制存储颜色,输出的结果也是1到12之间! 用邻接矩阵存储边,暴力枚举每种颜色是否选,时间复杂度,接着搜索判断是否连通。因为...
生成树
洪水填充
时间复杂度
爆搜
邻接矩阵
搜索
fill
稠密图
flood
二进制
2019-08-23
2
768
首页
上一页
1
2
3
4
下一页
末页