Scarlet_Hypoc

分类

比赛题解(3) 题解(7)

/ 注册

全部文章（共10篇）

牛客2021年愚人节比赛题解

有些奇奇怪怪的题不能保证分析是正确的…… A 啥都不干就好了。 #include <cstdio> int main() { } 话说7秒AC的那个老哥确实离谱，这必是个大预言家（ B 需要通过诡异的手段获得系统时间，这些科技具体可以自己百度，这里提供一种（虽然我也不明白原理）： #...

愚人节题解

2021-04-01

11 1183

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

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

2021-03-20

9 590

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

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

2020-10-07

1 647

牛客挑战赛43 部分题解

A 容易发现每一个数分一段是最优的，因为两个数或起来可能变小而绝不可能变大。代码如下： #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using...

2020-09-21

2 589

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

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

2020-09-15

1 549

牛客IOI周赛17-提高组题解

可怜的比赛又被神仙xgc秒飞了…… T1 考虑枚举断掉哪一条白线，断掉这条白线之后，要使树不联通，就要把子树里延伸出子树外的黑线都删掉，显然有两条及以上时不可能做到，一条时就把这条删掉，没有时就可以随便删一条黑线，用树上差分维护一下即可。代码如下： #include <cstdio> ...

2020-09-15

1 460

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

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

2020-09-15

1 544

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

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

2020-09-15

0 476

B. 牛牛的算术题解

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

2020-08-28

0 522

B-Suffix Array 题解

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

2020-07-16

25 895