ZOJ Monthly, November 2010
A ZOJ3427 Array Slicing 21.05% (56/266)
B ZOJ3428 Bug Races 25.00% (2/8)
C ZOJ3429 Cube Simulation 22.94% (131/571)
D ZOJ3430 Detect the Virus 8.23% (40/486)
E ZOJ3431 Escape! 9.90% (21/212)
F ZOJ3432 Find the Lost Sock 18.38% (257/1398)
G ZOJ3433 Gu Jian Qi Tan 17.41% (39/224)
H ZOJ3434 Hiiragi’s Sticks 23.68% (9/38)
I ZOJ3435 Ideal Puzzle Bobble 4.87% (2/41)
J ZOJ3436 July Number 13.15% (15/114)

因为这一段时间考试、作业、Project实在忙不过来。所以原定的三题比较难的题目都没有挂出来,所以平凡的题目好像多了一点。最近事情好多好烦,希望快点应付过去……

ZOJ3427. Array Slicing

downloadsource code (ZOJ3427.cpp) [regex, simulation, slice, splice]

其实就是要实现一个list的__getslice__和__setslice__操作(pretty solution in python),或者说splice(more pretty solution in perl)操作。题目关于slice只贴了wiki上一段话,没有详细解释,不过sample给得很强,我以为slice是common sense,可是我错了。

输入有点小麻烦,其实scanf可以轻松搞定的啦,规模非常小,所以暴力什么的就好了。STL里的vector::insert和list::splice都可以直接做题目中的操作。题目说数字都是100,不过list的长度可是可以长到很长的哦,xe一点倒是可以让用数组的TLE,不过这是签名题,没有那么坏啦,sample应该是非常强的了 :-)

ZOJ3428. Bug Races

