ZOJ八周年庆,8道题,比赛时间188min,很有爱。其实是因为勉勉强强才凑到了8道题,如果正正经经比5个小时的话,大家都圆满了。


ID Title Ratio (AC/All)
A(ZOJ3305) Get Sauce 16.56% (142/857)
B(ZOJ3306) Kill the Monsters 17.36% (25/144)
C(ZOJ3307) Magic Machine 18.03% (11/61)
D(ZOJ3308) Move the Knights 37.23% (35/94)
E(ZOJ3309) Search New Posts 20.20% (80/396)
F(ZOJ3310) Unrequited Love 23.47% (307/1308)
G(ZOJ3311) ZOJ Special AC String 24.59% (338/1374)
H(ZOJ3312) 8*8 7.14% (2/28)


除了G和H外都是summer2009暑期集训里的题。不说废话了,正文开始:

ZOJ3305: Get Sauce

一个n<=16个元素的集合,给定m<=种备选子集,问最多可划分出多少个不相交的备选子集。

source code [bitwise, search]

这题有复杂度O(3^n),而且常数很小的算法。这基于下面这个简单又漂亮的位运算枚举子集的循环

for (int sub = mask; sub != 0; sub = (sub - 1) & mask)

sub将依次表示mask所有可能的子集,总的枚举复杂度则是n^3。

当然,搜索加有效地剪枝总是能过的。不过我表示剪枝苦手,当时也不知道这样一个O(3^n)枚举子集的算法,所以我是训练前18名中唯一一个没过这道题的,惭愧啊~

ZOJ3306: Kill the Monsters

在一个20×20的grid中,选择共n行与列,使得最多的’#'同时被所选行和列覆盖。

source code [bitwise]

很evil的一道题,要不断优化,很容易TLE。基本的算法是对行进行O(2^20)的枚举,然后再对列排序贪心。第一个优化自然是引入位运算,并预处理出数组bits,表示二进制下1的个数;第二个优化,也是比较重要的优化,设当前枚举的行选择掩码为i,已知这列’#'的掩码为mask[j],则选择这列可实现覆盖两次的’#'数可以通过bits[i & mask[j]]快速得到;此外对列贪心使用桶排序也是可选的一个优化。

ZOJ3307: Magic Machine

给定一个长度为n的序列seq,问题中给定的算法正确返回第k大值的概率。

source code [DP, 记忆化搜索]

首先是trick:输入数据以一个负数结尾; 有重复数字; 第k小的未必是序列排序后的第k个数; 如果没有k个不同值,那么概率显然是0。算法就是记忆化搜索:

double gao(int l, int r) {
    if (l >= r) {
        // interval[left, right] is illegal or empty
        return 0;
    } else if (dp[l][r] >= 0) {
        // done
        return dp[l][r];
    } else {
        double &ret = dp[l][r];
        ret = 0;
        // random choose one position i that left <= i <= right
        for (int i = l; i < r; ++i) {
            ret += a * ok[i]  + b * gao(l, i) + (1 - a - b) * gao(i + 1, r);
        }
        ret /= (r - l);
        return ret;
    }
}

其中gao(l, r)返回在区间[l, r)内获得正确结果的概率。如果第i个数的值是第k大的,那么ok[i] = 1,否则ok[i] = 0。

ZOJ3308: Move the Knights

一个棋盘只在白格子有马,马移动的花费与起终点的格子权和马的类型有关,问移动k个马的最小代价是多少。

source code [FlowNetwork, MinCostMaxFlow]

看到国际象棋和马,想到二分图,这还是一个带权二分图。由于题目中要求恰好移动其中的k个马,而不是全部,我们可以按费用流构图,再增加一个超级源点s’,和一条s’->s流量为k费用为0的边,最小费用最大流之。

ZOJ3309: Search New Posts

对帖子进行一系列发布,回复和标记为已读等操作,要求对每个search查询输出未读帖子(帖子数<100)。

source code [DS]

合理的利用数据结构和算法减小均摊复杂度,各式各样的解法都可以。我的方法:

