【题解】牛客CSP-S提高组赛前集训营6

A. 集合统计

出题人:henry_y

题意

定义一个集合 函数为 。给定一个集合 ,求该集合所有非空子集的 函数之和。

题解

解法一(

直接枚举所有子集判断即可。复杂度

解法二(题解做法)

考虑每个数作为答案的贡献。

设小于 的数共有 个,那么 作为最大值的子集共有 个,对答案累加上 即可。 作为最小值同理。

找到小于 的数和大于 的数可以直接排序。

复杂度

标程

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41720323


B. 下雨天

出题人:Trote

题意

个池塘,第 个池塘容量为 ,初始时水量为 。接下来 天会发生水量变化:设第 个水池当前水量为 ,经历了某天,水量如果增加 ,那么该水池在这天过后的水量为 ;若 是个负数(水量减少),那么水量为 。求每天所有水池的总水量。

题解

解法一(​)

注意到 的数据有 分,可以直接暴力获得。

出人意料的是第 个点 ,测试中某些暴力也能跑过,这样暴力可以获得 分。

解法二(数据随机)

接下来需要稍微认真一些地分析问题。

首先注意到小的池塘的水量一定小于等于大的池塘。

然后注意到大小相邻的两个池塘水量要么相等,要么水量相差

或者说,一段相邻的关系要么呈斜率为 的斜线,要么呈斜率为 的直线。

注意到至少有 的数据随机,观察后发现随机情况下,斜线和直线的数目较小,可以用预先编号分段后利用线段树或者其他方法处理。

这样大概可以获得 分左右,会被一些精心构造的数据卡掉。

解法三(题解做法)

可以发现,相邻关系不同的数目是 的,每次最多生成两个新的,或至多删除所有旧的。

利用一个栈维护即可获得满分。

均摊时间复杂度 ,当然也可以用 之类的东西维护。

想起来总觉得很难写,其实写了之后发现没有那么困难。

标程

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41725379


C. 树上队列

出题人:Tweetuzki

题意

一棵 个点的树,求多少种 DFS 序满足任意相邻 个节点的导出子图连通。求所有 都求一遍答案。

题解

解法一(

暴搜每种合法的 DFS 序,检验是否合法。注意一下实现应该可以通过 以内的分数。

解法二(树退化成链)

我们发现不论 取何值,只有从两端中的一端走到另一端合法,也就是所有的答案都是 。因此输出 即可。

解法三(

有一个非常重要的性质隐藏在题目里:

那么我们因此有一个结论:在开始时,队列一定踞在原树的某一棵子树里,且去掉队列所占有的这些节点后,仍然是一个连通图。

这是因为既然 ,就意味着队列开始时占据的 个节点在移动过程中必须移开。而一旦这些节点将原树分成两个子树,那么当队列全部移开时,就会导致顾此失彼,这些子树没有边将它们合并起来。也就是说这样就会导致队列内元素不连通,这是一种不合法的方案。

形式化地说,就是:

表示 是否在初始队列中,即 初始队列 为边集。那么一个合法方案的初始队列就一定有且仅有一个 ,使得

根据对称性,可以发现最终队列一定也是踞在一个子树中的。

我们先介绍一个 的做法:考虑枚举队列所在子树的根节点 。一个节点 可以唯一确定一个初始时的队列(它确定了队列的大小、所占格子,但无法确定顺序,这是我们之后需要统计的)。这是因为我们假设 的父亲是 ,则只有 这一条不属于该队列。如果我们将 设为全树的根,那么 的大小就是 。由于 ,因此 一定是 所有子树中唯一一个最大的。

于是我们就可以确定哪些节点是初始队列中的节点,哪些节点不是队列中的节点。

接下来我们讨论情况是否合法。

情况合法的充要条件是,在 子树的所有节点中,儿子节点个数大于 的节点的子树大小不超过 。这个是很好理解的,因为队列遇到分叉地方必须要分开,而这个子树的根节点是无法移开的(不然就把这个叉分开了),因此所有儿子节点个数大于 (有分叉)的子树大小在最终状态中肯定是被队列占满的,否则不合法。

在合法的状态中,我们需要统计方案数。

根据乘法原理我们发现,方案数就是 子树的拓扑序数量乘上 子树除去 子树后的拓扑序数量。拓扑序的数量可以通过预处理组合数,然后依次合并子树转移。

时间复杂度

解法四(题解做法)

不管你是什么方法得到的反正我是打表发现的一个结论:对于答案序列 ,一定存在一个划分点 ,满足对于 的答案都是 的答案都为一个相同的值。

这个结论的正确性是很容易理解的。根据上面的 做法我们发现,队列的路线一定是从一个子树出发,然后经过一条长长的链,最后落到一棵子树中。再根据已经提及的合法条件可知,随着队列大小的扩大,知道扩大到这两端较大的子树的大小后,就能够填满这两棵子树,开始出现合法方案,而且在这之后随着队列大小的增加,新的元素可以被挤到中间那一条链上去,而这样是不会影响总方案数的。

因此我们试图在原图上找到这样一个类似于流星锤的形状:两棵子树 ,满足较大的子树大小尽可能小,以及中间的一条长链,这条长链上有所有不在 子树内的点。注意这里的长链指的是边。

想到子树大小尽可能小,我们自然地想到了树的重心(PS:比赛时,选手 Freopen 提交了一个这么找重心的方法——先随便以一个点为根,然后找到树上唯一一个子树大小为 的点,即为树的重心。在这道题上,这种方法是正确的。因为如果不存在这样一个点,那么答案一定全部都是 )。我们可以找出树的重心 ,然后找到重心的最大子树 ,可以发现一旦存在答案,那么 的这条边一定是“流星锤”中间这条链的一部分。然后把 这条边不断往外延伸,就可以找到“流星锤”两端的子树节点 。然后这个划分点 就等于 子树大小的较大值,答案就是 子树的拓扑序数量乘上 子树的拓扑序数量的两倍。

预处理阶乘的逆元 ,找重心 ,动态规划求拓扑序 ,输出答案 ,因此总复杂度

解法五(验题人做法)

对解法三的 DP 进行换根优化。注意细节。

时间复杂度也是

标程

解法四

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41724753

优化找重心:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41724987

解法五

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41724763

全部评论
T1 5min 100pts, T2 5min 30pts, 然后就是2h55minの自闭
5 回复
分享
发布于 2019-11-09 22:09
想起来总觉得很难写,其实写了之后发现调不出来。
2 回复
分享
发布于 2019-11-10 08:06
秋招专场
校招火热招聘中
官网直投
T2的100分是什么鬼?没看懂,还是我太菜了
2 回复
分享
发布于 2019-11-10 13:39
t2 std 哪去了
1 回复
分享
发布于 2019-11-09 22:19
T3不需要知道最后的结论也可过,但写起来超级麻烦qwq
1 回复
分享
发布于 2019-11-09 22:26
可不可以把第二份题解再详细地说一下qwq
1 回复
分享
发布于 2019-11-10 07:48
又是您出题😆
1 回复
分享
发布于 2019-11-10 08:18
spfa
点赞 回复
分享
发布于 2019-11-09 22:04
前排
点赞 回复
分享
发布于 2019-11-09 22:05
什么也看不懂,只能默默说一句NB
点赞 回复
分享
发布于 2019-11-09 22:07
T3 语文大战
点赞 回复
分享
发布于 2019-11-09 22:10
T2 有std吗?
点赞 回复
分享
发布于 2019-11-09 22:23
表示T3读不懂题qwq
点赞 回复
分享
发布于 2019-11-10 11:00
第一题dp也可以吧
点赞 回复
分享
发布于 2019-11-10 17:42
T1用前缀和可以我的代码
点赞 回复
分享
发布于 2019-11-10 21:23

相关推荐

头像 头像
03-18 20:55
浙江师范大学
点赞 评论 收藏
转发
12 2 评论
分享
牛客网
牛客企业服务