sakuya. Luna Dial

sakuya. Luna Dial

ZOJ3382. 月時計 ~ ルナ・ダイヤル

downloadsource code (ZOJ3382.cpp) [表达式解析(parser), 树形DP]

题目Luna Dial即ルナ・ダイアル取自《东方红魔乡》第五面BOSS战十六夜咲夜的theme《月時計 〜 ルナ・ダイアル》,所以题目自然和女仆长有点关系了。其实主要还是因为描述和样例中选取了时间操作作为例子,所以很自然地就想到了女仆长。女仆长在《东方花映冢》的theme《フラワリングナイト》(flowering night)的Arrangeナイト·オブ·ナイツ(night of nights)也是鬼畜音乐的代表作之一。(鬼畜音乐的最高代表自然是二小姐的theme《U. N. Owenは彼女なのか》,神主さま……)略鬼畜什么的最讨厌了,所以放个比较美的MAD吧:
(nico)【第3回MMD杯本選】Dial Connected 月時計~ルナ・ダイアル【東方PV】.mp4

Get the Flash Player to see the wordTube Media Player.
  • 紅魔館のメイド/完全で瀟洒な従者/十六夜咲夜(いざよい さくや)

题目给你ntype≤4种数据类型,nop≤6种二元运算符,包括运算符的优先级和结合性,neq≤种二元合法运算及其结果类型,最后对每个表达式,要求其产生各种运算结果的不同方法。表达式里有一种特殊的,优先级最高的运算符”/”,表示“或”。

首先要做的就是把表达式解析成一个二叉树,这需要一个比较通用的Parser,根据优先级(precedence)和结合性(associativity),将一个含有各种空白(包括空格和TAB)的字符串转为二叉树。注意运算符也可能是一个string,而不是char。Parser的复杂度应该是O(length)的,可以用堆栈实现,此题数据规模较小,所以递归也没有问题,时限也放得很宽,但有卡O(n^2)算法的数据。我的程序写的比较差,quark的程序速度是我的4倍多,内存差不多是我的1/5,而且不会有爆栈问题。

有了一个二叉树,那么求解答案就是一个很简单的树形DP了,每个节点都是一个vector<int>记录改子树对应的表达式算得各种类型结果的不同方法数。对于叶子节点,改节点对应的类型为1,其它皆0。对于”\”对应的节点,结果就是两个vector的和。而对于其它二元运算的节点,则要根据题目所给的二元合法运算及其结果类型求出结果,比如在”+”对应的节点有x=a+b,那么this[x]+=left[a]*right[b]。

题目在算法上没什么复杂的,主要的难点在于表达式解析,代码量是所有题里最大的,而且debug要花不少功夫。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

3 Responses to “sakuya. Luna Dial”
  1. jing says:

    题目好长 》。。《

  2. quark says:

    今天又重新搞了一下,交到 ZOJ 上面,又快了一点 – -

  3.  
Leave a Reply