void gaoSearch() {
    set<string> post;
    list<string>::iterator it = lst.begin();
    while (post.size() < 100 && it != lst.end()) {
        if (post.find(*it) == post.end()) { // new
            if (st.find(*it) != st.end()) {
                fputs(it->c_str(), stdout);
                post.insert(*it);
                ++it;
            } else {
                it = lst.erase(it);
            }
        } else {
            it = lst.erase(it); // ++it;
        }
    }
    fputs("###\n", stdout);
}

lst是按发布/回复时间顺序保存着帖子的std::list,st则是保存着未被标记为已读的帖子的std::set。虽然search里有个可能很慢的while循环,但其实对于每个帖子操作,都只会在while循环里被执行一次,所以复杂度是O(nlg(n))的,其中lg(n)来源于std::set,如果用hash,可以优化到O(n)。

ZOJ3310: Unrequited Love

从n个数组成的环中取出互不相邻的一些数,使得这些数的和的最大。

source code [DP, enumeration]

首先考虑从n个数组成的序列中取出互不相邻的一些数,使得这些数的和的最大的问题。这是一个简单的动态规划(看着像Fibonacci数列^ ^):

long long gao(int n, int a[]) {
        long long x, y, z;
        x = y = 0;
        for (int i = 0; i < n; ++i) {
                z = x;
                x = y;
                y = max(y, z + a[i]);
        }
        return x;
}

对于环的情况,通常的解决办法就是拆环成链。对于这题,显然要么不选第一个,于是可以转换成[2, n]组成的链的问题;要么不选第n个,于是可以转换为[1, n - 1]组成的链的问题。注意n = 1的情况。

ZOJ3311: ZOJ Special AC String

判断给定字符串在所定义的两条规则下是够是acceptable的。

source code [string, greedy]

合法的字符串具有O{a}ZO{b}JO{c},且a + b = c && b > 0的形式,其中O{x}表示x。再补几个case:

OO
ZZ
ZJ
OZJO

ZOJ3312: 8*8

构造一个满足给定值的由8个8组成的算术表达式。

source code [Fraction, search]

算法就是按1个8,2个8……8个8的顺序预处理出所有可能的值,可以用map去重复,并记录答案。长度为30的限制没太大用,事实上长度可以控制在1+4*7-2=27以内。玩过24点的都应该知道,里面有一类很evil的case就是中间过程不能整除,出现了分数。这里也一样,中间过程应该用分数记录。然后题目要求是恰好8个8,不要像我一样脑残的输入1输出8还不知道错了。

15 Responses to “ZOJ 8th Anniversary Contest解题报告”
  1. wzc1989 says:

    Search New Posts 看着好像不是nlogn,貌似复杂度有点高?
    如果有很多search,一个search是不是就是nlogn?

    • watashi says:

      复杂度的确是O(nlgn)的,而且用hash_set代替set就能做到O(n)
      如果search多了,那么每个search的时候st.size()和lst.size()势必就大不了
      每个post只会进st, lst一次,出一次,所以看起来每次search都有个while循环很吓人,但总的循环次数只有n而已

  2. inowfordream says:

    求教大牛,那个3^n的复杂度如何证明…

  3. Navi says:

    手机一水…原来yq无线可以直接上国际网

  4. VegetableB says:

    揭露黑历史啊……

  5. Hang Hang says:

    有钱提醒,ZOJ3305: Get Sauce有个3^n写成n^3了,我还是在肥羊zz的时候才发现的,教坏xpy了

    • watashi says:

      钱在哪里?
      我错了,其实本来全部写成n^3了,结果还有一个漏网了,不过简单推导一下就能证明是3^n吧

  6. Navi says:

    Get Sauce原来我当时过了啊-.- 发现当时好像是各种ws办法终于过了的…
    AC String再补两个Case: OJZO和OJZOO-.- 我感觉把所有情况都考虑到了结果还是wa.. 想了好一阵终于想到忘记判b不能为0了… 于是准备比赛结束前一分钟交-.- 结果忘记了……刚才一交果然ac…

  7.  
Leave a Reply