Scarlet_Hypoc

题解

比赛题解(3)

/ 注册

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

牛客挑战赛48 D-牛奶题解

大家应该普遍用的是州区划分那题的做法，毕竟这题求一个集合的贡献是很容易的，再套一个子集卷积优化递推就做完了。这里提供一种不同的做法。假设求出来集合贡献的生成函数为，那么答案其实就是子集卷积意义下的。 update：被评论区大佬教育了，事实上这个等比数列不需要恰好求到第项，以上的不影响答...

2021-03-20

9 756

牛客IOI周赛18-提高组 C-山脉题解

考虑枚举山峰的最右边位置，那么 ~ 是一个不下降序列， ~ 也是个不下降序列。考虑一个最大高度为的不下降序列的方案数，做一下差分，那么有若干个位置不为，且这些位置的总和为，那么相当于将分给这个位置，由于数字都大于，所以第一个位置的差分值至少为，所以实际上是将分给 ...

2020-10-07

1 853

牛客等级之题 N1(8.3) 题解

题目传送门题目大意：一开始箱子里有个黑球个白球，每次有的概率放进去一个黑球，有的概率放进去一个白球，放完球后再随机拿一个球，问进行次后箱子里黑球期望个数。题解可以注意到每次操作后球数是保持在不会变的。令表示进行次操作后黑球的期望个数，显然有。有四种情况需...

2020-09-15

1 762

牛客练习赛60 F-几何带师题解

题目传送门题目大意：给出一条线段以及个点，问从这个点里面选出两个点，这两个点所在直线穿过的方案数。题解考虑在同侧的两点，假如穿过，那么一定有在内或在内。不妨设在内，那么一定满足间一定满足，这个您随手画两条线段就能明白。然后这个东西...

2020-09-15

1 694

牛客练习赛64 E-红色的樱花

题目传送门题目大意：有一张的网格图，起点为，终点为，有三种移动方式：1、选择一个，移动到，代价为；2、移动到，代价为；3、移动到，代价为，问能否到达终点，能的话最小代价是多少。题解比较显然的是操作至多用一次，那么看一下用和不用哪个代价更小即可。假如只看操作，那...

2020-09-15

0 628

B. 牛牛的算术题解

推一下柿子就好了：令，代入得：可以发现，当时答案肯定为，所以只需要考虑的情况。那么这个东西也像上面预处理出来就可以回答询问了，代码如下： #include <cstdio> #include <cstring> #include <algorit...

2020-08-28

0 696

B-Suffix Array 题解

A. B-Suffix Array 给出一个字符串，定义一个字符串 ~ 对应的 ~ 满足，如果不存在这样的，那么，现在要求将的所有后缀按照其对应的序列的字典序排列。题解很神，用到一个神仙结论直接切飞，原文为（为了好看些，我自己稍微加了点 LaTeX 元素）： Let T...

2020-07-16

25 1087