ZOJ Monthly, December 2010
A ZOJ3446 Doraemon’s Battle 13.84% (54/390)
B ZOJ3447 Doraemon’s Number Game 29.66% (35/118)
C ZOJ3448 Doraemon’s Number Game II 0.00% (0/4)
D ZOJ3449 Doraemon’s Number Game III 18.77% (40/213)
E ZOJ3450 Doraemon’s Railgun 11.28% (22/195)
F ZOJ3451 Doraemon’s Shooting Practice 8.33% (2/24)
G ZOJ3452 Doraemon’s Stone Game 33.89% (20/59)
H ZOJ3453 Doraemon’s Sweet Bullet 25.00% (5/20)
I ZOJ3454 Nobita’s Letter 36.36% (8/22)
J ZOJ3455 Shizuka’s Letter 27.95% (26/93)
K ZOJ3456 Traveler Nobita 7.50% (3/40)

ZOJ3446. Doraemon’s Battle

downloadsource code (ZOJ3446.cpp) [search, bfs]

Doraemon初始有lh的血量和0的技能值,有n个敌人,他每回合有4种选择:

  • 消灭一个敌人并增加一个技能值;
  • 回复lh/5血量;
  • 用尽现有技能值s,打掉Ds个敌人;
  • 不动。

Doraemon回合之后,若剩下m个敌人,则其血量减少m,技能值增加m%3。Doraemon的血量若小于等于0,就挂了。问最少多少回合消灭所有敌人。

不动这个选择显然是没有好处的。只要从初始状态出发,用[h][s][n]标记走过状态,bfs就可以了。注意D数组不一定是递增的,所以每一步都要尝试三种可能的操作,过度的剪枝可能会WA。不过有一个很有效的剪枝就是:“实际上对于相同的敌人数与技能值,HP越多越好,因此只要记录HP最多的状态就可以了”(by pxhdg)。加上这个剪枝之后,原本350ms的程序一下减到了10ms。

ZOJ3447. Doraemon’s Number Game

downloadsource code (ZOJ3447.py) [greedy, BigInteger]

贪心。结果最大的策略就是:不断最小的两个数,计算后放回数集之中;相反的,结果最小的策略就是:不断取出K个(如果不足则取出全部)最大的数,计算后放回数集之中。题目结果很大,需要高精度。

ZOJ3448. Doraemon’s Number Game II

downloadsource code (ZOJ3448.java) [counting, number theory]

求满足以下两个条件,长度为n的b进制数的个数分别是多少

  1. x移除s~t(3≤s≤t≤n)位之间的某一位得到y,使得x % y == 0
  2. x移除最左边的一位得到y,使得x % y == 0

假设移除了第p位,设x=ibp+1+jbp+k,那么y=ibp+k,又x%y=0知道(x-by)%y=0,即|jbp-k(b-1)|%|ibp+k|=0,我们知道分子小于bp+1,而因为3≤p,所以i>p,所以分母大于bp+1,所以分子等于0,即jbp=k(b-1),所以j=k=0。而对于任何以个形如i*b(n-t+1)的n位数,我们总能去掉其第t位,使得x=by。所以答案就是(b-1)bt-2,和s无关。

对于第二问,设x=ibn-1+j,那么y=j,又x%y=0知道(x-y)%y=0,即ibn-1%j=0。所以我们先枚举i=1~b-1,然后要求满足j<bn-1的约数j的个数。这等于ibn-1的约数个数减去那些大于等于bn-1的约数个数,将ibn-1分解质因数后这二者都很容易求得。

ZOJ3449. Doraemon’s Number Game III

downloadsource code (ZOJ3449.cpp) [number theory, BigInteger]

将一个十进制数一直按b进制解释转成十进制,b小于10,于是最后变成一个数字,问这个数字是多少。

\sum_{i=0}^{n-1}{d_i10^i}\equiv\sum_{i=0}^{n-1}{d_ib^i}\pmod{10-b}

