王清楚

2020-01-22 18:01 已编辑牛客运营

关注

【题解】CCPC Wannafly Camp Day3

A、黑色气球

签到题
$n=2$ ？

B、小吨的点分治

假设我们已经对一棵树进行了点分治得到对应的点分树。如果我们删去原树中的一条边，把得到的两个连通块中的点分别称为黑点和白点。对于点分树中的每个白点（黑点），我们找到它的祖先中最近的一个白点（黑点）作为它新的父亲，这样就能得到两棵全由白点组成的树和全由黑点组成的树（因为有且仅有一个白点和黑点找不到同色的祖先），它们分别为原树切分得到的两棵树的点分树。
反过来再考虑，如果我们把两棵树通过一条边 $(u, v)$ 连接起来，我们怎样把原有的两棵点分树合并起来，并且保持原本点分树中的祖先后代关系呢？可以发现，我们只要把 $u$ 到所在点分树根节点的路径以及 $v$ 到所在点分树根节点的路径按任意顺序归并起来即可。
考虑树形DP。之前的结论意味着，我们只需要关心树的根节点在点分树中的深度。因此设 $f[i][j]$ 表示对 $i$ 的子树进行点分治，并且 $i$ 在点分树中的深度为 $j$ 的方案数。把 $x$ 的儿子 $y$ 的DP数组合并上来时就有 $f^{\prime}[x][i]=\sum_{j=1}^{i} \sum_{k=i-j}^{n} f[x][j] * f[y][k] *\left(\begin{array}{c}{i-1} \\ {j-1}\end{array}\right)$
直接实现是 $O\left( n^{4}\right)$ 的，预处理 $f[y]$ 的后缀和就不需要枚举 $k$ 了。每次合并的复杂度是两棵子树大小的乘积，因此最终的时间复杂度为 $O\left( n^{2}\right)$ 。

C、无向图定向

Easy-3
答案 = 最小染色数 - $1$

D、求和

先进行一些化简。
令 $f(i)=\sum_{j=1}^{i} \sum_{k=1}^{i} \operatorname{gcd}(i, j, k)$
$\begin{aligned} f(i) &=\sum_{d | i} \sum_{j=1}^{i} \sum_{k=1}^{i} d[g c d(i, j, k)==d] \\=& \sum_{d | i} \sum_{j=1}^{\frac{i}{d}} \sum_{k=1}^{\frac{i}{d}} d\left[g c d\left(\frac{i}{d}, j, k\right)==1\right] \\ &=\sum_{d i} \sum_{j=1}^{\frac{i}{d}} \sum_{k=1}^{\frac{i}{d}} d \sum_{e | g c d\left(\frac{i}{d}, j, k\right)} \mu(e) \end{aligned}$
令 $T=de$
那么 $\begin{aligned} f(i)=& \sum_{T | i} \sum_{d | T} d \mu\left(\frac{T}{d}\right)\left(\frac{i}{T}\right)^{2} \\=& \sum_{T | i} \phi(T)\left(\frac{i}{T}\right)^{2}=\sum_{T | i} \phi\left(\frac{i}{T}\right) T^{2} \\ \sum_{i=1}^{n} f(i)=& \sum_{i=1}^{n} \sum_{T | i} \phi\left(\frac{i}{T}\right) T^{2}=\sum_{T=1}^{n} T^{2} \sum_{i=1}^{\frac{n}{T}} \phi(i) \end{aligned}$

E、棋技哥

搞你一波心态!

F、社团管理

决策单调性
类似整体二分转移

G、火山哥周游世界

考虑一下虚树和最远点？

H、火山哥的序列

我们从大到小考虑每个数考虑每个数在什么时候能作为最大的 $gcd$
首先找到是这个数的所有倍数的数,假设位置是 $a[0],a[1],..,a[k-1],a[k]$ ,那么显然还剩着 $(a[k-1],a[k])$ (即 $r<a[k-1]$ ),剩着 $(a[0],a[1])(l > a[1])$ ,还剩着 $(a[0],a[k])$ (即 $l>a[0],r<a[k]$ ),这些都是可能的
考虑一下我们实际上每次相当于删一个区间状物
用一个线段树维护每个点为左端点的时候最远删到了哪，以及还剩多少个区间没有被删即可。

I、N门问题

贪心地让每一步中正确的门的概率最小、每次打开概率最大的门、每次打开概率最小的门，这些策略都是错误的，枚举一些N= $5$ 、 $6$ 的情况大概可以感受到
事实上，通过归纳法可以证明，无论打开了哪扇门，A选择的那扇门在门打开之后都会变成全场唯一概率最小的门。
通过这一结论我们可以把问题转成类似一个序列操作问题：
一开始有 $N$ 个球一起放在序列头，有一个是正确球。
每次 $A$ 从序列头的所有球中随机抽一个，然后 $B$ 可以丢弃剩下球中不是正确球的任意一个，然后 $A$ 把他抽的球单独地放在序列末尾
可以感受到，当 $N$ 足够大时， $B$ 一定可以通过控奇偶性让 $A$ 必败(这也可以坑到只观察序列前三项而认为序列单调递增趋于 $1$ 的选手)
然后可以根据这个写一个 $DP$ ， $f[i][j][k]$ 表示剩 $i$ 个球，第一堆有 $j$ 个球，正确球在位置 $k$ ，这种情况下 $A$ 获胜的概率 $DP$ 发现当 $N>=10$ 的时候 $B$ 就有让 $A$ 必败的策略了
所以其实提前算完了小数据，大数据直接输出 $0$ 就行
于是又在外边套了个无聊的数论模型
J、简单字符串
考虑一下我们肯定会切在Lyndon分解上

$Lyndon$ 串

对于字符串 $S$ ，如果 $S$ 的最小后缀是他本身，那么 $S$ 是 $Lyndon$ 串。
$s$ 为 $Lyndon$ 串等价于 $s$ 本身是其循环移位中最小的一个

我们可以将任意串 $v$ 划分成 $v=v_{1}^{q_{1}} v_{2}^{q_{2}} \ldots v_{m}^{q_{m}}\left(v_{1}>v_{2}>\ldots>v_{m}\right)$ ，其中 $v_{1}, v_{2}, \dots v_{m}$ 都是 $Lyndon$ 串，这一形式被称为 $v$ 的 $Lyndon$ 串划分

存在性：初始时每段一个字符。不断地将相邻两段 $s_{i}<s_{i+1}$ 合并。
唯一性：若有两种方案，取第一次不同的位置，设 $\left|s_{i}\right|>\left|s_{i}^{\prime}\right|$ ，令 $s_{i}=s_{i}^{\prime} s_{i+1}^{\prime} \cdots s_{k}^{\prime} \operatorname{pre}\left(s_{k+1}^{\prime}, l\right),$
则 $s_{i}<\operatorname{pre}\left(s_{k+1}^{\prime}, l\right) \leq s_{k+1}^{\prime} \leq s_{i}^{\prime}<s_{i \circ}$