ZOJ Monthly, July 2009

[F]ZOJ3227 Perfect Cherry Blossom 0.00% (0/13)
[H]ZOJ3229 Shoot the Bullet 12.12% (4/33)

ZOJ Monthly, November 2009

[E]ZOJ3263 Immaterial and Missing Power 0.00% (0/8)

标题是照着vls的《我出过的题目》取的,确切的说是我出过的以東方Project为背景的,已经公开的题目。因为今年Summer2010暑期集训新手上路选拔和七月校队选拔中,我又出了11道东方系列的题目,以在这个月办好一场东方专场ZOJ月赛(详情:acm_x_touhou),用把力,把去年暑假的yy变成现实。去年出的这三题当然离办一场Monthly还有无限远,不过今年提前准备,再加上vout和猛犸的强力支持,现在已经有了充足的各种难度,各种类型的东方系列备选题目能够支援ZOJ八月的月赛了。届时希望广大acmer和touhou fans捧场 :D

ZOJ3229 Shoot the Bullet (文花帖)

downloadsource code (ZOJ3229.cpp) [FlowNetwork, 上下界最大流]

在未来的n天中,文文要强拍幻想乡的mm们为《文々。新闻》增加8g素材。但是每天她只能对某些mm拍照,并且所拍照片数不能过多或过少,每天总的照相数也有上限,而n天内她所拍某个mm的相片也有最低要求。在满足所有这些要求的前提下,希望最后拍的照要尽量多,求任意一个最优方案。

很裸的上下界最大流,构图算法都没什么需要多说的了,有模块就直接秒杀了。ZOJ上就这题的AC数到了三位数,不知道有没有人用来测模块。

ZOJ3227 Perfect Cherry Blossom (妖々夢)

downloadsource code (ZOJ3227.cpp) [DP, SegmentTree]

 暖和的季节结束了,边境被银白色的幻想所封闭。
 人们在这不知道什么时候结束的漫长冬天中,也变得安分起来了。

 但是,活泼的狗还有妖怪们和这并没有关系。
 没错,这里,幻想乡原本就没多少人类,而且在冬天,冬之妖怪也会吵闹起来。

 渐渐地,到了雪融化,银白色的飞雪变成樱花烂漫的季节。
 幻想乡也并不例外地到了本该是暖和起来的季节。

 到了5月,春天却没有到来。

 普通的魔法使,雾雨魔理沙和普通人类一样,
 对于严寒也相应地很讨厌,却从中享受着另一种乐趣。

 魔理沙:“虽说很普通,不过也不是讨厌春天啦。”

 雾雨宅因为有魔暖房的缘故而很暖和。
 不过即使不这样魔法室也是某种暖和的地方。

 魔理沙:“因为这场雪,就不能去神社玩了啊。”

 少女看见了自己家门前的飞雪中,夹杂着桃色的花瓣。
 这是只在这里东方的国家才会开放的花的花瓣。对,是樱花。

 魔理沙:“难道,冬天是只存在于这里吗?
 不对,已经5月了啊,因为太冷而没发现到!”

 如果去上风处应该可以找到开放的樱花。只是,雪是从山上吹下来的。
 而原本山上的樱花就应该比平地迟的……
 少女沿着樱花的花瓣,为了寻找还看不见踪影的春天而出发了。

摸你傻从y=-1移动到y=S,每次y++,x可以在[0,w)范围内移动,但是会产生a*abs(x2-x1)的花费,然后撞弹扣分,收集道具加分,目标是亿万长者。

注意s很大而n很小,没有子弹或道具的y是没有意义的,所以先离散化。简单的dp方程是dp[i+1][j]=max{dp[i][k]+a*abs(k-j)},但复杂度是O(w2n)的。然后可以在转移过程中通过对k<j和k>j两种情况分类讨论,预处理后一行一行地转移,复杂度是O(wn)的。处理的关键是对于向右移动的情况,从k=0->w扫描,但不是记录下max{dp[i][kk]|kk≤k},而是记录tmp[k]=max{dp[i][kk]+a*kk|kk<k},这样就可以O(1)得到max{dp[i][k]-a*(j-k)|k<j},对于向左移动时,类似地处理。

正确的算法复杂度应该是O(lgw*n)的,做法和O(wn)的类似,注意到n相对很小,每次需要更新的值不多,但却要浪费O(w)的时间预处理,所以引进线段树优化之。类似上面的情况,需要分向左和向右两个线段树,这个线段树只要支持最基本的区间最大值查询和对一个点的值的更新就可以了,应该是最简单的线段树了。这样可以在O(lgw)得到max{dp[i][kk]+a*kk|kk<k}和max{dp[i][kk]-a*kk|kk>k},然后得到新的dp[i+1][k]。注意转移时不能一个点一个点更新,要整行整行地更新,从(x1,y)到(x2,y)的移动是非法的。

ZOJ3263 Immaterial and Missing Power (萃夢想)

downloadsource code (ZOJ3263.cpp [parameter search, shorest path]

 萃まる夢、幻、そして百鬼夜行。

题目说的就是西瓜打算集合幻想乡的少女们到博丽神社召开宴会,幻想乡可以看成一个无向图,每为少女都有自己的默认速度V和一个属性A,并且她每次走到一个地方,就会逗留时间Tj。西瓜可以动用她操纵密与疏的能力,她花费ci的灵力可以让少女速度增加A*sqrt(ci),不过改变不了她逗留的时间。不过她总共只有C的灵力可作分配。

首先想到可以二分答案,二分时间T内是否可以让所有少女走到博丽神社。而为了判断这一点,需要对每个少女求出至少要花多少灵力来加速她,这又是一个二分,二分ci,求最短路,看看是否不超过之前二分的时间T。于是问题就是一个二分里套n个二分,里面又是一个最短路。由于对不同的ci,最短路径是不同的,所以每次都要重新求最短路。

5 Responses to “我出过的东方系列题目”
  1. VegetableB says:

    为什么不等那次月赛出来之后再写?

  2. Fancy says:

    只做出过一道>_<

  3.  
Leave a Reply