CCPC 2015 简单题解

本篇简单描述一下 CCPC 2015 决赛的题解（非官方）。

Secrete Master Plan

Tags: 杂题

把输入的格子数字按顺时针或者逆时针顺序放到两个数组中，然后用 for 循环判断能不能通过 shift 来使得两个数组相同。

Build Towers

Tags: 启发式搜索

把状态进行 hash，然后跑 A* 或者 IDA*，一个简单的估价函数可以是

$$h(s) = size - 6$$

其中 $s$ 是状态，$size$ 是当前状态中单独块的个数，比如说 $0-1$ 算是 $1$ 块，$0-1,3-5$ 算是 $2$ 块。

一个比较好的优化是，把每个塔进行排序，行按照塔上木棍的数量从小到大，一样的时候，按字典序，这样可以把重复的状态减少。

The Battle of Chibi

Tags: 数据结构 动态规划 图论

定义状态 $dp[i][j]$ 表示选了 $i$ 个考虑到了前 $j$ 个，这 $i$ 个是严格递增的方法数，转移方程：

$$dp[i][j] = \sum_{a_k < a_j}(dp[i - 1][k])$$

这里的转移可以用树状数组进行优化，转移是 $O(\lg N)$ 的，总体复杂度 $O(N \cdot M \lg N)$。

Pick The Sticks

Tags: 动态规划

把金条按长度从大到小排序，定义状态 $dp[i][j][k]$ 表示考虑到前 $i$ 个金条，选了 $j$ 个，它们的长度和是 $k$，可以获得的最大价值，直接 0-1 背包就可以，其中 $j$ 是 0-2 的，如果 $j$ 是 $0$ 或者 $1$，那么新选择的金条有效长度减半，否则就用原长。由于这题说的是重心，为了方便处理，可以把所有的长度乘以 $2$ 方便转移。

Ba Gua Zhen

Tags: 数学 图论

先构建一棵生成树，对于所有的非树边，求出对应的简单环的异或和，这样我们可以得到 $M - N$ 个数，最后这题的问题就可以转化为给 $M - N$ 个数，选出一些数出来，使得异或和最大。这个可以用类似高斯消元的思想在 $O(60 \times (M - N))$ 时间内求得。

The Battle of Guandu

Tags: 图论

根据题意可以构建出一个不等式组，把这个不等式组，求个对偶形式，可以发现模型由一个单纯形的问题转化成了差分约束系统，可以建图跑最短路得到答案。

Ancient Go

Tags: 杂题

对于每个白子跑 DFS 或者 BFS 找气，只要气是 (1) 就说明下一步可以吃子。

Sudoku

Tags: 搜索 暴力

简单的搜索或者枚举就可以。枚举的话就直接枚举每一行的排列是什么然后判断，排列方式只有 $24$ 种，最暴力的做法也就 $O(24^4 \times N^2)$。

Mahjong

Tags: 动态规划 状态压缩

动态规划，定义 $dp[i][j][s]$ 表示考虑到第 $i$ 种牌，一共用了 $j$ 个，$s$ 表示一个压缩的状态，这个状态记录的是一个三元组 $(i,j,k)$，表示考虑到 $i$，其中 $i-2$ 剩下了 $j$ 个，$i-1$ 剩下了 $k$ 个，这样的状态定义可以比较方便处理重复的情况。其中对于每个状态，$s$ 的值是很少的，这里可以直接预处理出来合法的 $s$。

Walk Around The Campsite

Tags: 几何 动态规划

对于每一个点，我们都要知道站在它位置上可以 “看到” 哪些点，这里将所有的线段拆分成三种事件，一种是一个发现了一个新的线段，一个是一个线段将要被删除，还有一个是查询一个点是不是能从中心点看到。由于所有的线段最多只会在端点相交，所以我们可以用平衡树维护线段的序，平衡树的 key 是沿当前角度上从中心点看，这个线段到中心点的距离，值是线段，这样对于查询点的事件，我们只要看它是不是在最近的线段上就可以了。

处理完有效的信息之后就是一个很简单的转移（卧槽为毛这么多 dp）：

$$dp[i] = max(dp[k] - dist(k, i) + v_i)$$

其中，从 $k$ 可以看到 $i$。最后答案是 $max(dp[i])$。

Game Rooms

Tags: 动态规划

再吐槽下为毛这么多 dp（不

定义状态 $dp[i][j][k]$ 表示考虑到第 $i$ 层，上次和这一层一样的活动室是在 $j$ 层，当前楼层放 $k(0, 1)$ 这个活动室的最小代价。转移的时候可以处理出 $\sum{a_i}$ 和 $i \times a_i$ 然后在 $O(1)$ 时间内转移。

Huatuo’s Medicine

Tags: 杂题

签到 0.0

#! /usr/bin/env python2

T = int(raw_input())
for cas in xrange(0, T):
    print "Case #%d: %d" % (cas + 1, 2 * int(raw_input()) - 1)