====== 比赛地址 ====== [[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