作者bleed1979 (十三)
站内Prob_Solve
标题[情报] Google Code Jam 2008 第一题解法
时间Thu Jul 17 23:38:02 2008
Google Code Jam 2008 第一题
前面的宇宙会被挤压的废话就不多说了
这题的大意是在N组测资内, 有S个搜寻引擎要依序搜索Q个字
第一个选定的引擎不列入计算(count=0)
开始搜索後, 如果碰到的字和引擎的名字是相同的话
可以换引擎继续搜索
求依序搜索完所有的字後, 所换引擎次数最少为多少
解法：
依次建立每个引擎不包括相同字的起点和终点
然後找终点最远的引擎来更换
范例：
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
起点(从1开始算) 终点
Yeehaw
3 10
NSM
1 5
7 7
9 10
Dont ask
1 8
10 10
B9
1 3
5 6
8 10
Googol
1 2
4 4
6 9
开始跑：
从1开始跑, 有4个引擎都有1, 但Dont ask终点到8为最大, 所以一开始选Dont ask
再来从9开始跑, 包含9的有Yeehaw, NSM, B9 因为都到10 所以任选一个皆可
而10就是case的终点
所以换的次数最少为1次
还有5小时 有报名的可以参考看看
Bleed
--
ACM's PARADISE
http://bleed1979.myweb.hinet.net/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.16.70
1F：→ poga:我是直接从头开始跑，判断哪边需要switch就好了 07/18 00:27
2F：→ poga:毕竟输出不需要包含用哪个engine 07/18 00:27
3F：推 powertodream:我在想 search从头扫到尾, 一直很greedy 07/18 03:43
4F：→ powertodream:engine 五个都出现表示要换, 这样会有问题吗@@?y 07/18 03:43
5F：推 netsphere:我也是用 greedy mathod 07/18 08:50
6F：推 ledia:greedy 的基本题呀, 下一题也是 07/18 09:36
7F：推 Romulus:greedy is ok 07/18 15:00
8F：推 redray:我比较想知道第三题怎麽解.. 07/18 18:11
9F：推 Frozenmouse:我比较想知道第二题怎麽解.. 07/18 20:39
10F：推 hcldesmond:greedy +1 07/19 01:51
11F：推 sasbluesea:greedy +1 07/19 14:37
12F：推 windows2k:我用DP来解 XD, 果真变迟钝了 07/19 22:39
13F：推 Frozenmouse:楼上(握) 当下不知怎麽不敢用greedy...orz 07/20 15:09
14F：推 Romulus:第二题就表全部建起来event-driven就好了 07/21 10:10