CCPC-Wannafly Winter Camp Day3 (Div 1)

CCPC-Wannafly Winter Camp Day3 (Div 1)

Problem A

Unsolved.

Problem B

Solved.

题意：平面上有一个圆和两个点，求圆上一点，使得两个点不经过圆的内部到这个点的路径长度尽量小。

题解：分两种情况讨论：

第一种，两点连线过圆：两点到切点距离 $\times$ 切点之间的弧长，上下取 $min$。

第二种，两点连线与圆没有交点：只需要考虑该点在半圆上的位置，两点到该点距离是一个凹函数，三分求最小值即可。

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved.

寒假的时候无从下手，现在看来是个模板题（逃

题意：求$\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{n}\mu(gcd(i,j))$

题解：套路，枚举gcd，变成$\sum\limits_{k=1}^{n}\mu(k)(2\sum\limits_{i=1}^{n}\phi(i)-1$然后杜教筛搞$\mu, \phi$的前缀和。复杂度不会算，但是肯定小于$O(n)$，又给了5s，最后1500ms。

Problem G

Solved.

题意：一堆定义。

题解：直接贪心。显然 $1$ 的位置放 $1$ ，那么 $1$ 后面的数都比 $1$ 大（废话）。

$2$ 的位置如果在 $1$ 之后，显然这个位置先不放 $2$ ，因为 $2$ 放越前面，字典序越小。

于是贪心策略就出来了。

先贪心的从 $1$ 开始往后放，从 $1$ 的位置开始枚举，每次只往前放，直到放在第一个位置上，第一阶段结束。

剩下没有填数的位置，显然怎么填都成立，于是，贪心的把剩下的数从前往后填。

Problem H

Unsolved.

Problem I

Solved.

题意：$n$ 个人石头剪刀布，每次选两个人 $x,y$，$x$ 胜或平则 $x$ 留，否则 $y$ 留。每一个人的出拳都不会改变，最初一共有 $3^n$ 种出拳方案，在游戏进行的过程中，多次询问能让 $x$ 留下的出拳方案数量。

题解：要让一个人留下，只要看他要留下，需要作为 $x$ 赢多少次，和作为 $y$ 赢多少次。

每一次比赛都建立一个新的节点，这样整场比赛可以变成一棵二叉树，左孩子作为 $x$ 出战，右孩子作为 $y$ 出战。实际上，不考虑留的是谁，每一个节点上留下来的人出三种拳的可能性是一直相等的，$x$ 胜利的概率是 $\frac{2}{3}$，$y$ 胜利的概率是 $\frac{1}{3}$，因此每一次作为 $x$ 出战，出拳方案总数就乘上 $\frac{2}{3}$，否则乘上 $\frac{1}{3}$。

这样，我们只要维护每一个点到当前根路径当了多少次左孩子和右孩子，用并查集维护即可。

Problem J

Unsolved.