downloadsource code (ZOJ3428.cpp) [Number theory, Pythagorean triple, Euclid's formula, counting]

题目实际上就是给定n,考虑所有的边长为i ≤ j ≤ k = n的且沿表面对角线的长度是个整数的长方体,求其面对角线长度的均方和与体对角线长度的均方。也就是求这种长方体的个数和其两种对角线的长度的平方和。

事实上面对角线的长度就是sqrt((i+j)^2+k^2),所以我们不妨先考虑如何求方案数,首先利用Euclid’s formula(参考Pythagorean triple)可以得到所有的勾股数(x=r^2-s^2, y=2rs, z=r^2+s^2),这个不是太多的,我的程序一共算了518346对互质的r和s,一共算了12811925对不同的x和y。然后对于y=n,应该有x=i+j,且i ≤ j ≤ n,有从i从l=max(1, x – y)到r=x/2一共r-l种三元组;对于x=n类似。对于面对角线,这个很好求,就是加上(x^2+y^2)*(r-l)。对于体对角线,首先加上n*n*(r-l),然后就是\sum_{i=l}^{r-1}i^2+\sum_{i=l}^{r-1}(x-i)^2,\sum{n^p}直接套用O(1)公式就好。注意中间过程是会爆long long的。我的算法预处理出了所有的答案,事实上照范叔的按单case做的算法可以更快 :D

ZOJ3429. Cube Simulation

downloadsource code (ZOJ3429.cpp) [simulation]

注意到所有SWAP操作就相当于交换了两个坐标的值,所以直接模拟维护x、y、z坐标和原先的对应情况。于是fill操作是O(n)的,其余操作都是O(1)的。

ZOJ3430. Detect the Virus

downloadsource code (ZOJ3430.cpp) [base64, Aho-Corasick]

有若干种virus的关键字串,还有一些待检查查的数据,问数据中出现了几种不同的样本。不过输入是以base64给出的。

明显的多串匹配,上AC自动机,不过KMP也能过。AC自动机要能处理一个样本是另一个样本子串或两个样本连接后的子串的情况。

ZOJ3431. Escape!

downloadsource code (ZOJ3431.cpp) [DP, enumeration]

题目就是要从第n层逃到第1层出口,知道每层楼梯的位置,必须在一定时间Ti内逃离第i层。另外每层都有一些不同价值的宝物,问是否能逃出和能逃出时可获得的最大价值。

很显然的动态规划,dp[i][j]表示在时间逃离第i层的时间为j,然后由于每层最多只有5个宝物,只要考虑各种取得宝物的顺序,而两点之间所需的时间就是曼哈顿距离了,所以枚举所有5!+4!+3!+2!+1!+0!种可能的转移就好了。

ZOJ3432. Find the Lost Sock

downloadsource code (ZOJ3432.c) [bitwise xor]

签名题。也是骗提交的题。由于两个完全相同的串异或一下就全0了,所以只要把所有串都异或一下就是答案。不知道实现的好的hash能不能过,我的程序跑了30ms。

ZOJ3433. Gu Jian Qi Tan

downloadsource code (ZOJ3433.cpp) [greedy]

这题给出M个迷宫,在第i个迷宫中,你可以获得A[i]个Cake,并有许多Ice Heart(IH),对于第j个IH可以靠消耗B[i][j]个Cake来获得。最后,要求按顺序走完全部迷宫后,最多能获得多少IH。

比赛的时候WA了无数次才发现自己的贪心不对,后来写了个绕大弯的贪心过了。猛犸的算法是走到一个迷宫后,尽可能地占下所有的IH,如果占下某个IH时将当前积累的Cake消耗成了负数,则放弃之前取得的一个消耗Cake最大的IH。类似的标程是如果Cake数不足以再取得一个IH的时候,将消耗最小的IH的消耗值减去所剩的Cake数。我的想法比较蛋疼,就不说了。

ZOJ3434. Hiiragi’s Sticks

downloadsource code (ZOJ3434.cpp) [DP]

这题正好是H打头的title,所以就选了,不过题目背景很无聊,和H什么的也没有关系。直接按题目的理解把答案写成三层循环求和的话是很难算出来的,事实上把里面两重循环求和合并成直接按那两条规则DP就好了。起初所有dp[i]=0,然后如果柊(Hiiragi, ひいらぎ)已有一个长度为b的木棍,那么++dp[b],这相当于Use t1 as the new t and go back to the first step until t reaches 1,然后(2 .. l).each{|i| (i’s primer factor).each{|p| dp[i] += dp[i / p]}},这相当于For a number t, find one of its prime factor p, calculate t1 = t / p。于是dp[i]就是如果i \in S所能得到的收益。要注意题目里的描述Use each of your m short sticks to measure each of the lengths in S,m根木棍是要重复就算的,而S集合是要去掉重复计算的。

ZOJ3435. Ideal Puzzle Bobble

downloadsource code (ZOJ3435.cpp) [Number theory, Inclusion–exclusion principle, Möbius function, Möbius inversion formula, counting]

题目去掉背景以后就是要求#{(i, j, k) | gcd(i, j, k) = 1, i ≤ L, j ≤ W, k ≤ H}。

规模1e6,暴力显然是不行的。首先对于gcd(x, y) = 1这个问题,可以直接利用容斥原理(Inclusion–exclusion principle)得到解决。类似的,记f(x)表示gcd(i, j, k)整除x的个数,那么利用容斥原理有answer := f(1) – f(2) – f(3) – … – f(p) + f(2*3) + f(2*5) + … + f(p1*p2) – f(2*3*5) – …。事实上这个玩意是有名字的,叫做默比乌斯函数Möbius inversion formula。然后显然有f(n)=(i/n)(j/n)(k/n),这里的/是整数除法。至此,我们推出的这玩意在一维的情况其实就是默比乌斯反演公式(Möbius inversion formula),不过我总记不住,每次都是重新推。于是我们知道答案就是

 \sum_{n=0}^\infty\mu(n)\lfloor\frac{i}{n}\rfloor\lfloor\frac{j}{n}\rfloor\lfloor\frac{k}{n}\rfloor

这个公式应该是没有closed form的(这玩意要有closed form,必然会被搜OEIS的同学秒了,所以我出monthly的时候都会把此类题毙掉),不过我们已经能在O(N)的时间解决这道题了,事实上不只是三维,来个十维八维都不成问题,嗯事实上这题也可以扩展到更高维。如果这题是单case的话,到这里就结束了,不过这题有很多很多case,题目要求一个更高效的算法。做法就是合并(i/n)(j/n)(k/n)相同的项,即枚举商,比如这个\sum_{i=1}^n\left(\lfloor\frac{n}{x}\rfloor-1\right)的问题,很容易证明这个复杂度是O(\sqrt{N})的。这样我们事先求出默比乌斯函数函数的部分和(哦,这玩意也有名字,叫Mertens function),这部分只要通过素数筛法可以O(n)的预处理得到,然后对于(i/n)(j/n)(k/n)相同一段的和就可以O(1)得到,由于这样的段数不超过O(3\sqrt{N}),所以对于每个case,只要O(\sqrt{N})的时间求解。

ZOJ3436. July Number

downloadsource code (ZOJ3436.cpp) [search, counting]

将一个数字的相邻两位的差(的绝对值)组成一个新的数字,不断重复,如果最后得到7,就称这个数为July Number,比如9024 – 922 – 70 – 7。题目要求1e9范围内给定区间[a, b]里July Number的个数。

没有发现这种数字有什么特别的统计上的规律。不过可以想到,这种数是不太多的,事实上对各种Number有


353008254
January 451156127
February 131145647
March 44286220
April 14800278
May 4397180
June 1031969
July 160218
August 13851
September 256
October 0
November 0
December 0


所以只要把这些数暴力出来存在一张表里,然后对每个查询做两次二分就能得到答案。生成表的方法就是逆推!比如由7出发,可以得到70, 81, 92, 19, 29,从19出发可以得到109, 890,这只要枚举最后以为数字,然后枚举相邻两位的差是正的还是负的,可以简单的写成一个dfs。

19 Responses to “ZOJ Monthly, November 2010解题报告”
  1. jing says:

    为什么
    3
    YmFzZTY0
    dmlydXM=
    dDog
    1
    dGVzdDogdmlydXMu

    第二个病毒也算,不是还有个=吗

  2. jing says:

    为什么3
    YmFzZTY0
    dmlydXM=
    dDog
    1
    dGVzdDogdmlydXMu

    第二个病毒也算

  3. jing says:

    为什么3
    YmFzZTY0
    dmlydXM=
    dDog
    1
    dGVzdDogdmlydXMu
    第二个病毒也算

  4. lpld says:

    Escape! 这题..
    输入的数据Ti. 经测试有超过1000的,达到了1048….

  5. agralol says:

    感觉Escape!中枚举5!=120有点大,有没有可以解决这种定点最短路的O(N^2)的算法呢

    • watashi says:

      这题不大啊,5!最多算1000次,比DP转移的1000*1000还小啊
      没有的,应该是NP-hard的

      • agralol says:

        每一次转移都要枚举的话,不就是1000*1000*1000了?为什么最多1000次呢
        还有一个不大明白的,4!以后为什么不需要乘组合数呢,感觉这4个应该要事先选出来吧

  6. self_healing says:

    ZOJ3430. Detect the Virus 经测试原串里面有ascii码为0的字符唉,这样的数据合法?

  7. [...] 这里看后,更加吐血,居然输入也有哈,scanf也不用就读整形,嫌32位运算慢,用long long 64位来异或……囧,我太菜了。 [...]

  8. 山羊快跑 says:

    啊!我真什么都不是了……今天就被袜子TLE了两个多小时……“异或”两个字,恍然大悟,然后一个看博主标称,又立刻无地自容,怎么输入也这么抠门的优化……膜拜……

  9. 3214668848 says:

    orz I题神题啊,俨然就是spoj一题的升级版啊

    • Navi says:

      7001. Visible Lattice Points么?
      I题出出来的时候好像spoj还没挂那题的样子…

  10. Navi says:

    bs.. H题为什么就要和H有关系……

  11.  
Leave a Reply