GCJ 应该是算法比赛里面实质上做的最好玩的一个，个人觉得，为了每年都必须保持有的衣服，虽然工作很忙，还是要参与的。

不过今年的 GCJ Qualification Round 还比较好搞，虽然最终 Large Case 的结果未出，但是基本可以确定满贯了，题目比较容易，就是第三题扫雷稍微卡壳了一下，WA 了一次。代码和数据在这里。

A. Magic Trick (6pt)

这道送分题，数字 1-16 排成 4×4，先给一个行数，打乱，再给一个行数。问两次都出现在指定行的数字，按情况输出。

太简单不解释，用 Python 写更是舒心省事。

import sys

sys.stdin = open('A-small-attempt0.in', 'r')
sys.stdout = open('a-small.out', 'w')

for t in range(int(input())):

    k = int(input())
    r = [set(map(int, input().split())) for i in range(4)][k-1]

    k = int(input())
    r &= [set(map(int, input().split())) for i in range(4)][k-1]

    print('Case #%d: %s' % (
        t + 1,
        'Volunteer cheated!' if len(r) == 0
        else r.pop() if len(r) == 1
        else 'Bad magician!'
    ))

sys.stdin.close()
sys.stdout.close()

B. Cookie Clicker Alpha (8pt/11pt)

这道题也不难，单线贪心问题。刚开始你有 0 财富，每秒会产生 2 财富（连续产生非离散），给出 C/F/X，随时可以花掉 C 块钱来使得财富产生速率增加 F/秒，问最快多少时间可以积累到 X 财富。

这是一个简单的贪心过程，也没有什么技术含量，不解释直接上代码：（Python 真是舒心省事！）

import sys

sys.stdin = open('B-large.in', 'r')
sys.stdout = open('b-large.out', 'w')

for c in range(int(input())):

    (C, F, X) = map(float, input().split())
    f = 2
    t = 0
    ans = X / f
    while t < ans:
        t += C / f
        f += F
        ans = min(ans, X / f + t)

    print('Case #%d: %.7f' % (c + 1, ans))

sys.stdin.close()
sys.stdout.close()

C. Minesweeper Master (11pt/24pt)

扫雷，给出一个 RxC 的尺寸，以及雷数 M，求构造一个一击通关的雷阵。

最后的构造法很简洁，但是想出来有点慢。分情况讨论：

1. 如果 min(R, C) = 1 或者 R*C-M=1（安全格数仅一格），必然可行直接构造

2. 剩下的情况肯定是至少两行，至少两列，至少两安全格的情况：

我们通过构造可以发现最小的通关单元是角落上 4×4 的空位，而且不难发现，2, 3, 5, 7 这几个数字都构造不了的，先作排除。

其他情况我们按照这样的方法来构造：如（R=6, C=8）：

我们先把 RxC 填满雷，灰色的是雷。

然后如上图我们构造 rr, cc 满足 2 <= rr <=R, 2 <= cc <= C。

我们可以看到，如果把绿色部分全部都标记为安全格，那么肯定是 OK 的。并且，这时候我们任意从上到下从左到右将黄色的地区的雷拿走（我们开始的时候），拿走的部分肯定也保证是安全的（仔细斟酌一下就知道了）。

如上图，我们在 rr 和 cc 定下来之后往黄色区域填了6 个格子，这样就构造了一个 R=6/C=8/M=24 的雷阵（绿色橙色是安全格，灰色黄色是雷区。）

此外，我们可以发现，只要 rr 和 cc 确认了，就可以产生任意一个安全格数在 (rr+cc-2)2 到 rrcc 范围的雷阵。

另外，如果 rr=2 或者 cc=2，这个范围就只有一个数（等于 2rr 或者 2cc），也就是说明如果只有两列的情况，如果是奇数是行不通的。

其他情况，所有的雷数都可以构造！

那么我们只需要遍历一下 rr 和 cc，看看 RC-M 是否在 [(rr+cc-2)2, rr*cc] 这个区间内，如果是，直接按照这个方法构造即可。

这样复杂度不会很高啦，不仔细分析了。下面是代码：

import sys

sys.stdin = open('C-large.in', 'r')
sys.stdout = open('c-large.out', 'w')


