Contest Info

date 2017.08.06 10:00-15:00

practice link

Solutions

A. Biconnected

题目大意：给你一个 \(n\leq 10\) 个点的简单无向图（实际上输入的是它的补图），问它有多少个子图满足 \(1\) 到 \(n\) 所有点在该子图中属于同一个边双连通分量，答案对 \(10^9+7\) 取模。

题解： （cls 在 WC 上讲的方法是用 dp 求出不双连通的子图数量，用所有子图的数量减去它就是答案。cls 说，不双连通的图都是由一些双连通分量组成的森林，然后就可以 dp 了。然而当时我也一直没弄明白根据这个性质要怎么去 dp（可能是因为我在冬眠吧），WC 过后我又去研究这道题，找到了“将狼踩尽”大佬的题解和代码，花了挺久的时间终于看懂了他的更加巧妙的思路，但是由于代码能力太差，就把他的代码几乎照抄了一遍过掉了。然后快三年过去，我再看到这道题，有点记忆混乱，以为自己当时是自己重新写的代码，然后就…非常的尴尬了。）

重新回到这道题目，因为由双连通分量组成的森林其实还不太好算，考虑再转换一下问题，求连通的子图的数量，然后减去连通，但是不满足双连通的子图的数量。

先考虑如何求连通的子图的数量，令 \(g[s]\) 表示令集合 \(s\) 中的所有点连通，且只存在 \(s\) 集合内部的点之间连的边的子图（为了方便叙述，后面提到的与集合 \(s\) 有关的子图都默认要求满足这一条件）的数量。

同样从反面考虑，令原图中集合 \(s\) 内的点之间的边的数量为 \(edge\_cnt[s]\),则 \(\displaystyle g[s]=2^{edge\_cnt[s]}-\text{令 $s$ 不连通的子图数量}\)。如何计算令 \(s\) 不连通的子图数量呢？我们枚举 \(s\) 中编号最小的点所在的连通块 \(s_1\)，然后集合 \(s-s_1\) 内部可以任意连边，但是不可以向 \(s_1\) 内的点连边，这样得到的子图中 \(s\) 显然都是不连通的。

然后来考虑如何求连通但是不满足双连通的子图数量，我们可以将其看成一棵以一个双连通分量作为根，其余的点组成的若干个连通分量连向它，的一棵深度为 \(2\) 的树。

令 \(h[s_1][s_2]\) （\(s_1 \land s_2 = \emptyset\)）表示不考虑集合 \(s_2\) 内部的连边，将 \(s_1\) 中的点分成若干个连通分量，每个连通分量向 \(s_2\) 中的点连恰好一条边的方案数。

那么，如何去计算 \(h[s_1][s_2]\) 呢？首先，边界条件为 \(h[0][s]=1\)。枚举 \(s_1\) 中编号最小的点 \(i\) 所在的连通分量 \(s_3\)，同时要保证 \(h[s_1-s_3][s_2]\) 已经计算完毕，这样就可以算出 \(s_3\) 中的点作为一个连通分量，使得 \(s_1\) 按上述方式连向 \(s_2\) 形成树的方案数： \(h[s_1-s_3][s_2]\)乘上 \(s_3\) 集合内部连通的方案数 \(g[s_3]\)，再乘上从 \(s_3\) 中某一个点向 \(s_2\) 中某个点连一条边的方案数 \((edge\_cnt[s_2+s_3]-edge\_cnt[s_2]-edge\_cnt[s_3])\)。

令 \(f[s]\) 表示使 \(s\) 中的所有点属于同一个边双连通分量的子图数量，则 \(f[s]=g[s]-\text{令 $s$ 不双连通的子图数量}\)。根据上面的分析，我们来计算令 \(s\) 不双连通的子图数量。枚举 \(s\) 中编号最小的点 \(i\) 所在的双连通分量 \(s_1\)，则以 \(s_1\) 为根形成树的方案数为 \(f[s_1]\times h[s-s_1][s_1]\)。

其中时间复杂度的瓶颈在于计算 \(h\) ，要枚举 \(s=s_1+s_2\)，然后枚举 \(s\) 的子集 \(s_1\)，再枚举 \(s_1\) 的子集 \(s_3\)，总的时间复杂度为 \(O(4^n)\)。空间复杂度因为要记录 \(h\) 数组，也是 \(O(4^n)\)。

