荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: duck (一棵树), 信区: ACMICPC
标 题: 国际大学生程序设计竞赛试题及专家解析
发信站: 荔园晨风BBS站 (Sat Apr 15 10:44:25 2006), 站内
试题是pdf和jpg图片格式的,在软件开发版FTP里
ftp://s:s@192.168.111.118:118
包括:
第三十届国际大学生程序设计竞赛试题
第二十九届国际大学生程序设计竞赛试题
第三十届国际大学生程序设计竞赛试题 Problem A-J (jpg格式)
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三题基本没人做，我现在没有太多的时间所以也没细看，如果有人有想法请说
出来吧。
解析转载自:http://blog.csdn.net/wuyingying/archive/2006/04/14/663690.aspx
--
▄▄▅ ▄▄▅▅▆ ▃▄▆ ▄▅█▅▄
▉ ▇ ▅▅▆ ▉ ▃▄▆ ▄▄▉▄▆
▊▂▇ ▊ ▊ ▊ ▉ ▌ ▌▌ ▊
▋ ▌ ▇▃█ ▋ ▋ █▃▄▅▋
▌▇ ▊ ▌ ▅▃▃ ▄
▊ ▉▉ ▊ ▌█▃▄▆ ▌
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.118]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店