范艺杰

分类

题解(20)

/ 注册

全部文章（共20篇）

牛客练习赛71 C 数学考试

我们发现可以通过第一个不合法的位置不重不漏的统计所有非法方案。设dp[i]表示处理到sa[i],且sa[1]，sa[2]...sa[i - 1]这些点都是合法的方案数。那么答案就是n! - dp[1] * (n - sa[1])! - dp[2] * (n - sa[2])! - ... - dp[...

2020-10-10

10 684

牛客小白月赛28 E 会当临绝顶，一览众山小

题目可以转化成1）找某个坐标左边第一个比他大的数。2）找某个坐标右边最小的数。这两个操作分别可以用两颗线段树维护。 1）中维护区间max，如果右区间最大值比要查询的值大，则递归右区间，否则递归左区间。2）中维护区间min，如果据区间最小值比右区间最小值小，递归左区间，否则递归右区间。复杂度O...

2020-09-27

2 613

牛客练习赛70 D 数树

没看到题目中条件保证是一颗森林，自行加强题目。这里采用时间线段树+回退并查集来解决。并查集可以O(1)的插入，很难O(1)的支持删除操作，但是可以回退。我们使用时间线段树，将所有操作锁定为插入操作，使用回退并查集维护即可。复杂度O(nlogn)。 #include <cstdio> #i...

2020-09-27

4 481

浙江科技学院第17届大学生程序设计竞赛（公开赛）F

每个本质不同子序列的贡献是1。本题的期望可以转化为概率。由于序列自动机就是子序列的最小表示。我们依据序列自动机进行概率转移。 #include <cstdio> #include <algorithm> #include <cstring> using names...

2020-09-15

6 741

牛客练习赛69 F 解方程

迪利克雷卷积的性质告诉我们，积性函数卷积性函数的得到的结果也是积性函数。题目公式中有两个积性函数，因此可以推断出f也是一个积性函数。因此我们只要处理出所有f(p^k) (p是质数)的值即可线性筛，复杂度O(n)。代码： #include <cstdio> #include <al...

2020-09-11

6 1051

牛客练习赛66 E

我们考虑每个点成为区间左端点时合法的右区间范围，我们假定a是下标比i大的且值比i大的最小下标，b是下标比a大且值比i大的最小下标，那么以i为左端点的合法区间范围应是[a, b -1]。同理我们也能求出i是区间右端点时合法的区间[ql, qr]。set即可完成。我们从左往右扫，每个点是左端点时的合法区...

2020-06-27

8 894

第十七届同济大学程序设计预选赛H

我们不妨将入栈操作看作在这个时间点加1，将出栈操作看作这个时间点-1。那么询问当前时间点的栈顶元素就是找到最大的后缀下标使得这个后缀的和是1即可。我们通过线段树来维护区间后缀值，维护时，需要同时维护这个区间和以及后缀最大值。如果采用是自底向上的线段树即zkw线段树，那么query只要一个函数即可。如...

2020-05-10

2 770

武汉大学2020年大学生程序设计大赛决赛C

这里介绍一种失了智的算法。这种算法基于插桩原理。我们每隔len插一个庄,我们发现所有长度为len的子串都会和一个桩相交。然后对于每个长度len我们只要能够通过n/lenlog(len)的复杂度算出所有长度为len的SAN值就可以在nloglog的时间复杂度内解决问题。这里有三个子问题：1.如何判断[...

2020-04-26

8 654

牛客算法周周练3E

这是一道典型的网络流题目。我们只要对于每个SPF值向汇点连一条容量为这个SPF值个数的边，然后源点向每头牛连一条容量为1的边，每头牛向每个可用的SPF值连一条容量为1的边，求最大流即可。这里还有一个问题就是如果按照上述方式建图可能或有C*1000条边这个数量级是2e6的有可能TLE，我们需要建边优化...

2020-04-21

3 618

【民间题解】牛客练习赛56

没有人写题解我来写一发 A-小蒟和他的乐谱设当前的音符为x ，((x - 1) % 7 + 7) % 7即为这个数在模7意义下的正模。判断是不是0，1，2，4，5即可。然后问题简化为求最长全1段。复杂度O(n)。 B-小琛和他的学校我们钦...

2019-12-29

4 1258