这套体中推荐ZOJ 2674, ZOJ 2673, ZOJ 2676, ZOJ 2675。其中2674是欧拉函数,但模型非常赞;2673是非常不错的DP问题;2676是0-1分式规划与网络流相结合的经典中的经典。

ZOJ2670 Nonoptimal Assignments

downloadsource code (ZOJ2670 .c) [构造]

给定n,构造一个n*n的矩阵,使得按题目所给的“贪心”算法,不能得到正确解。

构造非常简单,下面是我的一种构造
\begin{pmatrix}0&1&1&\cdots&1\\0&2&2&\cdots&2\\0&0&2&\cdots&2\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&2\end{pmatrix}

ZOJ2671 Cryptography

downloadsource code (ZOJ2671.c) [math, SegmentTree]

有n<30000个2×2矩阵,m<30000次查询,每次查询需要快速回答区间[i, j]内矩阵的积(mod r)。

如果把矩阵换成整数,把求矩阵积换成求区间和(或最大/小值),那么这就是线段树一个经典的应用,而且是结构最为简单的一种线段树。而矩阵的乘积运算同样满足结合律((A*B)*C=A*(B*C)),符合应用线段数优化的条件,所以通过线段树,问题能在O(mlg(n))内解决。

ZOJ2672 Fibonacci Subsequence

downloadsource code (ZOJ2672.c) [DP, hash]

给定一个长度为n<=3000的序列,要求满足Fibonacci性质(c[i]=c[i-1]+c[i-2])的最长的子序列。

枚举c[1]=a[i]和c[2]=a[j],那么可以依次在序列中查c[3]=a[k], c[4], …其中k显然应该取满足a[k]==a[i]+a[j]&&k>j中最小的。但可能有很多比较长的序列,而对一个最大长度为m的Fibonacci序列,会被枚举到O(m)次,总的处理复杂度是O(m^2)的,会TLE。为了避免这种重复计算,引入动态规划,dp[i][j]表示c[1]=a[i], c[2]=a[j]的序列的最大长度,那么有dp[i][j]=dp[j][k]+1,DP复杂度为O(n^2)。最后问题的关键是已知i和j,如何得到k,一个map<a[k], k>可以满足要求,但是这里它太慢了,O(n^2lg(n))的复杂度将会超时。所以需要用O(1)的hash_map代替O(lg(n))的map,也可以自己实现哈希。

ZOJ2673 Hexagon and Rhombic Dominoes

downloadsource code (ZOJ2673.c) [DP, bitwise]

问用两个正三角形组成的棱形覆盖变长为n<=7的正六边形三角网格的方案数。

mp.2673
首先往找规律和yy递推公式想,未果。最后回到把一行的状态压缩为掩码,然后按行动态规划(DP)。不过这里如何记录一行的状态也是有技巧的,因为n=7时,最长的一行有多达4*7-1=27个三角形。首先只考虑六边形的上半部分,分析以后,可以发现状态可以简单记录如下,只需记录头朝下的三角形,如果它与上一行的三角形构成棱形的话,记为1,否则就是与同一行的三角形构成棱形,记为0,这样一行最长为2*7-1=13,而且对于第i行,掩码里恰有i-1个1。dp[i][j]记录第i行状态为j的方案数,那么有dp[i][j]=sum{dp[i-1][k]|ok(j,k)},其中ok(i,j)表示状态j和k是吻合的,我写了一个函数来判断,不知道能不能通过精巧的位运算漂亮的实现。由于上下是对称的,而中间的两行要吻合,它们的状态要相同,所以答案就是sum{dp[n][i]^2},答案在long long范围内。

以下是引用asmn在2010/4/1 0:22:51的发言:
你那样好麻烦啊……对于三对边长分别为a、b、c的六边形,答案是所有这样(i + j + k – 1)/(i + j + k – 2)的乘积,其中1<=i<=a, 1<=j<=b, 1<=k<=c。

可以参考http://en.wikipedia.org/wiki/Young_tableau

ZOJ2674 Strange Limit

