ACM-ICPC 2015 regional Shanghai onsite 简单题解

发表于 分类于

本篇简单描述一下 2015 年上海 ACM/ICPC onsite 的题解（非官方）。

An Easy Physics Problem

Tags: 几何

简单几何，不过好多人说会挂精度是怎么回事。。（不管反正我只会嘴炮

注意，两个点都在圆外，而且不在圆边上，这点非常重要！

Binary Tree

Tags: 构造

好吧。。这题本来想出成不给 KK 的，但是考虑到缺中档偏简单的题而且不给 KK 输出不好控制，就给了个这么奇怪的限制。。

对于所有的奇数我们可以用 11 , 22 , 44 , ⋯\cdots , 2K2^K 这条路径进行贪心构造。

对于所有偶数的情况，由于我们已经构造出了所有的奇数，偶数就是奇数加 11 啦，所以我们可以从 11 走到 2K−12^{K-1} 然后走到 2K+12^K+1 。

时间复杂度 O(K)O(K) 。

Colorful Tree

Tags: 数据结构

先上一个可能会 TLE 的做法。。把整个树根据 DFS 序展开成线性的，然后我们可以把整个问题转化为，修改一个区间颜色，查询区间不颜色的数量。这里，如果修改的单点的话，就可以用类似 这个破题 的思路来写了。这样时间复杂度是 O(Nlg⁡2N)O(N\lg^2N) .

对于把区间更新转化成单点更新，可以考虑，由于我们每次都是更新的一整个子树，那么对于修改操作，我可以把根结点的颜色更新成我们要的颜色，对于剩下的点，我们直接暴力把它们删掉。对于删颜色的操作，最多只会有 N+MN+M 次。

查询的时候，我们先看这个区间内的不同颜色数量，再考虑，如果根的颜色是空的话，我们要找到根真正的颜色，还要看这个颜色在不在区间内。不过这个好处理，直接维护一个线段树，表示每个点真正的颜色就可以了（对于更新一个子树的颜色，就等价于更新线段树里面一个区间的值）。

最后，我们考虑怎么把时间复杂度再降一点（现场前者做法如果常数不大其实是可以过的）。对于相同颜色的结点，我们把他们按 DFS 序排好序，我们维护一个树，树上每个结点的值，表示以这个结点为根的答案，那么我们直接考虑不转线性地去维护这些答案。我们会发现，对于每个点，它的颜色只会影响到它到它祖先里面深度最大的同颜色点下面的结点的答案。但是有可能一个结点下面会有多个同颜色的点，怎么办？我们假设同颜色的 DFS 序是 aa , bb , cc , ⋯\cdots ，对于 aa 我们只认为它影响到了 aa 到 LCA(a,b)LCA(a, b) 路径上的答案，对于 bb 来说，影响到的是 bb 到 LCA(b,c)LCA(b, c) 上的答案。。。这样就可以把整个问题转化成了树上路径更新，单点查询的问题了。

最后，总体复杂度是 O((N+M)lg⁡N)O((N + M) \lg N) 。

Discover Water Tank

Tags: 动态规划

将整个 hh 数组抽象成一棵笛卡尔树，对于每一个挡板，我们从它最高点向左右划横线，直到遇到比它高的挡板停止，然后我们会发现这个图被分成了很多个长方形，这些长方形就是树的每个结点（自己画图 QUQ）。然后我们就可以在这些结点上 DP 了。

定义状态

dp[u][s]dp[u][s]

表示考虑到结点 uu ， ss 表示有水还是没水，值是最多不冲突的条件的数量。然后直接树形 DP 转移就可以了。

这个树不一定要建出来，可以用并查集抽象化就可以（当然建树并不难写就是了）。

对于每个结点，我们需要把在内部的条件预先排好序（内部有可能冲突），所以最后时间复杂度是 O(Mlg⁡M+N)O(M \lg M + N) 。

Expection of String

Tags: 动态规划

Solution I

直接 DP 每两个位置的期望，定义状态

dp[s][i][j][k]dp[s][i][j][k]

表示现在还有 kk 次交换机会，两个数位置在 ii 和 jj ，乘号在 kk ，对最后答案的影响。转移可以通过求和来达到 O(1)O(1) 。

时间复杂度是 O(N3⋅K)O(N^3 \cdot K) 。

Solution II

固定 CC 我们用 DP 算 x×yx \times y 的期望

