2019-11-02 22:34 北京航空航天大学运维工程师

关注

【题解】牛客CSP-J入门组赛前集训营3

有趣的游戏

对于100分算法

按照题目的意思直接模拟，扫一遍数组，如果字符串有 $6$ 或者字符串中 $0$ 的个数大于 $1$ 的个数就输出 $Alice$ ，否则输出 $Bob$
时间复杂度 $O（n），n$ 为字符串长度

幸运数字

对于20分

对于小的数据，我们很简单的可以利用 $dfs$ 去解决， $dfs（i，sum，mod）$ 代表放了 $i$ 个数字，它的和为 $sum$ ，余数为 $mod$ 。于是我们可以转移到 $dfs（i+1，sum+x，（mod*10+x）%p)$ 当 $sum=y，mod=0$ 的时候统计答案。
其实这个时候我们可以用一个常见的小优化，也就是记忆化将分数提高到 $90$ 分。

对于100分

我们可以利用 $dp$ 解决， $f[i][j]$ 代表数码和为 $i$ ，余数为 $j$ 的数字个数，于是我们转移方程为 $f[i+x][（j*10+x)%p]+=f[i][j]$ 。输出 $f[y][0]$ 即可。

拯救地球

对于20分算法

直接对于每个任务暴力搜索
时间复杂度 $O（qm+qn）$

对于另外20分算法

将外星生物看成每条道路的边权，将国家看成点后，我们发现边权很小，于是我们可以对于 $1$ ~ $w$ 中的每个权值建立一张图，保证第 $i$ 张图中的边在原图中的边权小于等于 $i$ .然后对于每张图都预处理出来每个点最多能拯救多少个点，于是每个任务的答案都被处理出来了.
时间复杂度 $O（wm+wn+q）$

对于再另外20分算法

将任务看成询问，先让询问按照 $w$ 从小到大排序，然后从 $x$ 出发，把 $x$ 周围的边全部存进一个优先队列中，优先队列按边权从小到大排序，然后扫一遍询问，如果当前询问的 $w$ 大于等于优先队列的队首，那么弹出队首，然后把这条边周围的未被标记的边标记并加入优先队列，当无法弹出队首时，此时访问过的点数就为此次询问的答案
时间复杂度 $O（qlogq+mlogm）$

对于100分算法

将任务看成询问，我们把边和询问按照 $w$ 从小到大排序，然后扫一遍，扫的同时加边建图，然后用并查集维护加边操作和联通块大小
时间复杂度 $O（n+mlogm+qlogq）$

兔纸的公司

题外话

我想了很多种水法，都没办法水到比较高的分数。
前几个点造的都很水，所以应该都能水到。
后面几个点我并没有想到特别好的水法，想到的一些水法也并没有办法水到分，所以出题人实在不知道该如何卡水法，加强数据，只能恭喜能水到分的同学。

题目大意

给定一棵有根树，根为 $1$ ，每个点有个权值 $a_i$ 。
除了根之外，都有一个父节点，且最多只有一个孩子节点。
可以进行若干次这样的操作：将 $a_i$ 减1，将 $a_{f_i}$ 加1，然后交换 $i$ 和 $f_i$ 的权值即 $swap(a_i,a_{f_i})$ ， $f_i$ 是 $i$ 的父节点。
询问最终是否有可能让这颗树形成一个大根堆，即父节点大于等于孩子节点。

对于10%的数据

$n$ 只有 $3$ ，那么树只有2中形态，可以分类讨论一下。
题外：抱歉QAQ，没想到一些同学辛辛苦苦写了分类讨论结果没开ll的情况，第一档数据我是卡了int的...

对于20%的数据

$n \leq 10$ 各种暴力爆搜乱搞

对于另外10%的数据

可以注意到在篡位的过程中是有不变量的，即 $a_i-dep_i$ 始终是不变的。 $dep_i$ 为 $i$ 的深度。
对于 $i$ 爬到 $f_i$ 深度减少了，权值也减少了， $f_i$ 换到 $i$ 深度增加了，权值也增加了。因此 $a_i-dep_i$ 始终是不变的。
那么设 $b_i=a_i-dep_i$ 。
可以发现我们可以交换树上任意两个点的 $b_i$ 而不改变其他点的 $b_i$ 。因为孩子与父亲换和父亲与孩子换是等价的，我们只需要将 $i$ 沿 $i$ 到 $j$ 路径不断交换，再将 $j$ 沿 $i$ 到 $j$ 路径不断交换，就可以实现任意两个点的交换。
既然如此，我们可以将题目看成是将 $b_i$ 这些数填在树上。
我们将 $b_i$ 从大到小排序，然后依次从根往下填。
但注意到虽然 $b_i$ 满足了大根堆，但 $a_i$ 不一定满足大根堆。
如果想让 $a_i$ 满足大根堆，需要满足父节点的 $b_{f_i}$ 严格大于子节点的 $b_i$ 。
证明： $b_i<b_j\\ a_i-dep_i<a_{f_i}-dep_{f_i}\\ 其中 depi=dep_{f_i}+1\\ a_i-1<a_{f_i}\\ a_i都是整数，所以有\\ a_i<=a_{f_i}$
因此题目变成将 $b_i$ 填入树内且父节点严格大于孩子节点。
由于这个部分分满足树是一条链，因此只要 $b_i$ 互不相同，就可以满足父节点严格大于孩子节点的条件。
因为 $n\leq10^3$ 可以预处理出 $b_i$ 后 $O(n^2)$ 暴力枚举两个数看是否相等。

对于再另外20%的数据

在上一个部分分的基础上，我们可以利用 $sort$ 或 $map$ 在 $O(nlogn)$ 的时间内判断是否有两个数相等。

对于剩余的50%的数据

对于不是链的情况，我们可以将最大的 $b_i$ 填在根节点，然后把根节点删去，那么最大的 $b_i$ 只能有一个。
删去根节点后会形成若干条链，那么 $b_i$ 就可以有相同的数，因为可以填在两条不同的链中。
那么只要让每一条链中的数都互不相同，然后对于每一条链单独的排序一下，就可以满足题目要求。
我们可以将 $b_i$ 离散化一下，然后记 $c_i$ 为 $i$ 在 $b$ 中出现的次数。
贪心的想， $c_i$ 越大的要更早处理，因为越前，链的条数就更多，我们发现支链数越多，就会越优，因此我们将 $c_i$ 从大到小排序，依次处理，维护每条链目前的剩余空位，以及链的条数。
那么我们每次贪心的将这些数放在链空位最多的链上，这个过程可以用优先队列来实现。
由于 $\sum_{i=1}^{max\{b_i\}}c_i=n$ 所以总的效率是 $O(Tnlogn)$ 。