于是我们知道对10-b求模是关于这种运算的不变量,可以发现答案就是b+(n-10)%(10-b)。不过特别的,对于n<10,答案就是n。这题数据量很大,Java可能会TLE,一个优化是只要对lcm(1..8)=840求一次模就够了。当然,还有这种更BT的写法(downloadZOJ3449delta.cpp)。

ZOJ3450. Doraemon’s Railgun

downloadsource code (ZOJ3450.cpp) [DP, geometry, Knapsack]

攻打来袭的敌人,攻打第i组敌人耗时Ti,可以消灭敌人Wi,求在T0时间内最多可以消灭的敌人数,但有一个限制条件:告诉了每组敌人坐标和自己的坐标,对于位于一条线上的所有组敌人,每次攻打只能攻打离自己最近的那组。

首先要做的事就是合并共射线的点,对于x, y, g = gcd(|x|, |y|),那么我们可以用(x, y)代表这个射线,而g正好可以代表这个距离。对于同一条射线,按g排序后,只有在第1到k-1个都取了的时候才能取第k个,不妨做一个部分和,那么就变成在多个里只能选一个。最后就是一个背包问题了。尽量避免使用浮点数,会有精度问题。验题的时候似乎发现,有的人的程序会死在T=0上。

ZOJ3451. Doraemon’s Shooting Practice

downloadsource code (ZOJ3451.cpp) [math, physics, simulation, if-else]

足球射门练习。给出足球起点坐标,初速度大小,初速度方向,问球能不能进。

题目保证没有边界数据,不用关心EPS,只要模拟就好了。不过还是有几种情况需要考虑的,代码里都有注释,就不在这里细说了。

ZOJ3452. Doraemon’s Stone Game

downloadsource code (ZOJ3452.cpp) [game-theory, greedy, off-by-1]

有很多堆高度不超过2的石头,石头有两种颜色,A只能拿白色的石头,B只能拿黑色的石头,如果拿的是最底下的石头,那么那整一堆石头都会崩溃掉。轮流取,直到有一个人没法取了,另一个人就赢,要求根据给出的石头的信息(每种石头堆的数量),判断A是先/后手时的是必胜还是必败。

很显然一堆w可以为A争取一回合,一堆ww可以为A争取两个回合,对B类似,而且他们都不会受到对方的影响,所以是可以留到最后取的。于是关键在于wb和bw的争夺了,假设wb和bw数量都不为0,那么首先对方做什么有利的操作,自己也可以对称的做相同的操作,格局不变,所以首先要将wb和bw抵消掉。接下来考虑只剩wb,那么对于A来说,显然要先取其中的w,减少对方能取的b;而对于B来说,也会先取其中的b,避免这种减少。那么分析以后就会发现,n个wb对于A来说总是n个回合,但是对于B来说,如果A先手,只有n/2个回合,否则有(n+1)/2个回合。最后比的就是谁的回合先用完。

ZOJ3453. Doraemon’s Sweet Bullet

downloadsource code (ZOJ3453.cpp) [SegmentTree]

n个敌人站成一排,每个敌人有l[i]的血,区间[a[i], b[i]]都是第i个敌人的朋友。Doraemon依次发射m个糖衣炮弹,第j个会攻击下标最大的血量不少于k[j]的敌人,如果没有则跳过。假设i受到攻击,那么首先l[i]减小至1,然后l[a[i] .. b[i]]都增加1。问最后的max{l}。

直接在线段树上一步一步模拟。线段树需要支持点等于1,区间加1,查询最大值,查询最大的大于给定值的下标等操作。为了在保证复杂度不退化的前提下实现这些操作,我们在每个节点上维护两个值x和y,其中x记录的是区间的最大值,y记录的则是该区间又加了几次1。引入y的原因和引入懒标记有点类似,无论是点等于1,还是区间加1,我们每次都用x[p]=max(x[L(p)],x[R(p)])+y[p]来更新一下x的值。除此以外,所有操作就和最常见的线段树没有区别了。具体实现可以看代码。

