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

Solved.

题意：给一个最多十四个点的无向图，求选一些边使得，两两点对的最短路之和最小。

题解：如果保留最少的边，最后肯定是棵树。考虑状压dp，dp[i][j]表示bitmask i下以j为根的生成树。合并两个不相交的树新增加的代价就是两个树节点相乘再乘上链接两根的代价（相当于枚举边的贡献）。有点卡常

Problem E

Solved.

题意：给定一根无根树 $T$，每一次执行一次操作：

将上一步获得的有根树（初始状态下，此有根树为以 $1$ 为根的无根树 $T$）的根节点连接到 $T$ 的复制的每一个节点上，并将所得树的根节点设为 $T$ 的复制的某个节点（操作时给出）

求每一步操作所得树的最大独立集。

题解：设 $Inc(t,i)$ 代表树 $t$ 包括第 $i$ 个节点的最大独立集，$Exc(i)$ 代表树 $t$ 不包括第 $i$ 个节点的最大独立集，$Mxm(t)=max(Inc(t,i),Exc(t,i))$ 为树 $t$ 的最大独立集，则对于任何 $t,i$，可以通过状态转移方程发现 $Inc(t,i) \le Exc(t,i)+1$。将所给出的无根树的根节点设为 $1$,此时设以 $i$ 为根的子树为 $son(i)$。首先通过 dp 计算出所有的 $Inc(son(i),i)$ 和 $Exc(son(i),i)$，再通过 $Inc(son(1)=T,1)$ 和 $Exc(son(1)=T,1)$ 按邻边逐个推出所有的 $Inc(T,i)$ 和 $Exc(T,i)$。

我们发现，将一棵树 $T_1$ 以 $rt$ 为连接点复制到另一棵树 $T_2$ 上的每一个节点，成为新树 $T_3$ 时，可以分两种情况讨论：

1）$Inc(T_1,rt)<=Exc(T_1,rt)$：此时包含有 $rt$ 的贡献小于等于不包含 $rt$ 的贡献，根据递推公式，要获得最大独立集不需要将任何一个 $rt$ 的复制加到最大独立集中，因此此时 $Inc(T_3,i)=Inc(T_2,i)+Mxm(T_1)*size(T_2),Exc(T_3,i)=Exc(T_2,i)+Mxm(T_1)*size(T_2)(i \in T_2)$。

2）$Inc(T_1,rt)=Exc(T_1,rt)+1$：此时包含有 $rt$ 的贡献正好比不包含多 $1$，我们可以近似地等价为将 $T_2$ 的每个节点接上一个新节点，再额外加上一个 $Exc(T_1,rt)$ 的独立集。令加上新节点后的新树为 $T'$，此时 $Inc(T_3,i)=Inc(T',i)+Mxm(T_1)*size(T_2),Exc(T_3,i)=Exc(T',i)+Mxm(T_1)*size(T_2)(i \in T_2)$。

我们发现，每一次需求的 $T'$ 结构都是相同的，因此以同样的方法预处理所有的 $Inc(T',i)$ 和 $Exc(T',i)$ 即可。

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.