Andrew Stankevich’s Contest #6
ZOJ2595 Ackerman’s Function 14.93% (99/663)
ZOJ2596 The Minimal Angle 11.07% (65/587)
ZOJ2597 Yellow Code 38.21% (146/382)
ZOJ2598 Yet Another Digit 23.79% (138/580)
ZOJ2599 Graduated Lexicographical Ordering 20.99% (80/381)
ZOJ2600 GSM 20.00% (55/275)
ZOJ2601 Warehouse Keeper 14.69% (117/796)
ZOJ2602 Don’t Go Left 24.13% (49/203)
ZOJ2603 Railroad Sort 46.76% (123/263)

稿好久,趁着集训间隙前来填坑。大妈题就是好啊就是好,于是顺便广告一下,8月14日,ZOJ将办一场Andrew Stankevich’s Contest, Warmup的Practice,用的题目是Andrew Stankevich’s Contest #11,年代有点久远,不过对绝大多数人来讲应该应该是一套非常不错的新题,去年我们也拿来组队训练过,欢迎捧场。

ZOJ2595 Ackerman’s Function

downloadsource code (ZOJ2595.cpp) [recursion, number theory, Euler's theorem]

求Ackerman函数A(n, m)模t的值。

n\m 1 2 3 4 5
1 2 4 6 8 10 … (2m) 2 \times m
2 2 4 8 16 32 … (2m) 2 \uparrow m
3 2 4 16 2222 22222 … (m2) 2 \uparrow\uparrow m
4 2 4 65536 \begin{matrix}\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}} \\ 65536 \end{matrix} overflow .. 2 \uparrow\uparrow\uparrow m
5 2 4 overflow .. 2 \uparrow\uparrow\uparrow\uparrow m ..

上表中用到了Knuth’s up-arrow notation。从上面的表中可以看出n=1, n=2, m=1, m=2的时候问题都很简单,而事实上n和m只要稍稍大一点,这个数就大得不得了,而它关于t的余数就是定值。证明就是利用欧拉定理,可以参考在Andrew Stankevich’s Contest #8解题报告中,ZOJ2674 Strange Limit这题的解题报告。对于n=3&&m<32和n==4&&m==3的时候,结果未必收敛到了ZOJ2674中定义的那个极限,所以也要特殊处理,方法类似求那个极限的递归。

ZOJ2596 The Minimal Angle


downloadsource code (ZOJ2596.cpp) [geometry, math]

给你一段折线,要你通过平面旋转变换,使得最后所有向量关于x轴的极角的和模2*PI最小。

显然最小的答案总是0,只要反向旋转所有向量关于x轴的极角的平均数就好了,平面旋转变换后的坐标可用如下公式计算:
\begin{bmatrix} x' \\ y' \end{bmatrix} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}

ZOJ2597 Yellow Code

downloadsource code (ZOJ2597.cpp) [构造]

gray code恰好相反,yellow code相邻两个数的二进制位有一半(取下整)是不一样的,第一个和最后一个也要满足这个条件。

对1和2的情况,直接输出{“0″, “1″}和{“00″, “10″, “01″, “11″}。对于n>3的情况,递归构造,每次把n分成左右两个部分l+r=n,然后

ans[n][i] = ans[l][i & ((1 << l) - 1)] + ans[r][(i + (i >> r)) & ((1 << r) - 1)];

含义就是左边是长度为l的code的不断循环,右边是长度为r的code的也循环,不过每循环一周,循环起点向后移1。注意拆成的l和r不能都是奇数,比如把6分成3+3,就会有问题,因为可能左右部分都只有1个不同,加起来只有2个不同,不满足至少3个不同的条件。

这题方法必须不唯一了,求仰慕各路大牛们的方法。

ZOJ2598 Yet Another Digit

downloadsource code (ZOJ2598.java) [DP]

问一个数有多少种不同的redundant binary notation,也就是每位数可以是0, 1, 2的二进制表示。

重复的表示就是通过把原本二进制中的10000变成02000, 01200, 01120, 01112这样的形式产生的,有几个0就有几种不同的表示。从低位往高位看,记x为最后一个1没有变成0的方案数,y为最后一个1变成了0的方案数。初始有x=1,y=0。如果第i个bit是1,和上个为1的bit间有c个0,那么有x’=x+y,y’=x*c+y*(c+1)。最后的答案就是x+y。

