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()
你解题思路好清晰啊!
楼主想问下,第二题得t<ans是什么意思啊。 我打印下了所有的时间 以例题中的C=30.0, F=2.0, X=100为例 其中all_time 是循环中的x/f+t 即总时间 t=0.000000,f=2,ans=50.000000, in loop,t=15.000000,f=4,ans=50.000000,all_time=40.000000 in loop,t=22.500000,f=6,ans=40.000000,all_time=39.166667 in loop,t=27.500000,f=8,ans=39.166667,all_time=40.000000 in loop,t=31.250000,f=10,ans=39.166667,all_time=41.250000 in loop,t=34.250000,f=12,ans=39.166667,all_time=42.583333 in loop,t=36.750000,f=14,ans=39.166667,all_time=43.892857 in loop,t=38.892857,f=16,ans=39.166667,all_time=45.142857 in loop,t=40.767857,f=18,ans=39.166667,all_time=46.323413 循环到第三次就出结果,之后的循环是什么意思? 我得思路是计算下一次循环后的总时间如果t(n)<t(n-1) n就是最后要买农场的个数,通过不等式变换得n<= xf-2c/cf , 然后计算买n个农场后 总时间