Andrew Stankevich’s Contest #1
ZOJ2313 Chinese Girls’ Amusement 34.16% (233/682)
ZOJ2314 Reactor Cooling 26.61% (297/1116)
ZOJ2315 New Year Bonus Grant 35.25% (239/678)
ZOJ2316 Matrix Multiplication 44.19% (293/663)
ZOJ2317 Nice Patterns Strike Back 24.05% (115/478)
ZOJ2318 Get Out! 19.91% (94/472)
ZOJ2319 Beautiful People 26.34% (254/964)
ZOJ2320 Cracking’ RSA 31.41% (82/261)

大妈题第一套的解体报告。个人推荐ZOJ 2318ZOJ 2320。AC代码含,可直接看或下载

ZOJ2313 Chinese Girls’ Amusement

downloadsource code (ZOJ2313.cpp) [number theory]

求最大的k<=n/2使得gcd(n,k)=1。

如果n是2m+1形式的,那么k=m就是答案;
如果n是4m形式的,那么k=2m-1就是答案;
如果n是4m+2形式的,那么k=2m-1就是答案。
证明略,需要简单的高精度。

ZOJ2314 Reactor Cooling

downloadsource code (ZOJ2314.java) [FlowNetwork, 上下界最大流]

求一个无源汇的上下界网络流的可行流。

裸的上下界网络流问题,规模也很小,最暴力的网络流算法也没问题。至于上下界网络流可行流转化为普通网络流最大流的构图和原理,看论文吧(明白了很简单,虽然要独立想到绝对不容易)。

ZOJ2315 New Year Bonus Grant

downloadsource code (ZOJ2315.java) [graph, greedy]

给定一棵树,要求找出一个最大的边集合,要求一个顶点上至多只有一个边属于这个集合。

对于一个图,这是一个一般图最大匹配问题;如果这个图没有奇环,那还是一个二分图匹配问题;而这个题目中是一个树,规模也要求一个O(n)的算法。可以考虑树形DP,不过对问题的进一步分析可以得到一个拓扑排序+贪心的算法,方法如下:按拓扑排序的顺序遍历所有节点,如果该节点及其父节点(chief)都未被标记,则标记上,并把该节点加入答案中。就不证明了。

ZOJ2316 Matrix Multiplication

downloadsource code (ZOJ2316.c) [graph, math]

A是图G的关联矩阵,求B=ATA的元素和。

对于图的关联矩阵,有性质:
ans=\sum_{i,j}{B_{ij}}=\sum_{i,j}\sum_k{A_{ki}A_{kj}}=\sum_k\sum_{i,j}{{A_{ki}A_{kj}}}=\sum_{k=0}^n{d(v_k)^2}
其中d(vk)为定点k的度数。复杂度为O(n+m)。

ZOJ2317 Nice Patterns Strike Back

downloadsource code (ZOJ2317.java) [DP, 矩阵乘法]

一个黑白pattern是nice的,当且仅当没有没有一个2*2的部分是全白或全黑的,问有多少种不同的n*m的pattern。

注意要判断一个pattern是不是nice的,只要检查相邻的两行的状态。由于m很小,可以将行的状态用2^m的掩码来表示,dp[k][i]表示k行,最后一行状态为i的pattern个数,如果状态i和状态j不冲突,那么dp[k+1][j]+=dp[k][i]。由于问题中n很大,这样一行一行转移的动态规划肯定是吃不消的。注意每次的转移其实都是一样的,记dp[k]为一个列向量,建立一个2m*2m的01矩阵A,矩阵元素对应表示两行状态是否冲突,则dp[k+1]=A*dp[k],dp[n]=A^n*dp[0],而A^n可以利用经典的快速乘法运算来计算。

ZOJ2318 Get Out!

downloadsource code (ZOJ2318.java) [graph, geometry]

你是一个圈,被很多圈圈包围着,问你是否有可能逃出包围。

