2021牛客OI赛前集训营-提高组(第二场)题解

UPDATE: 更新了 T2 组合数的粗略推导过程。

串串串

算法一

暴力枚举 ,计算 的个数之和对 取模的结果。

时间复杂度 ,期望得分 分。

算法二

可以发现,交换 中任意两个位置,答案都是不变的,交换 中任意两个位置也一样。

那么我们可以将 中的 放在前面, 放在后面,答案即为 的个数和 的个数之差对 取模的结果。

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916774

方格计数

算法一

考虑枚举两个端点,强制两个端点选,令 为两个端点之间 轴上的距离, 为两个端点 轴上的距离,那么这里面可以选择的点的个数有 个。我们要求 个小球(强制两个端点选),需要放到 个盒子里,相邻两个小球的盒子编号差至少为 ,方案数为

这个推导的话大概就是我们选定 个格子,剩下的格子先忽略 的限制,选出若干种方案,然后再将这 个格子之间,就一定满足 的限制了。

时间复杂度 ,期望得分 分。

算法二

延续算法一的思路,发现对于相同的 方案数也是相同的,考虑枚举 ,跟算法一一样做,最后再乘个 就好了,时间复杂度

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48923271

树数树

算法一

表示 的子树中,允许使用子树外的 个祖先所得到的最长序列长度是多少,转移相当于各个儿子的一个 卷积。

时间复杂度 (不太确定),期望得分 分。

算法二

可以发现,一个节点 可以将子树中的两个序列给拼成一个序列,而且我们在处理完 的父亲的时候 的状态已经不用管了,我们可以用堆维护出 的子树中的点能组成的序列,转移相当于是将所有子树的堆合并成一个,然后取出其中最大的两个合并成一个。

可以使用启发式合并或者可并堆维护这个过程。

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916780

序列

算法一

考虑数位DP。

从前往后添加数字。考虑到某一个时刻,如果存在一个位置不在任何一个 se 序列中,且其后数位和(包括这一位) ,则这个数字就是不合法的,因为继续添加数字不可能影响到这一位。那么状态中不妨记录最长的数位和 的后缀以及不在任何一个 se 序列中的数字位数(显然这些数字组成一个后缀)。

先不考虑数字 。根据隔板法,数位和 的数字并不多。观察到不在任何一个 se 序列中的数字位数首先不会大于最长的数位和 的后缀的位数,所以状态数只有区区

至于转移,枚举在末尾添加的数,暴力判断是否合法以及转移到的状态即可。

考虑数字 。如果把 记进状态中,状态数就会爆炸。发现 不会被任何一个 se 序列覆盖,当且仅当其左右两个数都不会被任何一个 se 序列覆盖。换言之,如果转移时发现存在一个 不合法,那么也必定存在一个非零的数不合法。即我们在状态中可以完全不考虑 ,通过加 转移到下一位时不改变状态。

时间复杂度 ,期望得分 分。

算法二

发现这个数位DP没有什么上界的限制,每次转移的矩阵是固定的,显然考虑矩阵乘法优化DP。

唯一的问题是这个矩阵有一点点大,而且虽然是个稀疏矩阵,但是多乘几次就不稀疏了。

设转移矩阵为 ,初始矩阵为 ,那么我们所要求的就是 (具体细节取决于你的写法)。

假设我们现在已经知道了 的一个零化多项式 ,有

考虑将 分解为 ,其中满足 的次数小于 ,即

那么有

,即 时的答案。

那么有,且由于 是一个稀疏矩阵,我们可以在 的时间内计算出所有

幸运的是,我们知道矩阵的特征多项式就是他的一个零化多项式,且次数等于矩阵的行数。也就是说,我们可以求出 的一个 次的零化多项式。

唯一的问题是一般的求特征多项式的解法是 的,无法通过,但是你可以通过本地打表出 情况的矩阵的特征多项式。

得到特征多项式之后,你可以通过快速幂在 或者 的时间内得到

结合算法一,期望得分 分。

算法三

回到零化多项式 上来。

,有 ,即 .

换言之,

移项,则有

什么意思呢,就是说 有一个长度为 的递推式。

这样,我们根本不用显式的求出这个矩阵,只需要求出 的前 项,使用 算法求出其最短递推式,使用快速递推求出 即可。使用暴力多项式乘法即可。

时间复杂度 ,期望得分 分。

代码链接:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48916784

全部评论
这个 t4 是另一个出题人出的(我才不可能这么毒瘤
3 回复
分享
发布于 2021-10-06 22:32
这个D真的在CSP/NOIP范围吗
1 回复
分享
发布于 2021-10-06 22:14
英特尔
校招火热招聘中
官网直投
什么***D,写的AC自动机,感觉可以BM,但是只能算出答案的前500项,然后就过不了大样例。。。。
1 回复
分享
发布于 2021-10-06 22:21
T2的式子严格来说应该是g-1个盒子放n-2个球吧,最开始g+1个盒子除去(n-1)个空格并且固定左右端点要选。
1 回复
分享
发布于 2021-10-07 08:41
B 的柿子是怎么推的啊 /yun
1 回复
分享
发布于 2021-10-07 09:41
比上次的那**玩意好多了
点赞 回复
分享
发布于 2021-10-06 23:40
B 的柿子是不是上下写反了 = =
点赞 回复
分享
发布于 2021-10-07 09:30
T4的30分复杂度应该是o(n*2816*10)吧
点赞 回复
分享
发布于 2021-10-07 13:25
B的柿子好像又有点问题?为什么会多一个 -(k-1) ?
点赞 回复
分享
发布于 2021-10-10 19:24
请问一下能放一下 C 题暴力树形 dp 的部分分代码吗,感觉推不出转移方程
点赞 回复
分享
发布于 2021-10-17 07:33

相关推荐

7 1 评论
分享
牛客网
牛客企业服务