偶尔刷刷题

题解

/ 注册

全部文章 / 题解（共32篇）

牛客NOIP暑期七天营-普及组6-D-Bunny的聚会

题目大意：数轴上有n个点，在总代价不超过m的情况下，至多可以将多少个点移到一起？（代价：每个点移动的距离）数据范围500万，递增输入，不需要排序，显然需要用O(n)做法才能满分，而且读入还可能被卡。能走到一起的，必然是连续的若干个点：如果一个区间中有个点没有移动过去，那么终点要么在他左边，要么在...

区间平移分配律单调性区间和单调递增数学前缀和

2019-08-25

2 1010

牛客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 1041

牛客NOIP暑期七天营-普及组6-B-Bunny的任务

题目大意：n个任务，给你t的时间，最多做多少个？选出来的任务时间之后不超过t即可。假设答案是k个任务，如果其他任务的时间更小，换一个时间更短的任务进来，不影响答案，且花时间只会更少、更好！因此，我们可以选最短时间的k个任务。排序，贪心选择即可。注意：累加可能爆long long，用减法代替...

排序细节贪心

2019-08-25

3 899

牛客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 936

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 1002

牛客NOIP暑期七天营-普及组5-C所以，然后是几点呢

题目大意：输入前一个时间和经过的分数数，输出当前时间。 s数组解释：将下列字符串转成一行，反斜杠转义，每行长度42，那么0就是0-2、42-45、84-86，其他字符以此类推。 ._....._.._....._.._.._.._.._......__..... |.|..|._|._||_||_....

细节模拟字符串分类讨论思维

2019-08-24

0 910

牛客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 927

牛客NOIP暑期七天营-普及组5-A手术等级

题目大意：一个从1开始编号的数组的不完美度为，现在可以将数组分成两个从1开始编号的数组，请问分成的两个数组的不完美度之和最小是多少？将一个数组分成两半，左半边的不完美度的没有任何变化的。右半部分，假设是从i开始，区间是[i, n]：第i个元素由a[i]i变成了a[i]*1，第i+1个元素由a[i...

模拟查找枚举数学前缀和

2019-08-24

0 915

牛客OI周赛11-普及组-D凸包的交

题目大意：根据指定规则生成序列a，在所有长度不小于L的区间中，平均值最大是多少？ 1、递推计算序列：根据题目公式计算即可。 2、预处理前缀和：区间平均值，用到区间和，区间和可以通过前缀和O(1)算出来。 3、平均值即斜率：区间i+1到j的平均值是(s[j]-s[i]) / (j-i)，可以使用斜率优...

区间斜率优化数形结合斜率递推思维前缀和

2019-08-23

0 909

牛客OI周赛11-普及组-C-Colorful

题目大意：n个点，m条边，每条边有颜色，生成一棵树，要求边的颜色数最少，输出最小值。边多、点少，稠密图，但不能直接去重边，因为颜色是很重要的。因为颜色数量不超过12，那就用二进制存储颜色，输出的结果也是1到12之间！用邻接矩阵存储边，暴力枚举每种颜色是否选，时间复杂度，接着搜索判断是否连通。因为...

生成树洪水填充时间复杂度爆搜邻接矩阵搜索 fill 稠密图 flood 二进制

2019-08-23

2 803