0%

CCPC2015 简单题解

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

1
2
3
4
5
#! /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)