B. Rotate

题目大意：给出若干次旋转，问这些旋转等价于绕哪一点旋转多少弧度。

题解：找两个不同的特殊点模拟一下得到它们旋转后的位置，然后再求一下两条线段的中垂线的交点，就是旋转中心。选到旋转中心的概率几乎为 \(0\)。

C. Overt

题目大意：给你一个 hash 函数，包括 +=,-=,&=,|=,^= 五种运算，在 unsigned int 意义下进行，问初值取遍 \([0,2^{32})\) 时，结果的最大值是多少。

题解：做过 codeforces 上一道差不多的：codeforces 778E

我们考虑从低位到高位进行计算。假设当前在计算第 \(i\) 位，容易发现第 \(i\) 位以后的计算结果不影响 \(i-1\) 以前的位。同时如果第 \(i-1\) 位的进位情况确定了，那么枚举初值的第 \(i\) 位是 \(0\) 还是 \(1\) 以后，第 \(i\) 位的答案和进位情况也就完全确定了。

还注意到，进位只在加减法中产生，并且减法可以转换为加法，相邻的加法可以合并，因此转换后最多有 \(20\) 次加法。所以就可以状压 \(dp\) 了。设 \(dp[i][j]\) 表示当前进行到第 \(i\) 位的计算，第 \(i-1\) 位的计算中，产生了进位的加法计算的集合为 \(j\) 的状态下前 \(i-1\) 位的最大值，转移很简单。复杂度 \(\mathcal{O}(n2^{\frac{n}{2}}\cdot 32)\) 。有些卡常，实现时要非常小心。

D. Clone

题目大意：求 \(n\) 维欧式空间中一个超矩形中整点组成集合的最大反链。

题解：结论题。答案是满足 \(\displaystyle 0 \le x_{i} \le t_{i}, \sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor\) 的 \(x_{i}\) 组数。在本题的数据范围下用背包 \(dp\) 加前缀和优化就水过去了。

E. Walk

题目大意：有一个连通的简单无向图。在每个点都有相等的概率到达邻接的点。对于每个点，输出：等概率选择起点，走 \(d\) 步（可以经过一个点多次）的路径不包含它的概率。

题解：\(dp_x[i][j]\) 表示从点 \(i\) 走了 \(j\) 步，不经过 \(x\) 的概率。简单的转移方程：

\[ dp_x[i][0] = \frac{1}{n}, i\neq x\\ dp_x[v][j] = \sum_{u\rightarrow v}dp_x[u][j-1]/ deg_u, u,v\neq x \]

F. Tree

题目大意：给出一个 \(n \leq 10^5\) 个节点的带点权的树，要求维护 \(m \leq 10^5\) 次以下四种操作：

• 删去一条 \(x\) 到 \(y\) 的边，再添加一条 \(a\) 到 \(b\) 的边，保证操作之后仍然是一棵树
• 将 \(a\) 到 \(b\) 的路径上的所有点的点权都变为 \(x\)
• 将 \(a\) 到 \(b\) 的路径上的所有点的点权都加上 \(x\)
• 问 \(a\) 到 \(b\) 的路径上的所有点的点权的严格次大值，出现次数，不存在输出 "ALL SAME"。

题解：用 LCT 来维护树的形态改变，然后顺便用 splay 维护次大值。具体来说需要记录子树的大小，最大值，最大值出现次数，次大值，次大值出现次数，然后再维护两种修改标记以及它们的合并就可以了。复杂度 \(\mathcal{O}(n\log{n})\)。

G. Osu!

签到题

H. KAMI

unsolved

I. Compromise

题目大意：两个人在一个 \(DAG\) 上玩游戏，度为 \(0\) 的点对两个人分别有一个价值，其它点属于且仅属于其中一个人。两个人从 \(1\) 开始走，轮到谁的点就谁走，两个人的策略是让自己的价值最大，而不管对方。问：

• 第二个人能得到的价值是多少
• 若第二个人不再遵循价值最大的策略，而是可以为自己的点任意指定一个确定的后继结点，第一个人的策略不变，那么第二个人最多能得到多少价值