ZOJ2599 Graduated Lexicographical Ordering

downloadsource code (ZOJ2599.cpp) [DP, counting, parameter searching]

对1到n之间的所有数先按digit sum排序,如果digit sum相同则按字典序排,现在要求k拍在第几位,拍在第k位的数是什么。

还是比较经典的计数问题,写起来有点麻烦。我先通过DP预处理出长度为l(可以有前导0),且digit sum为s的数的个数。然后写了两个函数,sum_less(s, n)计算小于n的,digit sum小于s的数的个数,这个就是一位一位枚举,比较经典的方法。lex_less(s, k, n)计算小于n的,digit sum恰好为s的,字典序小于k的数的个数,这个思想还是一样的,不过麻烦一些。有个这两个函数,那么就可以直接求得k排在1 + sum_less(s, n + 1) + lex_less(s, k, n + 1),其中s是k的digit sum。反求则要麻烦一些,我先二分digit sum,利用sum_less,得到第k个数的digit sum是什么,然后按位枚举这个数,通过lex_less缩小范围,最终求得答案。

ZOJ2600 GSM

downloadsource code (ZOJ2600.java) [math, numeric, BigDecimal]

求一个边长为H的正六边形能够覆盖一个半径为R的圆的交的面积,输出时是比例形式。

结果的数学公式很容易得到,但是题目要求的精度非常高,而公式中还有sqrt和asin。我直接用了java.math.BigInteger,自己利用迭代算法求sqrt,用泰勒展开求asin,最后跑了1s多才跑出所有结果……果断打表。

ZOJ2601 Warehouse Keeper

downloadsource code (ZOJ2601.cpp) [MinCostMaxFlow, bigraph, kuhnMunkres]

有m个仓库和n种货物,每种货物可以选择放在几个仓库中的一个,每个仓库最多放一种货物,要求能安排最多种货物。有一些货物已经安排在了某些仓库,在保证安排最多种货物,希望尽量多保持原先的安排。

我是直接用最小费用最大流过的,比较容易TLE。实际上由于问题的特殊性,可以用二分图最大权匹配来做,对于原先的安排,连一条权为1001的边,对于其它可选的安排,连一条权为1000的边,利用KM算法可解,这个算法会快很多。

ZOJ2602 Don’t Go Left

downloadsource code (ZOJ2602.cpp) [bfs, path compression]

题目就是问给定的旋转机器(大误)是不是连贯的。所谓consecutive就是对任意的输入,他的head都不会往回移。

有关图灵机,参考wiki。首先读入输入,然后对于原地踏步的状态做一个预处理,也就是对所有a为0的状态做路径压缩,压缩的结果可能得到新的a为-1,1或表示进入原地死循环的2。然后我们从初始状态开始bfs,如果遇到-1,就说明”NO”,否则”YES”。注意结束状态u和结束字符s需要特殊处理。

ZOJ2603 Railroad Sort

downloadsource code (ZOJ2603.cpp) [构造, stack, queue, deque]

题目就是要利用n个栈对1~2^n这2^n个数排序。

首先考虑用n个双端队列对0~2^n-1排序,这个很简单:就是第一个队列把最低位为1的留下入队,把最低位为0的直接放走,然后第二个队列按第二位类似处理,最后得到的就是有序的。然后用类似的思路思考栈的,想了很久没多少头绪,最后还是有点找规律地发现了代码中的方法:在第k个栈中,如果(x >> k) % 4为0或3,那么留下入栈,否则直接放走。

这题方法必须不唯一了,求仰慕各路大牛们的方法。

6 Responses to “Andrew Stankevich’s Contest #6解题报告”
  1. Calvinxiao says:

    今天无意中搞了搞2603,由于太弱不会构造,发觉就是个快排啊,solve(1, (1<<n), queue q)就可以了。
    ZOJ服务器升级啦?感觉judge的速度快了很多。

  2. Sayakiss says:

    Ackerman’s Function 表中n=4 m=3有错
    2↑↑↑3=2↑↑4=65536
    所给项其值是2↑↑↑4

  3. VegetableB says:

    2595应该是我的最久远了吧……

  4.  
Leave a Reply