Forsaken_QAQ

编辑于 2020-03-29 19:58

+ 关注

【题解】牛客练习赛60 精

A.大吉大利

我们按位考虑，那么每一位的贡献就是在二进制下这一位在 $n$ 个数中出现的次数的平方乘上二进制的系数。

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

B.三角形周长和

也是一道签到题，但是边长改成了曼哈顿距离，至于为什么，完全是因为我不想写std去判精度。

因为 $n$ 是1000，所以直接 $O(n^2)$ 去枚举所有边，那么每一条边显然会在其他 $n - 2$ 个三角形中出现，这个就是这条边的贡献系数，这题就算完了。

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

C.操作集锦

求长度为 $n$ 的字符串的长度为 $k$ 的子序列。我们考虑用 $dp[i][j]$ 表示考虑前 $i$ 个字符形成的长度为 $j$ 的子序列个数。

那么如果我们不考虑会重复的情况，转移方程是 $dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]$ 。

那么显然是多算一部分重复的，我们记录 $pre[s[i]]$ 表示 $s[i]$ 这个字符之前出现的位置，那么多算的这部分很容易发现就是 $dp[pre[s[i]] - 1][j - 1]$ 。

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

D.斩杀线计算大师

算是出了一道假题，正解应该是同余最短路。介绍一下做法吧，现在是要求 $ax + by + cz = k$ ，那么我们设 $k = tc + p$ ，那么显然我们只需要凑出 $ax + by = p$ 就行了，考虑到 $p$ 是 $k \, mod \,c$ 的余数。因此 $p$ 的取值范围是 $[0,1e5)$ 。那么我们不妨设 $dp[i]$ 表示用 $a, b$ 可以凑出的最小的数。不难发现

$dp[i + a] = \min(dp[i + a], dp[i] + a)$ , $dp[i + b] = \min(dp[i + b], dp[i] + b)$ 。如果我们对每个下标都对 $c$ 取模，可以发现转移变成了 $dp[(i + a) \% c] = \min(dp[(i + a) \% c], dp[i] + a)$ 以及 $dp[(i + b) \% c] = \min(dp[(i + b) \% c], dp[i] + b)$ 。容易发现这恰好是最短路的转移，因此我们用 $[0, c)$ 的每个数作为数组下标，然后去跑最短路就能得到合法的方案。注意在跑最短路的时候记录路径的转移，这样就能通过 $dfs$ 去求解答案。复杂度是 $O(clogc)$ 。

额，这道假题应该是源于我图论实在是太差了，导致很多图论的做法都没有了解过。

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

E.旗鼓相当的对手

$dsu \, on \, tree$ 或者长链剖分应该都可以做。我写的std是用的 $dsu \, on \, tree$ 。因为是查询节点 $u$ 不同子树中距离为 $k$ 的点对，因此我们只需要用一个 $deep$ 数组来记录某个点的深度值，那么每次询问相当于查询所有深度为 $k + 2 * deep[lca] - deep[now]$ 的其他子树的节点产生的贡献。

感觉实在是非常的裸，所以难点在于 $dsu \, on \, tree$ ，有其他疑问可以提出来。

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

F.几何带师

总的来说这题我是要谢罪的。因为三点不共线的话，用std的做法有产生精度误差，其实可以避免这个精度误差，但是码量会比较大，因此我花了一天时间去造不存在三点共线的数据。

最后虽然找到了一个方法，但是在写数据生成器的时候，没有判重点，因此数据中存在重点。又因为 $1e5$ 的数据是难以验证是否存在三点共线的，因此我就用纯暴力去和std对跑，然后所有数据都通过了，这是我没有想到的，在std和暴力对上的情况下，我就相信了数据中是不存在重点的。不过还好是最后一题，没有影响排名。下面讲一下做法。

我们已经两个定点 $PQ$ ，现在我们需要判断直线 $AB$ 是否和线段 $PQ$ 相交。现在我们考虑一下 $A,B$ 在 $PQ$ 同侧的情况。那么必定存在 $A$ 在 $\Delta PBQ$ 或者 $B$ 在 $\Delta PAQ$ 中。

我们就假设 $B$ 在 $\Delta PAQ$ 中好了，设 $\theta_{APQ}$ 和 $\theta_{AQP}$ 分别表示 $\angle APQ$ 和 $\angle AQP$ 的角度。设 $\theta_{BPQ}$ 和 $\theta_{BQP}$ 分别表示 $\angle BPQ$ 和 $\angle BQP$ 。那么 $B$ 在 $\Delta PAQ$ 中当且仅当 $\theta_{APQ} > \theta_{BPQ}$ 且 $\theta_{AQP} > \theta_{APQ}$ 。不难发现这是一个二维偏序，我们对其中一维排序然后用 $BIT$ 统计即可。

当满足异侧的时候，则是两个外角满足大小关系，画图可以很容易发现。

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

2024最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(13) 回帖

加载中...

话题同步到我的动态回帖