CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 比赛地址 ======

[[https://ac.nowcoder.com/acm/contest/5667 |牛客OJ]]

Pro : 3/5/11

Rank: 312/1159

====== 题解 ======

===== [B] Boundary =====

==== 题意 ====

给出平面上$n$个点,找到一个过原点的圆,使得其能覆盖最多的点.

==== 题解 ====

因为已知原点在圆上,所以只需要枚举两个点就可以确定一个圆.枚举出所有的组合,算出共$\frac{n(n-1)}{2}$个圆心.找到其中出现次数最多的圆心,设出现了$k$次,则答案一定是$C_{Ans}^{2}=k$的解,这是显然的.总的时间复杂度为$O(n^{2}logn)$.

本题卡精度,eps需要设到$1e-10$.

===== [C] Cover the Tree =====

==== 题意 ====

给出一棵树,求最少的路径数,使得树上的每条边至少被覆盖了一次.

==== 题解 ====

显然,每条选择的路径一定是以叶子节点为起止点的.如果叶子的数目是$n$的话,答案就是$\frac{n+1}{2}$.接下来是如何将这些叶子两两配对.先求出DFS序,设$a_{i}$表示第$i$个叶子.只需要让$a_{i}$与$a_{\frac{n}{2}+i}$配对即可.对于叶子数是奇数的情况单独判断下就好.

===== [D] Duration =====

==== 题意&题解 ====

签到题

===== [F] Fake Maxpooling =====

==== 题意 ====

给出一个$n\times m$的方阵,$a_{ij}=lcm(i,j)$.求这个方阵中,每一个$k \times k$子阵的最大值之和.

==== 题解 ====

预处理出方阵后拿单调队列直接计算即可.

据说算lcm时会卡常,用了一个神奇的gcd写法直接莽过去了.

===== [G] Greater and Greater =====

==== 题意 ====

给出一个长度为$n$的序列和一个长度为$m$的序列,$m<n$.求将第二个序列放到原序列的哪些位置,可以让第一个序列的值大于等于第二个序列的值.

==== 题解 ====

bitset的奇妙用法.

预处理出第二个序列中,每个位置可以放在哪里,然后与到一起,再统计一下1的数目就行了.时间复杂度是$O(\frac{nm}{64})$.

===== [H] Happy Triangle =====

==== 题意 ====

有三种操作,第一种是往一个集合里加入一个数,第二种是删除一个数.第三种是询问操作,给出一个数,问能否从集合中取出两个数,使得这三个数构成一个合法的三角形.

==== 题解 ====

对于给出的数,分最大边和不是最大边讨论.

对于不是最大边的情况,只需要求两个前驱;对于最大边的情况,只需要考虑所有相邻的数就行.证明是显然的.

官方题解需要写一个平衡树,其实可以通过两个set+线段树解决.

===== [K] Keyboard Free =====

==== 题意 ====

已知三个同心圆的半径,求在这三个圆上各随机取一个点所构成的三角形的面积的期望.

==== 题解 ====

首先可以固定一个点.当第二个点也固定之后,和第一个点连线,先算出第三个点到该直线的距离的期望,再算面积的期望.因为精度要求不是很高,第二个点可以随机取足够多次.

实际测试发现卡常卡精度QAQ

====== 总结 ======


开题策略大失败.

C题一开始没什么思路,就一直在写B.结果因为没注意看条件,以为会有点重合的情况,自己给自己加了一堆限制条件,代码也改了好几版.发现只需要交初版代码的时候又被卡了精度莫名WA,最后凭直觉改了eps才过去.

因为在B题上浪费了太多时间,后期又一直在死磕C题和K题,导致有些题根本就没有读,错失了过G题和H题的机会.K题思路已经是正确的了,但是剩的时间太短来不及推式子,后期节奏彻底崩塌.

望之后引以为戒QAQ.
CVBB ACM Team

用户工具

站点工具

页面工具