downloadsource code (ZOJ2674.c) [recursion, number theory, Euler's theorem]

求aa..a%m!的极限。

非常好的一道题,题目的核心是欧拉定理(Euler’s theorem, a.k.a. Fermat-Euler theorem or Euler’s totient theorem)。但不像上海Regional的B那样赤裸裸的,隐藏得比较深,尤其是p是素数和模的是一个阶乘这些都是不必要的条件,纯属烟雾弹。欧拉定理的内容是:如果a和n互质,那么aφ(n)=1(mod n);对于任意a, n和较大的b,有ab=aφ(n)+b mod φ(n)(mod n)。

于是利用欧拉定理,问题就很简单了,我们把上面问题的极限记为x=gao(a, b=m!)。那么假设y=gao(a, φ(b)),就有x=aφ(b)+y mod b,而如果b=1,显然x=0。于是可以递归求解,显然φ(b)<b,递归将在有限步得到结果。

ZOJ2675 Little Mammoth

downloadsource code (ZOJ2675.c) [geometry]

计算矩形的公共面积()。

计算几何问题有一些共同点,如果能找到一个通用而有效的方法,可以避免很多if-else,而且精度问题也小。这一题我们可以求出所有关键点,然后用圆心出发的少描线来求交集。由两个关键点确定两条扫描线,进而确定一个三角形或一个扇形,然后可以求出这个三角形或扇形的有向面积。所有有向面积的和的绝对值就是答案。
mp.2675
上面这个图就是sample,我们可以依次
+Blue +Yellow -Fuchsia -Aqua +Red +Green
而得到交集的面积(的相反数)。注意求扇形面积的时候,别像我一样,多出或少掉了2πr2 :-)

ZOJ2676 Network Wars

downloadsource code (ZOJ2676.c) [FlowNetwork, parametric search(参数搜索), 0-1分式规划]

经典的0-1分式规划(fraction programming或分数规划,但优化里似乎都译作分式规划)+网络流最小割(最小割等于最大流)。请直接参考Amber大牛那篇《最小割模型在信息学竞赛中的应用》(Applications of Minimum Cut Model in Informatics)(点击下载)。网络流是浮点数的,需要注意,不过EPS哪怕取0.1也能AC。

ZOJ2677 Oil Deal

downloadsource code (ZOJ2677.c) [graph, greedy, MST]

一个由带权无向边组成的联通图,要求在保持连通性的前提下,删掉最多条边,所删边的总权重不能超过s。

贪心,首先求最大生成树(Maximum Spanning Tree缩写还是MST :-) ),那么为了保持连通性,这些边都不能删了。然后对能删的那些边按权重排个序,捡权重小的开始删,直到“经费不足”。

ZOJ2678 Bishops on a Toral Board

downloadsource code (ZOJ2678.c) [BigInteger, number theory, gcd]

问要覆盖一个m*n的棋盘,最少需要多少象,这里的象会穿越,拥有比地灵殿里八雲紫还强的支援特技

恩恩,答案就是gcd(m, n),很基本的数论,需要大数,我耍赖就直接上java.math.BigInteger.gcd了。


Andrew Stankevich’s Contest #8
ZOJ2670 Nonoptimal Assignments 75.66% (687/908)
ZOJ2671 Cryptography 27.49% (102/371)
ZOJ2672 Fibonacci Subsequence 7.57% (205/2705)
ZOJ2673 Hexagon and Rhombic Dominoes 43.88% (79/180)
ZOJ2674 Strange Limit 31.00% (71/229)
ZOJ2675 Little Mammoth 26.11% (47/180)
ZOJ2676 Network Wars 18.35% (350/1907)
ZOJ2677 Oil Deal 25.10% (229/912)
ZOJ2678 Bishops on a Toral Board 30.20% (151/500)

20 Responses to “Andrew Stankevich’s Contest #8解题报告”
  1. xioumu says:

    ZOJ2674有个疑问

    题目中给的a与b(m!)并不一定互质,为什么还可以用欧拉定理呢?

  2. wuyongxing says:

    good

  3. wuzhengkai says:

    E的话x=p^(phi(m!)+x%phi(m!))%(m!)
    这样枚举x%phi(m!),这个只有九千万,然后就过了

  4. [...] 首先是挑选第8套采取AK计划,但Strange Limit真的杀灭了我好多脑细胞——我对欧拉定理不熟悉,或者说数论确实是我的软肋,也活该09年上海被干死。不幸的是,AK在即的时候watashi抢先圆满并发布详细题解,狂灭我激情。不过他写的题解还真不错,他整个博客都不错。 [...]

  5. VegetableB says:

    想起来,2674我在zoj放题目出来之前就写过接替bg了……

  6. VegetableB says:

    为啥跳过了9了?

  7. 3xian says:

    哈,最近我也做了一下这套。
    第一题我想到两个方法:
    方法一:最右下角填1,其余都填0。
    方法二:把sample放在左上角,其余都填相同的比10大的数。

    最后一题【很基本的数论】好惭愧我是把小数据floodfill找规律的,其实该怎么推呀- -

    • watashi says:

      方法一很赞,比我的好多了

      最后一题我是这样想的:
      首先覆盖整个棋盘等价于覆盖整个第0行
      如果第0行的第b列被覆盖了,那么所有形如(i%m,(i+b)%n)的格子,在第0行就是所有形如(km+b)%n的列都被覆盖了
      然后这种数一共有n/gcd(m,n)个
      取b=0..gcd(m,n)-1就能把第0行完全覆盖

  8.  
Leave a Reply