可以对所有圆做一个平移,再将半径增加人的半径,这样人就在原点,半径为0了,方便考虑问题。原题问的是是否有一些圆包围了原点,实际上对于相交的两个圆,我们可以用他们圆心连线来代替它们。这样问题变为是否存在一个多边形,使得原点在这个多边行内部。判断点在多边形内一个比较简单有效的方法是按顺序扫描边,如果整个过程的有向视角之和为0的话,点在多边形外,为2PI或-2PI的话,点在多边形内。于是我们可以对所有相交的两个圆之间连两条有向边,边权是对应的有向角。答案取决于这个有向图里中是否存在负环,这只需要调用*一次*bellman_ford算法就可以判定了。

当然这题还有很多做法。但这种把计算几何问题转为图论问题后,再利用我们熟悉的图论算法求解,是最简单而不易出错的。

ZOJ2319 Beautiful People

downloadsource code (ZOJ2319.cpp) [DP, LIS]

选取最多的人,要求不存在两个人i和j,Si <= Sj && Bi >= Bj。

先把所有人按S排序,然后再按B求最长上升子序列(LIS)。LIS是很经典的问题了,简单的DP复杂度问O(n^2),这里需要使用经典的O(nlg(n))的算法。

ZOJ2320 Cracking’ RSA

downloadsource code (ZOJ2320.java) [number theory, linear system, gauss elimination]

一个m个数构成的集合,这m个数的质因子都来自前t个质数,问有多少个非空子集,其元素的积是平方数。

b_i=\prod_{j=1}^t{p_j^{a_ij}}
其中aij只有奇偶有影响,我们不妨记奇为true,偶为fasle。在令xi表示子集中含(true)或不含(false)bi。那么题目就要要求其次布尔线性方程组
\left\{\begin{array}{l}a_{11}\land x_1\oplus a_{12}\land x_2\oplus \cdots\oplus a_{1m}\land x_m=false\\a_{21}\land x_1\oplus a_{22}\land x_2\oplus \cdots\oplus a_{2m}\land x_m=false\\\cdots\\a_{t1}\land x_1\oplus a_{t2}\land x_2\oplus \cdots\oplus a_{tm}\land x_m=false\\\end{array}\right.
的非零解(非空子集)的个数。用高斯消元法求得系数矩阵{aji}的秩r,那么答案就是2m-r-1。

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

    ZOJ的java有没有啥好的IO或者其他优化方法呢….我2313和2317在ZOJ都超时了,SGU上都没问题…

    • watashi says:

      sgu单case时间也许更宽松一些吧,你是用Scanner么,这个很慢的
      在TC/CF上可以看到,像Egor, wata这样专用java的,都有自己的读入库吧
      不过有些题实现比较紧,java是基本没法过的

  2. zjut020 says:

    不是,是c++
    哦,那我优化下··
    :-)

    • zjut020 says:

      囧了,你的也超时……

      • watashi says:

        Run ID Submit Time Judge Status Problem ID Language Run Time(ms) Run Memory(KB) User Name
        2164885 2010-04-16 13:22:38 Accepted 2317 Java 2630 2735 watashi@Zodiac
        2164883 2010-04-16 13:22:28 Accepted 2317 Java 2590 1501 watashi@Zodiac

        我刚才又交了两次……我也不清楚怎么回事了

  3. zjut020 says:

    问下ZOJ2317 Nice Patterns Strike Back
    这题的zoj数据是不是有问题啊,我在sgu ac了这里却超时了。。
    = =

    • watashi says:

      不确定,但我觉得应该没什么大问题,我两边都可以,不过sgu是一个一个case跑的,ZOJ时间可能更紧
      我只知道sgu有几道题的spj有问题,WA的也能AC
      你是用java吗?

  4. VegetableB says:

    这套题比较老了,几乎都成了经典题了……

  5.  
Leave a Reply