题解：

第一问直接按拓扑序 \(dp\) 。

第二问，设 \(dp[i][j]\) 表示从第 \(i\) 个点开始走，是否有一种方案能走到第一个人的价值为 \(j\) 的点，那么答案为 \(\max\limits_{dp[1][j]==true}j'\)，其中 \(j'\) 是 \(j\) 对应点的第二个人的价值 。转移方程为：

\[ dp[i][j]=\left\{ \begin{aligned} &[j = value[i][1]],&deg^{+}(i)=0\\ &\left( \bigwedge_{u,i\to u}\bigvee_{k\le j}dp[u][k]\right) \land \left( \bigvee_{u,i\to u}dp[u][j]\right) ,&type[i]=1\\ &\bigvee_{u,i\to u}dp[u][j],&type[i]=2\\ \end{aligned} \right. \]

J. Resistance

unsolved

Replay and Summary

Replay

来到机房先把签到题 G 给过了，然后 D 发现 A 是一道做过的原题，cls 在冬令营上讲过。于是就翻出代码抄了一遍提交了，没想到当年写代码的时候也是抄的别人的。不管当年是不是自己写的代码，遇到一道做过的题的时候，还是应该重新思考重新写一遍。直接抄确实是一个严重的错误，感谢昂神指出来，以后一定避免相同的事情发生。

然后 Z 发现 D 是一道求偏序集的最长反链的题，之前在 bcpc 的预赛中用这种方法做过一道题（标程是枚举）。拿过键盘写了就过掉了。

Z 看了 B 题是一道几何题，接锅之后就开始写了。写的途中 W 一直在用矩阵想 E，仔细写了写式子发现矩阵转移不了，直接暴力地枚举删点然后 dp 转移即可。这个时候 Z 把 B 写得差不多了，就让出键盘在旁边静态查错，W 写了之后过了样例一发 ac。Z 也过来改了几个地方也 1a 了。

这个时候时间还剩的比较多，D 看没人碰键盘就过来用 LCT 写 F。 W 和 Z 各自在想 I 和 C。I 的题面非常长，而且题目有些细节没有描述清楚。W 和 Z 讨论了一会儿之后，觉得就是一个暴力的 dp。等 D 写得差不多的时候，接过了键盘开始写 I。

过了很久之后，Z 找到了 I 的一个小错误，wa 了一次之后又改了改过掉了。D 这时也发现 F 题修改的时候没有修改当前节点的权值，改了之后也 ac 了。

最后剩的几道题中 C H 毫无头绪，然后 J 题虽然看出了是一个电路题，用基尔霍夫定理应该可做。但是三人的电路都学得很差，讨论了半天也没个结果。说明还是有很多知识点上的缺失，各自分锅之后加入 todo list 以后慢慢补上。

coldwater

在队友疯狂过题的空隙中找到了摸键盘的机会，把 E 水过去了。然后看 J 题，显然是用基尔霍夫定律怎么缩点之后解个方程组，然而已经不会物理了。F 题裸 LCT 也不怎么会写了真的是 afo 太久了还得好好康复训练啊。

ShinriiTin

首先很抱歉比赛一开始就去抄了 A 的代码。 然后 W 让我看 F，我看了之后觉得是 LCT 题，因为队里只有我会写，我就接过锅来写。写了挺久也调了挺久的，还好调过样例之后就 a 掉了。今天比赛结束之后准备把自己写的 LCT 整理成方便用的模板，这样以后场上不至于浪费太多时间。 J 我感觉很僵硬，应该要去找一些电路的题来学习一下了。

zhongzihao

今天题比较友好，所以做的就很爽。 B 题和 D 题都很水，所以过来很快就 a 了，然后感觉 C 和 I 能做，过了好久以后想出了 I 是个 dp 然后写了一会 wa 了一发也 a 掉了（本场唯一一次 wa，我好菜啊.jpg）。然而剩下的一道 C 直到最后也没有头绪，并且最后一段时间又开始摸鱼了，虽然每次都觉得这样不好，但是实在想不出来也是很绝望的。虽然这次 a 了 B 这个勉强算是计算几何的东西，不过这题太水了，还是远远不够，继续刷题。