定义状态

dp[A][b][C][k]dp[A][b][C][k]

表示当前某三个位置 i<j<ki < j < k 的值分别是 AA BB CC ，还有 KK 步要走时，
这三个位置的 x×yx \times y 的期望，边界条件为

dp[A][b][C][0] = \begin{cases}A \times C & \mbox{if }B = *\\0 & \mbox{if }B \neq *\end{cases}

于是由于 AA BB CC 分别只能是 0−90-9 以及 * 共 1111 种 然后转移的时候也只与这 1111 种的个数有关，因此可以做到 O(11)O(11) 的转移

最后答案是

∑i<j<k(dp[si][sj][sk][k]×C(i,j,k))\sum_{i < j < k}(dp[s_i][s_j][s_k][k] \times C(i, j, k))

其中 C(i,j,k)=10(j−i−1)+(N−k−1)C(i, j, k) = 10 ^ {(j - i - 1) + (N - k - 1)}

总体复杂度 O(114⋅K+N3)O\left(11^4 \cdot K + N^3\right) .

Friendship of Frog

Tags: 杂题

怎么写都可以。。数据范围 N≤1000N \leq 1000 瞩目。

时间复杂度强行 O(N2)O(N^2) 。

Game of Arrays

Tags: 博弈

  • 先计算出 A+B−CA+B-C ，得到每一位需要操作的次数，若为正，即操作 AA 或 BB ，若为负，即操作 CC 。
  • 如果初始状态等式成立，则先手赢。否则枚举先手第一步。
  • 对于每一位，判断初始时是否在等式永远不可能成立的状态，如果是，后手赢。
  • 否则判断其是否有一种方法（后手不断操作 AA / BB ，或者后手不断操作 CC ），使其永远都不能成立。
    • 如果是，判断在这种情况下（后手不断操作 AA / BB ，或者后手不断操作 CC ），先手能不能赢（即在这一位等式永远不成立之前，先手把其他位都操作成等式）
    • 如果先手不能赢，那么后手就执行这种方法（后手不断操作 AA / BB ，或者后手不断操作 CC ），后手赢。
    • 如果对于每一位，后手都不能将其操作为永远不可能成立的状态，那么先手赢。

Happiness of Frog

Tags: 动态规划

不会。。。

Infinity Point Sets

Tags: 几何 计数

其实这题需要画图强行猜个结论（不

最后满足条件的点集，只有一种，那就是一堆共线的点，加上两边最多各一个点（最多的意思是可以有一边没有点，或者两边都没有）。

但是这样不好统计，怎么办？把这个结论划分成下面几类：

  • 小于等于 44 个点，或者大于等于 55 个点并且它们共线。
  • 大于等于 44 个点共线，加上其中一侧有一个点。
  • 大于等于 33 个点共线，加上两侧各有一个点。

我们枚举一个点，把所有点极角排序，对于第 2 种情况可以直接算出来，对于第 3 种情况，我们假设这个枚举的点是四边形的中心，这样可以把四边形加上对角线交点这种会重复算的去掉。

时间复杂度 O(N2lg⁡N)O(N^2 \lg N) 。

Journey of Taku

Tags: 图论 最短路

首先如果 Taku 使用了第二种魔法，那么有 KK 步的移动是可以确定的，于是我们记录每条边走完后，通过第一种魔法下一步是哪条边，这样可以倍增算出 K 步后在哪儿，于是可以直接建图，求最短路即可。

重要的话一定要加粗说！答案会爆 int，另外题意有毒！

时间复杂度 O(Mlg⁡K)O(M \lg K) 。

Kingdom of Black and White

Tags: 杂题

直接枚举修改哪个点，我们可以先算出原来的答案，然后修改一个点只会影响到相邻的两个连续段，直接算修改后对答案的影响就可以了。

时间复杂度 O(N)O(N) 。

LCM Walk

Tags: 数论（假）

对于 (x,y)(x, y) 走到 (x+z,y)(x + z, y) 或者 (x,y+z)(x, y + z) 。由于 z≥xz \geq x 且 z≥yz \geq y 。我们可以算出来 (ex,ey)(e_x, e_y) 的前驱。实际上前驱是唯一确定的，所以直接模拟就可以。

时间复杂度 O(lg⁡(max⁡(ex,ey)))O(\lg\left(\max(e_x, e_y)\right)) 。