Scarlet_Hypoc
Scarlet_Hypoc
全部文章
题解
比赛题解(3)
归档
标签
去牛客网
登录
/
注册
Scarlet_Hypoc的博客
一名可怜的小蒟蒻的博客……
全部文章
/ 题解
(共7篇)
牛客挑战赛48 D-牛奶 题解
大家应该普遍用的是州区划分那题的做法,毕竟这题求一个集合的贡献是很容易的,再套一个子集卷积优化递推就做完了。 这里提供一种不同的做法。假设求出来集合贡献的生成函数为 ,那么答案其实就是子集卷积意义下的 。 update: 被评论区大佬教育了,事实上这个等比数列不需要恰好求到第 项, 以上的不影响答...
2021-03-20
9
708
牛客IOI周赛18-提高组 C-山脉 题解
考虑枚举山峰的最右边位置 ,那么 ~ 是一个不下降序列, ~ 也是个不下降序列。 考虑一个最大高度为 的不下降序列的方案数,做一下差分,那么有若干个位置不为 ,且这些位置的总和为 ,那么相当于将 分给这 个位置,由于数字都大于 ,所以第一个位置的差分值至少为 ,所以实际上是将 分给 ...
2020-10-07
1
773
牛客等级之题 N1(8.3) 题解
题目传送门 题目大意: 一开始箱子里有 个黑球 个白球,每次有 的概率放进去一个黑球,有 的概率放进去一个白球,放完球后再随机拿一个球,问进行 次后箱子里黑球期望个数。 题解 可以注意到每次操作后球数是保持在 不会变的。 令 表示进行 次操作后黑球的期望个数,显然有 。 有四种情况需...
2020-09-15
1
693
牛客练习赛60 F-几何带师 题解
题目传送门 题目大意: 给出一条线段 以及 个点,问从这 个点里面选出两个点,这两个点所在直线穿过 的方案数。 题解 考虑在 同侧的两点 ,假如 穿过 ,那么一定有 在 内或 在 内。 不妨设 在 内,那么一定满足 间一定满足 ,这个您随手画两条线段就能明白。 然后这个东西...
2020-09-15
1
649
牛客练习赛64 E-红色的樱花
题目传送门 题目大意: 有一张 的网格图,起点为 ,终点为 ,有三种移动方式:1、 选择一个 ,移动到 ,代价为 ;2、移动到 ,代价为 ;3、移动到 ,代价为 ,问能否到达终点,能的话最小代价是多少。 题解 比较显然的是操作 至多用一次,那么看一下用和不用哪个代价更小即可。 假如只看操作 ,那...
2020-09-15
0
579
B. 牛牛的算术 题解
推一下柿子就好了: 令 ,代入得: 可以发现,当 时答案肯定为 ,所以只需要考虑 的情况。那么这个东西也像上面预处理出来就可以 回答询问了,代码如下: #include <cstdio> #include <cstring> #include <algorit...
2020-08-28
0
625
B-Suffix Array 题解
A. B-Suffix Array 给出一个字符串,定义一个字符串 ~ 对应的 ~ 满足 ,如果不存在这样的 ,那么 ,现在要求将 的所有后缀按照其对应的 序列的字典序排列。 题解很神,用到一个神仙结论直接切飞,原文为(为了好看些,我自己稍微加了点 LaTeX 元素): Let T...
2020-07-16
25
1010