第三⼗届ACMICPC世界总决赛题⽬解析
第三⼗届ACM/ICPC 世界总决赛题⽬解析
斯坦福⼤学王颖
Problem A
本题的⼤意是，给出⼀些机票，每个机票都是⼀条路线，⽐如城市A->城市B->城市K->…->城市N，并且每张机票有⼀个价格。我们可以只⽤⼀张机票的⼀部分，⽐如城市A->城市B->城市K，然后就丢弃这张机票。但有两个条件，第⼀，必须在机票的起始城市才能使⽤机票，也就是说，我们不能⽤上⾯的机票从城市B到城市K；第⼆，如果使⽤了⼀张机票的部分，以后就不能使⽤剩下的部分。 现在给出⼀条路线，我们要按顺序访问⼀系列的城市。给出所有可以购买的机票，每种机票可以买⽆限张，问怎样可以⽤最少的花费完成整个旅途。
本题的数据规模颇⼩，机票最多20种，⽽每个机票最多经过10个城市。由于机票可以重复购买，城市必须按顺序经过，很容易想到要⽤动态规划。但从⽐赛过程中可以发现，⽆数的队伍被这题卡住了，⽽且很少的队伍能够⼀次通过。问题就在于，并不是只能访问指定路径上的城市，⽽是可以访问⼀些辅助的城市来减⼩花费。所以，我们要⽤⼀个⼆元组(i,j)来表⽰⼀个状态。其中i表⽰指定路径上已经按顺序访问
了的城市数量，j表⽰当前所在城市。通过机票的信息，不难得到状态之间的⼀个有向图，⽽我们要求的其实就是⼀个最短路径。注意到这个图是有圈的，所以我们不能直接⽤动态规划，⽽是需要⽤最短路算法。本题初看觉得规模甚⼩，此时则可以发现最多能有20*10=200个城市，共可以有10*200=2000个状态，还是颇有规模的。 总结：想清楚后此题并不复杂。但⽐赛时必须保持头脑清醒，分析清楚题意，才可能顺利解决此题。⽐赛中虽然很多队伍做出此题，但很少有队伍⼀次做对，更有⼀些队伍⼀直困在这题，可见⽐赛中队伍普遍紧张，没能仔细的去考虑。 Problem B
典型的最⼩费⽤最⼤流，不多说了。⼆分图匹配也可以，但得到的图规模太⼤。
实验室制硝酸Problem C
物理题，恐怕还需要不少计算⼏何。⽐赛的时候没⼈做，我也没仔细看。
Problem D
题⽬⼤意：形如a…ab…b的数叫做bipartite number，⽐如1222，333999999，50，8888，1等等都是。给出⼀个数字x(x<=99999），求
出x的最⼩的倍数n=kx(k>1)，使得n是bipartite number。
这是⼀道⽐较tricky的题⽬。⽐较容易想到的⽅法是，长度为p的bipartite number很有限，最多有p*9*10个，可以⼀直枚举上去，直到得
到x的倍数。但编程试验⼀下就会发现，有时候直到上千位也没出现x的倍数。主要问题在于，如果x的末尾是0，那么n的末尾也必须是0。⽐如x=99990，那么n会形如aa…a0，⽽且aa…a是9999的倍数，这时候，只有⼀个⾃由度，所以我们可以期望得到的答案的长度是O(x)的。此时如果我们还⽤枚举所有bipartite number的⽅法，最多可能枚举90*(9999^2)/2个数，时间上不能接受。
解决这个问题的办法是，可以看到此时末尾已经确定，所以我们只需要枚举前⾯的部分，这个是可以在O(x)的时间内完成的，可以接受。但出现了另⼀个问题，末尾究竟有⼏个0？有⼈可能认为，x的末尾有⼏个0，n的末尾就有同样数量的0。这是错误的。不妨考虑x=250，任何形如a…a0 (a>0)的数都不是250的倍数。因为a只可能等于5，⽽55不是25的倍数。所以，n的末尾可能还需要更多的0。经过分析不难发现，如果x末尾的0都去掉后还是16或者25的倍数，则我们需要更多的0。⽽当x是2，4，8的倍数，或者5的倍数的时候，额外的0并不是⼀定需要的，但可能使得解更⼩。此时我们需要枚举0的个数，不过最多枚举3种情况，时间上完全可以接受。
当x不是10的倍数的时候，bipartite number对x的余数可以看成是均匀分布的，此时直接枚举我们可以
期望在O(x)的时间内得到解。我编程试验过，对于x不是10的倍数的情况直接枚举⼏乎不需要时间。但是，为了保证得到的是最⼩解，必须注意枚举的顺序。
总结：⼀道很考验选⼿综合素质的题⽬。严谨的数学上的分析，对各种细节的处理，还有编程实现上的技巧都是⾮常必要的。上⾯的分析虽然很长，⼀旦想清楚了程序可以写得很短。
思考题：为什么这样的bipartite number⼀定存在？
Problem E
题⽬⼤意：给出⼀个01串和⼀个压缩⽅法：把所有连续的1替换成其长度的⼆进制表⽰，只要这样的替换能够缩短字符串。⽐
如1111101110010就会变成1010110010。现在给出压缩后的串（长度<=40），和压缩前的串长（<=16000）还有1的个数，问解码⽅法是否唯⼀。
可以动态规划。虽然原串中1的数量可能很多，但0的数量最多40个。所以状态最多16000*40*40个，⽽其中的⼤部分状态都不会出现。要注意的⼀点是，得到的原串不但要保证0和1的数量正确，也要保证能压缩的⽚段都被压缩了。
这题的规模不⼤，也可以考虑搜索。这样需要⼀些剪枝。这题各种剪枝的⽅法很多，但要做到在时限内得出正确结果也不容易。
Problem F长兴电视台
我没理解题⽬，看不懂齿轮的契合⽅式。感觉上是搜索或者解⽅程之类的题⽬。⽐赛的时候没什么⼈做，也没⼈做对。
Problem G
题⽬⼤意：Jack带了⼀帮⼈去朝圣。Jack是管钱的，他会遇到四种操作：pay，collect，in，out。pay就是付⼀定数量的钱，collect是从让每⼈交⼀定数量的钱，in是新加⼊若⼲⼈，每个⼈要交当前总钱数/当前总⼈数这么多钱。out是离开若⼲⼈，每个⼈拿⾛当前总钱数/当前总⼈数这么多钱。注意，in和out的时候，可能出现每个⼈平均的钱是分数的情况。题⽬中说，假设Jack很幸运，每次都正好整除了，问他开始可能带了多少⼈。
这题看似不好下⼿，不过我们可以认真的分析。不难发现会出问题的只是in和out这两种操作。假设第⼀次in或out（不妨假设是in p）的时候，我们有n个⼈，平均每个⼈的钱是k，那么in p之后，我们有n+p个⼈，每个⼈的钱还是k。collect操作不影响当前的整除性。不妨假设接下来两个操作分别是pay q
和in t，那么pay q后有n+p个⼈，每个⼈的钱是k-q/(n+p)。这必须是整数，因为下⼀个操作是in。所以n+p必须
是q的约数，从⽽n只可能有有限个。
从上⾯的分析不难得出结论，如果我们把in和out叫做critical operation，那么问题有有限个解当且仅当⾄少存在⼀个pay operation夹在两
个critical operation之间。
我们可以不断重复上⾯的步骤，把所有连续的critical operation之间的pay都合并起来（注意，collect操作对整除性没有任何影响），然后得出⼀系列整除式，每个都是形如(n+a)|b。不需要去求解整个系统，n⼀定是b-a的约数，所以对⼀个式⼦求出所有约数，然后代⼊其它式⼦检验即可。
这个算法似乎太简单了⼀点，⽐赛中不应该只有这么少的队伍做对。或许有些地⽅我没考虑到，⼤家不妨指正。
Problem H
似乎是⼀道挺⿇烦的折纸题，⽐赛的时候没⼈做。
Problem I
送分题。求两两间最短路中最长的⼀个。简单的floyd算法，放在topcoder绝对5分钟内⼀堆⼈做出来了。
Problem J
题⽬⼤意：给出⼀个有向图和两个点s1,s2，求⼀个最⼩的顶点的⼦集，使得在这个⼦集induce的⼦图中这两个点相互可达。
其实可以看成是我们要选择两条路径，⼀条从s1到s2，另⼀条从s2到s1，使得路径上出现的顶点数量最少。⾸先，s1和s2必须在⼦集中。让S(v1,v2)表⽰要使得v1,v2强连通必须选择的除v1,v2外的顶点个数，d(v1,v2)表⽰丛v1到v2的最短路，那么显然S(v1,v2)
遥远的拥抱<=d(v1,v2)+d(v2,v1)-2，因为如果两条最短路径没有重合的顶点，那么出现的顶点总数就是d(v1,v2)+d(v2,v1)-2。考虑有重合顶点的情况，不妨假设中间有⼀个点t，那么要让v1,v2强连通，我们可以让v1,t强连通并且t,v2强连通，所以S(v1,v2)<=S(v1,t)+S(v2,t)+1。如果
让T=S(v1,v2)+1，那么T(v1,v2)<=T(v1,t)+T(v2,t)。这看起来难道不熟悉么？这个就是说，我们可以把T(v1,v2)看成v1,v2间的⼀种最短路径。这样算法就变得清晰了，先⽤floyd算法求出d(i,j)，然后让T(i,j)钟信才
=d(i,j)+d(j,i)-1，再⽤⼀次floyd算法更新T(i,j)的值，最后的答案就
是T(s1,s2)+1。整个算法的主体部分不超过10⾏代码。
总结：
A,B,D,E,G,I都是属于“较好做”的题⽬，J属于算法性强的⼀道图论题，剩下三题不太好说难度，但⾄少不常规。Final中⼤家还是很谨慎的，不会轻易去做⼀道不常规的题，也不会轻易去做别⼈没做对过的题。虽然最后冠军是6题，但我觉得如果⼀些队伍其实有做出7题的实
⼒。Final这样的⽐赛，还是很看发挥。郑州牧专教务管理
A,B,D,E,G,I这6题中，I属于必对题，B属于基本题，A有⼀点trick，但也应该做对；D，E略为复杂，各有⼀些陷阱，但也属于该做对的题⽬。G只要仔细分析其实很简单。J题如果想出了算法，写程序只是5分钟的事。当然了，⽐赛中要做到这些，远⽐⼀个没有压⼒的旁观者分析的要难得多。
剩下的C,F,H三题基本没⼈做，我现在没有太多的时间所以也没细看，如果有⼈有想法请说出来吧。
敦煌学十八讲
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议