AC. 梦想

frank_c1

[ZJOI 2014] 璀璨光华

发布于2016年04月10日 | 暂无评论 | 877阅读 | 搜索

题目描述

金先生有一个女朋友——没名字。她勤劳勇敢、智慧善良。金先生很喜欢她。为此,金先生用a ^ 31 \times 1 \times 1的独特的水晶制作了一个边长为a的水晶立方体。他要将这个水晶立方体送给他见过最单纯善良的她。

由于水晶立方体太大,不好运送,金先生还是将它拆开来送出。他相信拼好这个水晶立方体难不倒聪明的她。

没名字收到了礼物后果然不一会儿就根据说明将水晶立方体拼好了。没名字发现,有n块水晶在漆黑安静的夜晚会随机向上下左右前后六个方向的一个发出光。被光照到的水晶显得格外好看。没名字给每一块不会发光的水晶定义了一个好看程度。水晶立方体在夜晚中的好看程度就是每块被光照到的水晶的好看程度之和。没名字想知道,水晶立方体在夜晚中的好看程度的最小值和最大值。

输入格式

输入文件glitter.in的第一行是a,表示水晶立方体的边长。

接下来a ^ 3行,每行若干整数。第一个整数g[i],表示第i块水晶的好看程度。如果g[i] = 0,代表这块水晶会发光。接下来3 - 6个整数,代表与这块水晶有公共面的水晶编号。

n \le 8, a \le 70, g[i] \le 1000000

输出格式

输出文件glitter.out总共一行,两个整数,水晶立方体在夜晚中的好看程度的最小值和最大值。

题目解析

说这题难,其实也不难;说这题不难,也确实在当年坑过不少神犇。

首先,输入格式令人十分不爽,我们考虑把立方体建出来。记一块水晶x相邻的数目为D(x)。可以从某一D(x) = 3的水晶(坐标记为(1,1,1))开始搜索,搜到一块水晶x时,若它相邻的水晶中有D(x) - 3块位置确定,那我们就可以尝试确定x的位置。随便怎么确定都行。

建出立方体后,可以直接统计答案。怎么统计呢?6 ^ n爆搜即可。