def solve(R, C, M):
    G = [['*'] * C for r in range(R)]
    if min(R, C) == 1 or R*C-M == 1:
        for m in range(R*C-M):
            G[m % R][m // R] = '.'
        G[0][0] = 'c'
        return G
    else:
        (rr, cc) = (0, 0)
        for r in range(2, R+1):
            for c in range(2, C+1):
                if r+r+c+c-4 <= R*C-M <= r*c:
                    (rr, cc) = (r, c)
                    break
            if rr:
                break
        if rr or cc:
            for r in range(rr):
                G[r][0] = G[r][1] = '.'
            for c in range(2, cc):
                G[0][c] = G[1][c] = '.'
            rem = R*C-M-rr-rr-cc-cc+4
            for r in range(2, rr):
                for c in range(2, cc):
                    if rem > 0:
                        G[r][c] = '.'
                    rem -= 1
            G[0][0] = 'c'
            return G
    return None

for t in range(int(input())):

    result = solve(*map(int, input().split()))

    print('Case #%d:' % (t+1))
    if result:
        for line in result:
            print(''.join(line))
    else:
        print('Impossible')

sys.stdin.close()
sys.stdout.close()

D. Deceitful War (14pt/16pt)

最后一道题，其实还没 C 难，是一个纯粹贪心的问题，田忌赛马升级版，直接就按照田忌赛马版解释题目吧：

我是田忌，对方是齐威王，我们各有 N 匹马。正常的游戏规则是：我先出马，要将真实的战斗力告诉齐威王，然后齐威王拿一个马跟我比，谁的马赢了得一分。

本来如果正常游戏，齐威王只要足够聪明，我是占不到便宜的，先在这样的情况下算一下这样我最多能得到多少分 y。

但是我会作弊，我偷窥了所有齐威王的马的战斗力，然后我出马的时候可以报一个假的数，但是原则是齐威王按照“最优策略”出一个马跟我比的时候，输赢结果必须跟那个马真的就是这个战斗力的情况一样（譬如说我报战斗力是 0.5，齐威王出个 0.6 的马跟我比输了，这样是不行的）。再算一下在作弊的情况下我最多能得多少分 x。

注：上面的 x, y 符号跟原题不同，以我代码里面的符号编号为准。

解法：

首先正常情况下很容易处理，先把两个战斗力数组排一下序，然后遍历我的马，然后齐威王在自己可以战胜的马里面挑一个最差的拿出来比，赢不了就随便拿一个（因为这样的话剩下的一个都赢不了了），这样算出来的就 OK 了。

然后，作弊的情况下，如果我要赢，我就必须先用最差的马把齐威王的最强的马消耗掉，消耗完之后剩下的马就从强到弱出。

但是我们计算的顺序跟出马的顺序不一样，我们只关心实际比赛的匹配，顺序先不管：从小到大遍历我的马，如果能够至少赢得到齐威王的任一只马，我们就加一分，然后两只马一起拿走（最终我们控制顺序肯定可以让最后实际比的就是这一对）。如果一只都赢不了，那我们可以唬齐威王拿最强的马干掉我最弱的马，这样的话把这只马跟齐威王最强的马一起拿走，我不加分。

这样的话操作也很简单，由于时间充裕，也没有怎么做查找的又花了（本来在常规模式下应该用 map 之类的结构，在作弊模式下应当用 deque 之类的结构才能保证效率最好，但我的代码里面直接没有管，但不影响结果），代码如下：

import sys

sys.stdin = open('D-large.in', 'r')
sys.stdout = open('d-large.out', 'w')

for t in range(int(input())):

    N = int(input())
    A = sorted(map(float, input().split()))
    B = sorted(map(float, input().split()))

    x = 0
    _B = B.copy()
    for a in A:
        if a > _B[0]:
            _B.pop(0)
            x += 1
        else:
            _B.pop()

    y = 0
    _B = B.copy()
    for a in A:
        lose = False
        for i in range(len(_B)):
            if _B[i] >= a:
                lose = True
                _B.pop(i)
                break
        if not lose:
            y += 1
            _B.pop()

    print('Case #%d: %d %d' % (t + 1, x, y))

sys.stdin.close()
sys.stdout.close()

然后这次比赛如无意外应该满贯了，希望是个好的开头，今年顺利把 Google 衣服拿到手。

---

【转载请附】愿以此功德，回向 >>

原文链接：http://www.huangwenchao.com.cn/2014/04/gcj-2014-qual.html【Google Code Jam 2014 – Qualification Round】