ZOJ3454. Nobita’s Letter

downloadsource code (ZOJ3454.cpp) [graph, LCM]

给定一种映射f,问一个序列通过任意次映射的复合,可以得到多少不同的文本,相当于求#{fi}

首先将映射转成一个有向图,我们知道所有的点的出度都是1,所有它应该是由很多ρ字型组成的。或者说,对于图上每一个点i,沿着边走x[i]步后,都会进去一个大小为y[i]的圈,所以答案就是max{x[i]}+lcm{y[i]}。注意lcm(a%m,b%m)!=lcm(a,b),所以求lcm的过程中是不能求模的,一个可行的办法是先对所有y[i]分解质因数,最后求lcm的时候再取模。

ZOJ3455. Shizuka’s Letter

downloadsource code (ZOJ3455.cpp) [counting, statistics]

有一种加密方法,对于字符串P,首先将字符串中的字符进行替换,然后可以对位置进行交换,最后将它插入另一个字符串中间获得加密串T。然后对于一对T与P,求T是否可以为P的一个加密结果,若是则求所有的加密位置。

首先只考虑替换和交换这两步,那么会知道,这样变化后会满足出现i次的字母的个数l[i]是不变的,反之,如果满足这个条件,则一定可以通过替换加交换得到。而从位置j到位置j+1,多了一个字符T[j+n],少了T[j],所以最多有两个l[i]发生了变化。如果我们用一个变量k,记录有多少l[i]与P的一致,那么k==SIGMA的时候,就是一个合法的位置。每一步,这些变量都可以在O(1)的时间内得到维护,所以总的复杂度是O(n)的。

ZOJ3456. Traveler Nobita

downloadsource code (ZOJ3456.cpp) [graph, MST, trick]

每个点和边都有权值。点是本来就有的,边是从最开始一条都没有按题目给的顺序每一年增加一条的。现在有一个人要从0点出发,走遍所有其他点(可以走多次)最后回到0点。问对于对于每一年是否能制定出一个在一年内走完的计划,并求花费。每经过一条边则花费对应的权值,每到一个点则花费对应权值。题目有一个限制条件是那个人只能有N-1条路的通行证。

由题目知道,所走的边构成一棵树,如果我们把所有边的边权改成路的权值的两倍加上所连接点的权值,那么我们会发现,这棵生成树的大小就是所花费的时间。所以题目就是要不断的求对应的最小生成树。不过这题还有一个trick,就是要注意闰年是有366天的,有可能MST的大小正好在区间(365, 366],于是……

12 Responses to “[题解]ZOJ Monthly, December 2010”
  1. agralol says:

    3450的dp扩展的时候t的增量可能等于0,不注意还真容易WA。。

  2. Yuan says:

    请问下,3454. Nobita’s Letter这题
    入度应该有可能大于2吧,应该ρ有可能是多叉的?

  3. jing says:

    3447好难写~~~~(>_<)~~~~

  4. zsasuke says:

    3448题,x怎么能表示成x=ib^(p+1)+jb^p+k呢???
    例如:
    x=2321234234,10进制;
    x=ib^(p+1)+jb^p+k=23*10^8+2*10^7+1234234,我想移除第7位,移除后y=232123234,也就是y=ib^7+k=23*10^7+2123234
    这2个表达式的k根本不相等啊,到底是怎么回事呢?

    • zsasuke says:

      也就是说这题,在题目里,你的移除的第p位是从左到右算的,但是,解题报告里却是从右到左算的,搞反了,不对啊

  5. starvae says:

    ZOJ3449. Doraemon’s Number Game III:一个优化是只要对lcm(1..8)=840求一次模就够了。
    应该是对lcm(1..9)=2520 求模吧?

  6.  
Leave a Reply