偶尔刷刷题

分类

题解(32)

/ 注册

全部文章（共3篇）

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

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

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

2019-08-23

0 906

牛客NOIP暑期七天营-普及组4-A火龙果树

题目大意：一棵树，第一年只有祖先0；每一年，0可以分支出1个1，0可以分支出1个0和1个1，n年后共有多少个结点？ f[i][j]表示第i年数字j的数量： f[i][0] = f[i-1][1]，因为只有1能得到0； f[i][1] = f[i-1][0]+f[i-1][1]，因为0和1都能够得...

预处理状态规律递推

2019-08-22

0 865

牛客NOIP暑期七天营-普及组2-C硬币

题目大意：有n枚硬币，a枚正面朝上，b枚反面朝上，每次操作随机抽取一枚翻过来，m次操作正面朝上的数量的数学期望是多少？如果只有1枚硬币，每次翻转的都是同一枚，最终要么是正面朝上，要么是反面朝上，数学期望是0或者1。对于n枚硬币，a枚正面朝上，b枚反面朝上，下一次有两种状态： 1、随机抽到正面朝上...

期望滚动数组递推概率 DP

2019-08-20

1 736