当前位置:首页 >> 学科竞赛 >> 信息学奥赛试题精选33题(附带题解)

信息学奥赛试题精选33题(附带题解)


基础题:
【1 Prime Frequency】

【问题描述】
给出一个仅包含字母和数字(0-9, A-Z 以及 a-z)的字符串,请您计算频率(字符出现 的次数) ,并仅报告哪些字符的频率是素数。 输入: 输入的第一行给出一个整数 T ( 0<T<201),表示测试用例个数。后面的 T 行每行给出一 个测试用例:一个字母-数

字组成的字符串。字符串的长度是小于 2001 的一个正整数。 输出: 对输入的每个测试用例输出一行,给出一个输出序列号,然后给出在输入的字符串中频 率是素数的字符。这些字符按字母升序排列。所谓“字母升序”意谓按 ASCII 值升序排列。 如果没有字符的频率是素数,输出“empty” (没有引号) 。 样例输入 3 ABCC AABBBBDDDDD ABCDFFFF 注: 试题来源:Bangladesh National Computer Programming Contest 在线测试:UVA 10789 样例输出 Case 1: C Case 2: AD Case 3: empty

提示

先离线计算出[2‥2200]的素数筛 u[]。然后每输入一个测试串,以 ASCLL 码为下标统计 各字符的频率 p[],并按照 ASCLL 码递增的顺序(0≤i≤299)输出频率为素数的字符(即 u [p[i]]=1 且 ASCLL 码值为 i 的字符) 。若没有频率为素数的字符,则输出失败信息。

【2 Twin Primes】 【问题描述】 双素数(Twin Primes)是形式为(p, p+2),术语“双素数”由 Paul St? ckel (1892-1919) 给出,前几个双素数是(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)。在本题中请你给 出第 S 对双素数,其中 S 是输入中给出的整数。 输入:

输入小于 10001 行,每行给出一个整数 S (1≤ S≤ 100000),表示双素数对的序列编号。 输入以 EOF 结束。 输出: 对于输入的每一行,输出一行,给出第 S 对双素数。输出对的形式为(p1,空格 p2),其中 “空格”是空格字符(ASCII 32)。本题设定第 100000 对的素数小于 20000000。 样例输入 1 2 3 4 注: 试题来源:Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Ba ngladesh 在线测试:UVA 10394 样例输出 (3, 5) (5, 7) (11, 13) (17, 19)

提示 设双素数对序列为 ans[]。其中 ans[i]存储第 i 对双素数的较小素数(1≤i≤num) 。ans[] 的计算方法如下: 使用筛选法计算出[2,20000000]的素数筛 u[]; 按递增顺序枚举该区间的每个整数 i:若 i 和 i+2 为双素数对(u[i]&&u[i+2]),则双素数 对序列增加一个元素(ans[++num]=i) 。 在离线计算出 ans[]的基础上,每输入一个编号 s,则代表的双素数对为(ans[s],ans[s]+ 2)。

【3 Less Prime】 【问题描述】 设 n 为一个整数,100≤n≤10000,请找到素数 x,x ≤ n,使得 n-p*x 最大,其中 p 是整 数,使得 p*x≤n<(p+1)*x。 输入: 输入的第一行给出一个整数 M,表示测试用例的个数。每个测试用例一行,给出一个 整数 N,100≤N≤10000。 输出: 对每个测试用例,输出一行,给出满足上述条件的素数。 样例输入 5 4399 样例输出 2203 311

614 8201 101 7048 注:

4111 53 3527

试题来源:III Local Contest in Murcia 2005 在线测试:UVA 10852

提示

要使得 n-p*x 最大(x 为素数,p 为整数,p*x ≤ n<(p+1)*x) ,则 x 为所有小于 n 的素 数中,被 n 除后余数最大的一个素数。由此得出算法: 先离线计算出[2‥11111]的素数表 su[],表长为 num。然后每输入一个整数 n,则枚举

{n % su[i ] su[i ] ? n} , 小于 n 的所有素数, 计算 tmp= max 满足条件的素数即为对应 tmp=n% 1? i ? num
su[k]的素数 su[k]。

【4 Prime Words】 【问题描述】 一个素数是仅有两个约数的数:其本身和数字 1。例如,1, 2, 3, 5, 17, 101 和 10007 是 素数。 本题输入一个单词集合,每个单词由 a-z 以及 A-Z 的字母组成。每个字母对应一个特定 的值,字母 a 对应 1,字母 b 对应 2,以此类推,字母 z 对应 26;同样,字母 A 对应 27, 字母 B 对应 28,字母 Z 对应 52。 一个单词的字母的总和是素数,则这个单词是素单词(prime word) 。请编写程序,判 定一个单词是否为素单词。 输入: 输入给出一个单词集合,每个单词一行,有 L 个字母,1≤L≤20。输入以 EOF 结束。 输出: 如果一个单词字母的和为素数,则输出“It is a prime word.” ;否则输出“It is not a prime word.” 。 样例输入 UFRN contest AcM 注: 试题来源:UFRN-2005 Contest 1 样例输出 It is a prime word. It is not a prime word. It is not a prime word.

在线测试:UVA 10924

提示

由于字母对应数字的上限为 52,而单词的长度上限为 20,因此我们首先使用筛选法, 离线计算出[2‥1010]的素数素数筛 u[]。 然后每输入一个长度为 n 的单词,计算单词字母对应的数字和 X=

?
i ?1

n

s[i ]?' a'?1 s[i ] ? {' a'..' z' }, s[i ]?' A'?27 s[i ] ? {' A'..' Z ' }

若 x 为[2‥1010]中的一个素数(u[x]=1) ,则表明该单词为素单词;否则该单词非素单 词。

【5 Sum of Different Primes】 【问题描述】 一个正整数可以以一种或多种方式表示为不同素数的总和。给出两个正整数 n 和 k,请 您计算将 n 表示为 k 个不同的素数的和会有几种形式。如果是相同的素数集,则被认为是 相同的。例如 8 可以被表示为 3 + 5 和 5 + 3,但不区分。 如果 n 和 k 分别为 24 和 3,答案为 2,因为有两个总和为 24 的集合 {2, 3, 19}和{2, 5, 17} ,但不存在其他的总和为 24 的 3 个素数的集合。如果 n = 24,k = 2,答案是 3,因 为存在 3 个集合{5, 19}, {7, 17}以及{11, 13}。如果 n = 2,k = 1,答案是 1,因为只有一 个集合{2} ,其总和为 2。如果 n = 1,k = 1,答案是 0,因为 1 不是素数,不能将{1}计 入。如果 n = 4,k = 2,答案是 0,因为不存在两个不同素数的集合,总和为 4。 请您编写一个程序,对给出的 n 和 k,输出答案。 输入: 输入由一系列的测试用例组成, 最后以一个空格分开的两个 0 结束。 每个测试用例一行, 给出以一个空格分开的两个正整数 n 和 k。本题设定 n ≤ 1120,k ≤ 14。 输出: 输出由若干行组成,每行对应一个测试用例,一个输出行给出一个非负整数,表示对相 应输入中给出的 n 和 k 有多少答案。本题设定答案小于 231。 样例输入 24 3 24 2 2 1 1 1 4 2 18 3 17 1 样例输出 2 3 1 0 0 2 1

17 3 17 4 100 5 1000 10 1120 14 0 0 注: 试题来源:ACM Japan 2006

0 1 55 200102899 2079324314

在线测试:POJ 3132,ZOJ 2822,UVA 3619

提示

设 su[]为[2..1200]的素数表;f[i][j]为 j 拆分成 i 个素数和的方案数(1≤i≤14, su[i]≤j≤1199)。 显然,边界值 f[0][0]=1。 首先,采用筛选法计算素数表 su[],表长为 num。然后每输入一对 n 和 k,使用动态规 划方法计算 k 个不同素数的和为 n 的方案总数: 枚举 su[]表中的每个素数 su[i](1≤i≤num) 按递减顺序枚举素数个数 j(j=14‥1): 按递减顺序枚举前 j 个素数的和 p(p=1199‥su[i]): 累计 su[i]作为第 j 个素数的方案总数 f[j][p]+=f[j-1][p-su[i]]; 最后得出的 f[k][n]即为问题解。 【6 Common Permutation】

【问题描述】
给出两个小写字母的字符串,a 和 b,输出最长的小写字母字符串 x 使得存在 x 的一个排 列,是 a 的子序列,同时也存在 x 的一个排列是 b 的子序列。 输入: 输入有若干行。连续的两行组成一个测试用例,也就是说,第 1 和第 2 行构成一个测试 用例,第 3 和第 4 行构成一个测试用例,等等。每个测试用例的第一行是字符串 a,第二行 是字符串 b。每个字符串一行,至多由 1000 个小写字母组成。 输出: 对每个测试用例,输出一行,给出 x。如果有若干个 x 满足上述要求,选择按字母序列 第一个。 样例输入 pretty women walking down 样例输出 e nw et

the street 注: 试题来源:World Finals Warm-up Contest, University of Alberta Local Contest 在线测试:UVA 10252

提示

试题要求按递增顺序输出两串公共字符的排列。计算方法如下: 设 S1=a1a2… a la ,S2= b1b2… blb 。 先分别统计 S1 中各字母的频率 c1[i]和 S2 中各字母的频率 c2[i](1≤i≤26,其中字母 ‘a’对应数字 1, 字母‘b’对应数字 2,…,字母‘z’对应数字 26) 。 然后计算 S1 和 S2 的公共字符的排列:递增枚举 i(1≤i≤26),若 i 对应的字母在 S1 和 S2 中同时存在( (c1[i]≠0)&&(c2[i]≠0) ),则字母'a'+i 在排列中出现 k=min{c1[i],c2[i]} 次。

【7 Anagram】

【问题描述】
给出一个字母的集合,请您编写一个程序,产生从这个集合能构成的所有可能的单词。 例如: 给出单词"abc", 您的程序产生这三个字母的所有不同的组合——输出单词"abc", "acb", "bac", "bca", "cab" 和"cba"。 程序从输入中获取一个单词,其中的一些字母会出现一次以上。对一个给出的单词,程 序产生相同的单词只能一次,而且这些单词按字母升序排列。 输入: 输入给出若干单词。第一行给出单词数,然后每行给出一个单词。一个单词是由 A 到 Z 的大写或小写字母组成。大写字母和小写字母被认为是不同的,每个单词的长度小于 13。 输出: 对输入中的每个单词,输出这个单词的字母产生的所有不同的单词。输出的单词按字母 升序排列。大写字母排在相应的小写字母前,即'A'<'a'<'B'<'b'<...<'Z'<'z'。 样例输入 3 aAb abc acba 样例输出 Aab Aba aAb abA bAa baA abc acb bac bca

cab cba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa 注: 试题来源:ACM Southwestern European Regional Contest 1995 在线测试:POJ 1256,UVA 195

提示

建立字母与整数间的对应关系: 字母‘a’对应 0,字母‘A’对应 1;…;字母‘z’对应 50,字母‘Z’对应 51。 为了按照字母升序的要求生成单词的所有排列, 首先将单词的所有字母转化为数字, 然 后递增排序数串,排列中每个位置的数字按由左而右顺序从数串中选择。 设单词长度为 l,数串的第 i 个位置已访问标志为 v1[i],初始时 v1[]清零;数字 k 对应 的字母已使用标志为 v2[k],v2[]为递归程序内的局部变量(0≤i≤l-1,0≤k≤51)。 生成所有排列的计算过程为一个递归子程序: void dfs(int d){ //从当前位置 d 出发,递归计算单词的所有排列 if (d==l) 输出当前数字排列对应的单词; //生成单词的一个排列 }else{ v2[]清零; //所有字母未确定 for(int i=0;i<l;i++){ //按由左而右顺序从数串中选择 d 位置的 字母:若数串的第 i 个位置未访问且对应字母未在排列中出现,则设访问标志,该字符进入 排列中的第 d 个位置 if(!v1[i]&&!v2[i 位置字母对应的数字]){ v1[i]=1;v2[i 位置字母对应的数字]=1; i 位置字母对应的数字放入当前排列的 d 位置; dfs(d+1); //递归排列的第 d+1 个位置 v1[i]=0; //恢复数串的第 i 个位置未访问标志 } } } }

显然,主程序设数串的所有位置未访问(v1[]清零),递归调用 dfs(0),便可按字母升 序要求输出单词的所有排列。

【8 How Many Points of Intersection?】

【问题描述】
给出两行,在第一行有 a 个点,在第二行有 b 个点。我们用直线将第一行的每个点与第 二行的每个点相连接。 这些点以这样的方式排列, 使得这些线段之间相交的数量最大。 为此, 不允许两条以上的线段在一个点上相交。 在第一行和第二行中的相交点不被计入, 在两行之 间允许两条以上的线段相交。给出 a 和 b 的值,请计算 P(a, b),在两行之间相交的数量。例 如,在下图中 a = 2,b = 3,该图表示 P(2, 3) = 3。

输入: 输入的每行给出两个整数 a ( 0<a?20000)和 b ( 0< b?20000)。输入以 a=b=0 的一行为结 束标志,这一测试用例不用处理。测试用例数最多 1200 个。 输出: 对输入的每一行,输出一行,给出序列编号,然后给出 P(a, b)的值。本题设定输出值在 64 位有符号整数范围内。 样例输入 22 23 33 00 样例输出 Case 1: 1 Case 2: 3 Case 3: 9

注: 试题来源:Bangladesh National Computer Programming Contest, 2004 在线测试:UVA 10790

提示

如 3 线交于一点, 则一定可以通过左右移动一个点使其交点分开, 上面线段上的两点与 下面线段上的两点可以产生一个交点。按照乘法原理,p(a,b)=错误!未找到引用源。 。 【9 Stripies】

【问题描述】

生化学家发明了一种很有用途的生物体,叫 stripies , (实际上,最早的俄罗斯名叫 polosatiki ,不过科学家为了申请国际专利时方便不得不起了另一个英文名) 。stripies 是透 明,无定型的,群居在一些象果子冻那样的有营养的环境里。在大部分时间 stripies 是在移 动中,当两条 stripies 碰撞时,这两条 stripies 就融合产生一条新的 stripies。经过长时间的观 察,科学家们发现当两条 stripies 碰撞融合在一起时,新的 stripies 的重量并不等于碰撞前两 条 stripies 的重量。不久又发现两条重量为 m1 和 m2 的 stripies 碰撞融合在一起,其重量变 为 2*sqrt(m1*m2)。科学家很希望知道有什么办法可以限制一群 stripies 的总重量的减少。 请您编写程序来解决这个问题。本题设定 3 条或更多的 stripies 从来不会碰撞在一起。 输入: 第一行给出 N (1 ≤ N ≤ 100), 表示群落中 stripies 的数量。 后面的 N 行每行为一条 stripie 的重量,范围为 1-1000。 输出: 输出 stripies 群落可能的最小总重量。 精确到小数点后 3 位。 样例输入 3 72 30 50 注: 试题来源:ACM Northeastern Europe 2001, Northern Subregion 在线测试:POJ 1862,ZOJ 1543,Ural 1161 样例输出 120.00

提示 设群落中 n 条 stripies 的重量为 m1m2‥mn。经过 n-1 次碰撞后的总重量为 W= 2 n ?1 (( m1m2 ) 2
1 n ?1

m3 2n ?2 ? mn2 )

1

1

显然,m1m2‥mn 按照重量递减的顺序排列,得出的总重量 w 是最小的。

【10 The Product of Digits】

【问题描述】
请您寻找一个最小的正整数 Q,Q 的各个位置上的数字乘积等于 N。 输入: 输入给出一个整数 N (0 ≤ N ≤ 109)。 输出: 输出一个整数 Q,如果这个数不存在,则输出?1。

样例输入 10 注: 试题来源:USU Local Contest 1999 在线测试:Ural 1014

样例输出 25

提示 分解 N 的因子的度量标准:尽量分解出大因子。 注意,有两个特例: N=0 时,Q=0; N=1 时,Q=1; 否则采取贪心策略,按从 9 到 2 的顺序分解 n 的因子:先试将 n 分解出尽量多的因子 9, 再试分解出尽量多的因子 8?。若最终分解后的结果不为 1,则无解;否则因子由小到大组 成最小的正整数 Q。

提高题:
【11 Democracy in Danger】

【问题描述】
在 Caribbean 盆地中的一个国家, 所有的决策是由在公民大会上简单的多数投票被通过 的。当地的一个政党,希望权力尽可能地合法,要求改革选举制度。他们主要论点是,岛上 的居民最近增加了,它不再轻易举行公民大会。 改革的方式如下:投票者被分成 K 个组(不一定相等) ,在每个组中对每个问题进行投 票,而且,如果一个组半数以上的成员投“赞成”票,那么这个组就被认为投“赞成”票, 否则这个组就被认为投“反对”票。如果超过半数的组投“赞成”票,决议就被通过。 开始岛上的居民高兴地接受了这一做法,然而,引入这一做法的党派,可以影响投票组的构 成。因此,他们就有机会对不是多数赞同的决策施加影响。 例如,有 3 个投票组,人数分别是有 5 人,5 人和 7 人,那么,对于一个政党,只要在 第一组和第二组各有 3 人支持就足够了, 有 6 个人赞成, 而不是 9 个人赞成, 决议就能通过。 请您编写程序,根据给出的组数和每组的人数,计算通过决议至少需要多少人赞成。 输入: 第一行给出 K,表示组数(K≤101) ;第二行给出 K 个数,分别是每一组的人数。K 以 及每组的人数都是奇数。总人数不会超过 9999 人。 输出: 支持某个党派对决策产生影响至少需要的人数。

样例输入 3 575 注: 试题来源:Autumn School Contest 2000 在线测试:Ural 1025

样例输出 6

提示 把每组人数从小到大排序, 总共 n 组, 则需要有 ? ? +1 组同意, 即人数最少的前 ? ? +1 2 2 组。对于一个人数为 k 的组需要同意,则需要有 ? ? +1 人同意。 2 由此得出贪心策略:人数最少的前 ? ? +1 组中,每组取半数刚过的人数。 2

?n? ? ?

?n? ? ?

?k ? ? ?

?n? ? ?

【12 Box of Bricks】

【问题描述】
小 Bob 喜欢玩方块砖, 他把砖一块放在另一块的上面堆砌起来, 堆成不同高度的栈。 “看, 我建了一面墙” ,他告诉他的姐姐 Alice。 “不,你要让所有的栈有相同的高度,这样你就建 了一面真正的墙了。 ” Alice 反驳说。Bob 考虑了一下,认为他姐姐是对的。因此他开始重 新一块接一块地重新安排砖块,让所有的栈有着相同的高度。但由于 Bob 很懒惰,他要移 动砖块的数量最少。你能帮助他吗?

输入: 输入由若干组测试用例组成。每组测试用例的第一行给出整数 n,表示 Bob 建的栈的数 目。下一行给出 n 个数字,表示 n 个栈的高度 hi,本题 设定 1 ≤ n ≤ 50,并且 1 ≤ hi ≤ 100。 砖块的总数除以栈的数目是可除尽的。 也就是说, 重新安排砖块使得所有的栈有相同的高度 是可以的。 输入由 n = 0 作为结束,程序对此不必处理。 输出:

对每个测试用例,首先如样例输出所示,输出测试用例编号。然后输出一行 "The minimum number of moves is k.",其中 k 是移动砖块使得所有的栈高度相同的最小数。在每 个测试用例后输出一个空行。 样例输入 6 524175 0 注: 试题来源:ACM Southwestern European Regional Contest 1997 在线测试:POJ 1477,ZOJ 1251,UVA 591 样例输出 Set #1 The minimum number of moves is 5.

提示

设平均值 avg=

?h
i ?1

n

i

n

,avg 即为移动后栈的相同高度。

第 i 个栈中砖头被移动的度量标准:若 hi>avg,则栈中有 hi-avg 块砖头被移动。 贪心使用这个度量标准是正确的,因为砖头被移动至高度低于 avg 的栈中。由于砖块总 数除以栈的数目是可除尽的, 因此这些栈中的砖头是不须再移动的。 由此得出最少移动的砖 数 ans=

? (h ? avg h
i i ?1

n

i

? avg)

【13 Minimal coverage】

【问题描述】
给出直线的若干条线段,直线是 X 轴,线段的坐标为[Li, Ri]。求最少要用多少条线段可 以覆盖区间[0, m]。 输入: 输入的第一行给出测试用例的数目,后面给出一个空行。 每个测试用例首先给出一个整数 M(1≤M≤5000) ,接下来若干行,每行以 "Li Ri"(|Li|, |Ri|≤50000, i≤100000)表示线段。每个测试用例以“0 0”为结束。 两个测试用例之间用一个空行分开。 输出: 对每个测试用例,输出的第一行是一个数字,表示覆盖区间[0, m]的最少线段数。接下 来若干行表示选择的线段,给出线段的坐标,按左端(Li)排序。程序不处理"0 0"。若无解, 即[0, m]不可能被给出的线段覆盖,则输出"0"(没有引号) 。 在两个连续的测试用例之间输出一个空行。

样例输入 2 1 -1 0 -5 -3 25 00 1 -1 0 01 00 注:

样例输出 0 1 01

试题来源:USU Internal Contest March'2004 在线测试:UVA 10020,Ural 1303

提示 把所有线段按左端点为第一关键字、右端点为第 2 关键字递增排序( (Li≤Li+1||(( Li == Li+1)&&( Ri< Ri+1)),1≤i≤线段数-1) 。 选取覆盖线段的度量标准:在所有左端点被覆盖线段中找右端点最远的线段。 贪心实现的过程: 设当前线段覆盖到的位置为 now; 所有左端点被覆盖的线段中可以覆盖最远的位置为 len,该线段为 k。初始时 ans=now=len=0。 依次分析序列中的每条线段: if (Li≤now)&&(len< Ri){ len= Ri;k=i;} if (Li+1 >now) &&(now<len){ now=len ;将线段 k 作为新增的覆盖线段 } if (now≥m)输出覆盖线段并退出程序; 分析了所有线段后 now<m,说明无法覆盖[0, m],无解退出。

【14 Annoying painting tool】

【问题描述】

你想知道一个恼人的绘画工具是什么吗?首先,本题所讲的绘画工具仅支持黑色和白 色,因此,图片是一个像素组成的矩形区域,像素不是黑色就是白色。其次,只有一个操作 改变像素的颜色: 选择一个 r 行 c 列的像素组成的矩形,这个矩形是完全在一个图片内。作为操作的一个 结果,在矩形内的每个像素会改变其颜色(从黑到白,从白到黑) 。 最初,所有的像素是白色的。创建一个图片,应用上述的操作数次。你能描绘出你心目 的那幅图片吗? 输入: 输入包含若干测试用例。每个测试用例的第一行给出 4 个整数 n,m,r 和 c, (1 ≤ r ≤ n ≤ 100, 1 ≤ c ≤ m ≤ 100) ,然后的 n 行每行给出您要画的图的一行像素。第 i 行由 m 个字符组 成,描述在结束绘画时第 i 行的像素值('0'表示白色,'1'表示黑色)。 最后一个测试用例后的一行给出 4 个 0。 输出: 对每个测试用例,输出产生最终绘画结果需要操作的最小数;如果不可能,输出-1。 样例输入 3311 010 101 010 4321 011 110 011 110 3422 0110 0111 0000 0000 注: 试题来源:Ulm Local 2007 在线测试:POJ 3363 样例输出 4 6 -1

提示 进行一次操作的度量标准:当前子矩阵左上角的像素和目标矩阵的对应像素的颜色不 同。贪心实现的方法如下

由左而右、自上而下枚举子矩阵的左上角 a[i][j] (1≤i≤n-r+1,1≤j≤m-c+1): 若左上角像素的颜色与目标矩阵对应元素的颜色不同(a[i][j]!=b[i][j]) ,则操作次 数 c+1;子矩阵内所有像素的颜色取反(a[k][l]^=1,i≤k≤i+k-1,j≤l≤j+c-1) 。 最后再检验一遍当前矩阵 a[][]和目标矩阵 b[][]是否完全一样。 若还有不一样的地方, 则说明无解;否则 c 为产生最终绘画结果需要操作的最少次数。

【15 Troublemakers】

【问题描述】
每所学校都有麻烦制造者(troublemaker) —— 那些孩子们可以使教师的生活苦不堪 言。一个麻烦制造者还是可以管理的,但是当你把若干对麻烦制造者放在同一个房间里,教 学就变得非常困难。在 Shaida 夫人的数学课上有 n 个孩子,其中有 m 对麻烦制造者。情况 变得如此的差,使得 Shaida 夫人决定将一个班级分成两个班级。请您帮 Shaida 夫人将麻烦 制造者的对数减少至少一半。 输入: 输入的第一行给出测试用例数 N,然后给出 N 个测试用例。每个测试用例的第一行给出 n (0≤n≤100)和 m (0<m<5000),然后 m 行每行给出一对整数 u 和 v,表示 u 和 v 在同一个房 间里的时候,他们是一对麻烦制造者。孩子编号从 1 到 n。 输出: 对于每个测试用例,先输出一行"Case #x:",后面给出 L ——要转到另一间房间的孩子 的数目,下一行列出那些孩子。在两个房间中麻烦制造者对数的总数至多是 m/2。如果不可 能,则输出"Impossible."代替 L,然后输出一个空行。 样例输入 2 43 12 23 34 46 12 13 14 23 24 34 样例输出 Case #1: 3 134 Case #2: 2 12

注: 试题来源:Abednego's Graph Lovers' Contest, 2006 在线测试:UVA 10982

提示 以孩子为节点, 每对麻烦制造者之间连边, 构造无向图 g。 设两个班级分别对应集合 s[0] 和集合 s[1],其中 s[1]中的人数较少。 依次确定每个孩子 i(1≤i≤n)所在的班级:将孩子 1‥孩子 i-1 中与孩子 i 结对制造麻 烦的孩子划分成 s[0]和 s[1]集合。若 s[1]中的孩子数较少,则孩子 i 送入 s[1]集合,这就 是孩子 i 转移到另一间房间的度量标准。贪心实现的方法是 依次搜索每个节点 i(1≤i≤n) : 统计节点 1‥i-1 中与节点 i 有边相连的点在集合 s[0]和集合 s[1]的点数; 若 s[1]中的点数较少,则节点 i 送入 s[1]集合; 最后 s[1]集合中的节点对应要转到另一间房间的孩子。

【16 Constructing BST】

【问题描述】
BST (Binary Search Tree, 二叉搜索树) 是一个用于搜索的有效的数据结构。 在一个 BST 中,所有左子树中的元素小于根,右子树中的元素大于根。

我们通常通过连续地插入元素来构造 BST,而插入元素的顺序对于树的结构有很大的 影响。请看下例:

在本题中,我们要给出从 1 到 N 的整数来构造 BST,使得树的高度至多为 H。BST 的高度 定义如下: 1. 没有结点的 BST 的高度为 0; 2. 否则,BST 的高度等于左子树和右子树的高度的最大值加 1。 可以存在若干顺序可以满足这一要求。在这种情况下,取小数字排在前的序列。例如, 对于 N=4,H=3,我们给出的序列是 1 3 2 4,而不是 2 1 4 3 或 3 2 1 4。 输入: 每个测试用例给出两个正整数 N(1≤N≤10000)和 H(1≤H≤30) 。输入以 N=0,H=0 结 束,这一情况不用处理。至多有 30 个测试用例。 输出: 对于每个测试用例,输出一行,以“Case #: “开始,其中?#?是测试用例的编号;然后在 这一行中给出 N 个整数的序列,在一行的结束没有多余的空格。如果无法构造这样的树, 则输出“Impossible.”(没有引号) 。 样例输入 43 41 63 00 注: 试题来源:ACM ICPC World Finals Warmup 1,2005 在线测试:UVA 10821 样例输出 Case 1: 1 3 2 4 Case 2: Impossible. Case 3: 3 1 2 5 4 6

提示 试题要求输出 BST 的前序遍历,即第一个输出根。因为要求字典序最小,所以要让根尽 量小。 对于把编号为 1 到 n 的节点排成一个高度不高于 h 的 bst, 左右子树的节点数不应超过 2 -1。根节点的度量标准是 若根的右侧可以放满节点,则根的编号 root 为 n-(2 -1);否则根的编号 root 为 1, 即根编号 root=max{1,n-(2 -1)}。
h-1 h-1 h-1

之后问题就转化成了把编号为 1 到 root-1 的节点排成一个高度不高于 h-1 的左 bst 子 树和把编号为 root+1 到 n 的节点排成一个高度不高于 h-1 的右 bst 子树。 上述贪心解法是递归定义的,可递归解决。
【17 Ordering Tasks】

John 有 n 项任务要做。不幸的是,这些任务并不是独立的,有的任务只有在其他一些任 务完成以后才能开始做。 输入: 输入由几个测试用例组成。每个用例的第一行给出两个整数:1≤n≤100 和 m。n 是任务 的数量 (从 1 到 n 编号),m 是在两个任务之间直接优先关系的数量。然后是 m 行,每行两 个整数 i 和 j,表示任务 i 必须在任务 j 之前执行。以实例 n=m=0 结束输入。 输出: 对每个测试用例,输出一行,给出 n 个整数,表示任务执行的一个可能的顺序。 样例输入 54 12 23 13 15 00 注: 试题来源:GWCF Contest 2 (Golden Wedding Contest Festival) 在线测试:UVA 10305
提示

样例输出 14253

任务作为节点, 两个任务之间的直接优先关系作为边: 若任务 i 必须在任务 j 之前执行, 则对应有向边<i-1,j-1>,这样可将任务间的先后关系转化为一张有向图,使得任务执行的 一个可能的顺序对应这张有向图的拓扑排序。设 节点的入度序列为 ind[],其中节点 i 的入度为 ind[i](0≤i≤n-1); 邻接表为 lis[], 其中节点 i 的所有出边的另一端点存储在 lis[i]中, lis[i]为一个 List 容器 队列 q 存储当前入度为 0 的节点,队首指针为 h,队尾指针为 t; 我们在输入信息的同时构建邻接表 lis[], 计算节点的入度序列为 ind[], 并将所有入度 为 0 的节点送入队列 q; 然后依次处理 q 队列中每个入度为 0 的节点: 取出队首节点 x; lis[x]容器中每个相邻节点的入度-1,相当于删除 x 的所有出边; 新增入度为 0 的节点入 q 队列;

依次类推,直至队列空为止。相继出队的节点 q[0]‥q[n-1] 即为一个拓扑序列。

【18 Spreadsheet】

在 1979 年,Dan Bricklin 和 Bob Frankston 编写了第一个电子制表应用软件 VisiCalc,这 一软件获得了巨大的成功,并且在那时成为 Apple II 计算机的重要应用软件。现在电子制表 是大多数计算机的重要的应用软件。 电子制表的思想非常简单,但非常实用。一个电子制表由一个表格组成,每个项不是一 个数字就是一个公式。 一个公式可以基于其他项的值计算一个表达式。 文本和图形也可以加 入用于表示。 请编写一个非常简单的电子制表应用程序,输入若干份表格,表格的每一个项或者是数 字(仅为整数) ,或者是支持求和的公式。在计算了所有公式的值以后,程序输出结果表格, 所有的公式都已经被它们的值代替。 输入: 输入文件第一行给出测试用例中的表格的数目。每个表格的第一行给出用一个空格分开 的两个整数,表示表格的列数和行数,然后给出表格,每行表示表格的一行,每行由该行的 项组成,每个项用一个空格分开。 一个项或者是一个数字值,或者是一个公式。一个公式由一个等号开始(=),后面是一个 或多个用加号(+)分开的项的名称,这样公式的值是在相应的项中的所有值的总和。这些项 也可以是一个公式,在公式中没有空格。 可以设定在这些项之间没有循环依赖,因此每个表格可以是完全可计算的。 每一个项的名字是由 1 到 3 个字母(按列) ,后面跟着数字从 1 到 999(按行)组成。按 列的字母构成如下序列:A, B, C, ..., Z, AA, AB, AC, ..., AZ, BA, ..., BZ, CA, ..., ZZ, AAA, AAB, ..., AAZ, ABA, ..., ABZ, ACA, ..., ZZZ。这些字母相应于从 1 到 18278 的数字,如图所 示,左上角的项取名为 A1。

左上方的项的命名 图 输出: 除了表格的数目以及列和行的数目不重复以外,程序输出和输入的格式一样。而且,所 有的公式要被它们的值取代。 样例输入 样例输出

1 43 10 34 37 =A1+B1+C1 40 17 34 =A2+B2+C2 =A1+A2 =B1+B2 =C1+C2 =D1+D2 注:

10 34 37 81 40 17 34 91 50 51 71 172

试题来源:1995 ACM Southwestern European Regional Contest 在线测试:POJ 1420,UVA 196
提示

在表达式中各项的命名格式,字母 A?ZZZ 代表列,数字 1?999 代表行。需要将列字母 转化为列序号,行数串转化为行序号。转化方法: A 代表 1, ?Z 代表 26, 字母序列 ck‥c1 对应一个 26 进制的列序号 y=

? (c
i ?1

k

i

? 64) * 26 i ?1 ;

数串 bp‥b1 应一个十进制的行序号 x=

? (b
i ?1

p

i

? 48) * 10 i ?1 。

即表达式中的项 ck‥c1 bp‥b1 对应表格位置(x,y) 。 设 数值表格为 w[][]; 表达式项所在位置值为 d, (i,j)对应位置值 d=j*1000+i,即 d % 1000 为行号,

? d ? ?1000 ? 为列号。 ? ?
我们将表格转化为一个有向图: 每项为一个节点, 数值项与表达式项间的关联关系为有 向边。若数值项(x,y)对应表达式项(i,j)中的某项,则(x,y)连一条有向边至(i,j) 。 设 相邻矩阵为 g,其中 g[x][y]存储与数值项(x,y)关联的所有表达式项的位置值; 表达式项的入度序列为 ind,即(i,j)中的表达式目前含 ind[i][j]个未知项。显然 ind[i][j]==0,表明(i,j)为数值项; ①构造有向图 我们边输入表格边构造有向图:若(i,j)为数值项,则数值存入 w[i][j];若(i,j) 为表达式项, 则取出其中的每一项, 计算其对应的行号 x 和列号 y, (i,j) 的位置值送入 g[x][y] 邻接表,并累计(i,j)的入度(++ind[i][j]) 。 ②使用删边法计算有向图的拓扑序列 首先将图中所有入度为 0 的节点(数值项)的位置值送入队列 q;然后依次按下述方法 处理队列中的每一项: 取出队首节点的位置值,将之转化为(x,y) 。依次取 g[x][y]中与数值项(x,y)相关

联的每个表达式项的位置值,转化为表格位置(tx,ty), 将(x,y)的值计入(tx,ty)中 的表达式项(w[tx][ty]+=w[x][y]) , (tx,ty)的入度-1(--ind[tx][ty]) 。若入度减至 0, 则(tx,ty)的位置值送入 q 队列。 依次类推,直至队列空为止。最后输出数值表格 w。

【19 Genealogical Tree】

火星人直系亲属关系的系统非常混乱。火星人在不同的群体中群居生活,因此一个火星 人可以有一个父母, 甚至也可以有十个父母; 而且一个火星人有 100 个孩子也不会让人感到 奇怪。火星人已经习惯了这样的生活方式,对于他们来说这很自然。 在行星理事会(Planetary Council)中,这样混乱的家谱系统导致了一些尴尬。这些火星 人中的杰出人士去参加会议, 为了在讨论中不冒犯长辈, 讨论中总是辈分高的火星人优先发 言,然后是辈分低的火星人发言,最后是辈分最低还没有子女的火星人发言。然而,这个秩 序的维持确实不是一个简单的任务。 一个火星人并不知道他所有的父母 (当然也不知道他的 所有的祖父母) , 但如果一个孙子在比他年轻的曾祖父之前发言, 这就是一个重大的错误了。 请编写一个程序,对所有的成员定义一个次序,这个次序要保证理事会的每一个成员所 在的位置先于他的所有后代。 输入: 标准输入的第一行只包含一个整数 N,1≤N≤100,表示火星理事会(Martian Planetary Council)的成员数。理事会成员的编号从 1 到 N。在后面给出 N 行,而且第 i 行给出第 i 个 成员的孩子的列表。 孩子的列表是孩子编号按任意次序用空格分开的一个序列。 孩子的列表 可以为空。列表(即使是空列表)以 0 结束。 输出: 标准输出仅给出一行,给出一个编号的序列,编号以空格分开。如果存在几个序列满足 这一问题的条件,请输出其中任何一个。这样的序列至少存在一个。 样例输入 5 0 4510 10 530 30 注: 试题来源:Ural State University Internal Contest October'2000 Junior Session 在线测试:Ural 1022
提示

样例输出 2 4531

将火星人设为节点, 父亲与儿子之间连一条有向边。 这个有向图的拓扑序列即为所有成

员的次序。 我们边输入信息边构造相邻矩阵 g,并统计节点的入度序列 ind(其中 g[x]存储 x 的所 有儿子,ind[x]为节点 x 的入度值) 。 接下来,将所有入度为 0 的节点送入队列 q 。然后依次处理队列 q 中的每个节点: 取队首节点 x;x 的每个儿子的入度-1。若减至 0,则该儿子进入队列 q; 依次类推,直至队列空为止。 最后输出输出拓扑序列,即 q 的出队顺序。

【20 Rare Order】

一个珍稀书籍的收藏家最近发现了一本用一种陌生的语言写的一本书,这种语言采用和 英语一样的字母。 这本书有简单的索引, 但在索引中的条目的次序不同于根据英语字母表给 出的字典排序的次序。 这位收藏家试图通过索引来确定这个古怪的字母表的字符的次序, (即 对索引条目组成的序列进行整理),但因为任务冗长而乏味,就放弃了。 请编写程序完成这位收藏家的任务,程序输入一个按特定的序列排序的字符串集合,确 定字符的序列是什么。 输入: 输入是由大写字母组成的字符串的有序列表, 每行一个字符串。 每个字符串最多包含 20 个字符。该列表的结束标志是一个单一字符?#?的一行。并不是所有的字母都被用到,但该 列表蕴涵对于被采用的那些字母存在着一个完全的次序。 输出: 输出一行大写字母,字母的排序顺序列按输入数据进行整理所给出。 样例输入 XWY ZX ZXY ZXW YWWX # 注: 试题来源:1990 ACM ICPC World Finals 在线测试:UVA 200,UVA 5139
提示

样例输出 XZYW

输入字符串的有序列表 T[](T 表的长度为 tot) ,按照下述方法将 T 表转化为有向图的 相邻矩阵 v: 每个大写字母为一个节点, 节点序号为字母对应的数值 (大写字母序列[A‥Z]映射为数 值序列[1‥26]) ,T 表中同一位置上不同字母代表的节点间连有向边:

for (int i = 0; i < tot; i++) for (int j = i + 1; j < tot; j++) { len = min(T[i]的串长, T[j]的串长); for (int k=0; k<len; k++) if (T[i]中第 k 个字母 != T[j]中第 k 个字母) { v[T[i]中第 k 个字母对应的节点序号][T[j]中第 k 个字母对应的节点序号]=true; break; } } 计算有向图的拓扑序列, 拓扑序列中节点对应的字母即为字母表中字符的次序。 计算方 法如下 初始化:置图中所有节点未访问标志,统计节点的入度(若 v[i][j]=true ,则 inq[i]=inq[j]=true,++ind[j]。1≤i,j≤26) ;将入度为 0 的节点(inq[i] && ind[i]==0) 送入队列 q。 依次处理队列 q 中的节点:取出队首节点 x,x 的所有相邻节点 i 的入度减 1。若减至 0(v[x][i] && --ind[i] == 0) ,则 i 节点入队。 依此类推,直至队列空为止。此时出队顺序对应的字母即为字母表中字符的次序。

综合题:
【21 Pushing Boxes】

想象您正站在一个二维的迷宫中,迷宫由是正方形的方格组成,这些方格可能被岩石阻 塞, 也可能没有。 您可以向北, 南, 东或西一步移到下一个方格。 这些移动被称为行走 (walk) 。 在一个空方格中放置了一个箱子, 您可以挨着箱子站着, 然后按这个方向推动这个箱子, 这个箱子就可以被移到一个临近的位置。这样的一个移动被称为推(push) 。除了推以外, 箱子不可能用其他的方法被移动, 这就意味着如果您把箱子推到一个角落, 您就永远不能再 把它从角落中推出。 一个空格被标识为目标空格。您的任务就是通过一系列的行走和推把一个箱子推到目标 方格中(如图) 。因为箱子非常重,您希望推的次数最少。您能编写一个程序来给出最佳的 序列吗?



输入: 输入文件包含若干个迷宫的描述, 每个迷宫描述的第一行给出两个整数 r 和 c (都小于等 于 20),表示迷宫的行数和列数。 后面给出 r 行,每行有 c 个字符。每个字符描述迷宫的一个方格。一个塞满岩石的方格 用一个‘#’表示,一个空方格用一个‘.’表示。你开始时站的位置用‘S’表示,箱子开 始的位置用‘B’表示,目标方格用‘T’表示。 输入以两个为 0 的 r 和 c 结束。 输出: 对输入的每个迷宫,第一行输出迷宫的编号,如样例输出。然后,如果不可能把箱子推 到目标方格,输出“Impossible.” ;否则,输出输出推的数目最小化的序列。如果存在多于 一个的这样的序列,选择总的移动(行走和推)最小的序列。如果依然存在多于一个的这样 的序列,那么任何一个序列都是可以接受的。 输出序列是一个字符串,由字符 N, S, E, W, n, s, e 和 w 组成,其中大写字母表示推,小 写字母表示行走,不同的字母代表方向北(north) ,南(south) ,东(east)和西(west) 。 在每个测试用例处理后输出一个空行。 样例输入 17 SB....T 17 SB..#.T 7 11 ########### #T##......# #.#.#..#### #....B....# #.######..# #.....S...# ########### 84 .... .##. .#.. .#.. .#.B .##S .... Maze #4 swwwnnnnnneeesssSSS Maze #3 eennwwWWWWeeeeeesswwwwwwwnNN Maze #2 Impossible. Maze #1 EEEEE 样例输出

###T 00 注: 试题来源:ACM Southwestern European Regional Programming Contest 1997 在线测试:UVA 589,ZOJ 1249,POJ 1475
提示

乍看试题,很容易看出迷宫是一个无权无向图,自然会产生使用 BFS 算法求最短路的 猜想,这个猜想确实看到了求解的大致方向。但是深入分析试题,却可以发现许多难点。例 如,移动过程需分前后两个步骤: ⑴人行走至箱子的相邻位置; ⑵推箱子至目标位置。而在推箱子的过程中,即可以沿一个方向一直推下去,也可以步 行到箱子的另一个相邻位置,换一个方向推。因此需要多次使用 BFS 算法。 ⑴ 输入迷宫信息 通过输入信息计算出相邻矩阵 p,其中 p[i][j]= ?

? true ? false

(i, j )无障碍 (i, j )有障碍

( 0≤i≤

r-1, 0≤j≤c-1), 并记下箱子的起始位置 (xb,yb) 、 目标位置 (xt,yt) 和你的开始位置 (xs,ys) 。 ⑵计算步行情况 移动过程先是从(xs,ys)出发,行走至(xb,yb)的四个相邻格中无障碍格之一,准备推箱 子。 设(xb,yb)有障碍(P[xb][yb]=false) ,从(xs,ys)出发,通过宽度优先搜索(BFS(xs,ys)) 计算出(xs,ys)与每个无障碍格(x,y)(0≤x≤r-1,0≤y≤c-1,p[i][j]=true)的可达状态 reach[x][y]= ?

? true ? false

( xs, ys)可达(x, y) ( xs, ys)不可达(x, y)

若(xs,ys)可达(x,y) ,则将每步的行走方向记入 way[x][y]。显然,way[x][y]的长度即 为(xs,ys)至(x,y)间的最短路径长度。 ⑶通过宽度优先搜索计算推动箱子的最佳方案 设人从(xs,ys)出发沿 i 方向进入(x,y)的移动方向序列为 ans[x][y][i],其最少步数 为 move[x][y][i]。箱子由(x,y)的 i 方向的相邻格推入(x,y)的被推次数为 push[x][y][i]。 为了避免重复进入(xb,yb)的相邻格,设 push[x][y][i]= ?

?0 ??

箱子沿i方向推入( xb, yb) 箱子未沿i方向推入( xb, yb)

一开始(xb,yb)恢复为无障碍状态(P[xb][yb]=true) ,队列撤空。然后枚举开始推的位 置,即(xb,yb)的四个相邻格:

若 i 方向的相邻格在界内且由 (xs,ys) 可达, 则 (xb,yb) 和 i 方向入队, push[xb][yb][i]=0, 将 way[((xb,yb)的 i 方向的相邻格)]记入 ans[xb][yb][i],其长度记入 move[xb][yb][i]。推前 位置确定后,进入宽度优先搜索: 若队列不空,则取出队首的坐标(x,y)和方向 d,直至队列空为止。 有两种推的方案: ? ? 沿 d 方向继续推下去 行走至箱子方向 i(i≠d)的相邻格,从 i 方向推箱子

① 沿 d 方向继续推 若相反的 3-d 方向上的相邻格(x?,y?)在界内且无障碍(如图)

图 若箱子未沿 d 方向推入(x?,y?)((push[x?][y?]][d]==∞)),则(x?,y?)和方向 d 入队; 在箱子沿 d 方向推入( x? , y? )的被推次数 = 沿 d 方向推入( x,y )的被推次数 +1(push[x?]][y?]][d]=push[x][y][d]+1)的情况下,若人从(xs,ys)出发,沿 d 方向进入(x?, y?)的总步数大于沿 d 方向进入(x,y)的总步数+1(move[x?]][y?]][d]>move[x][y][d]+1),则 最 佳 路 径 为 (xs,ys) ? → (x,y) → (x? , y?) ( move[x?]][y?]][d]=move[x][y][d]+1 ); ans[x?]][y?]][d]=ans[x][y][d]+d 方向对应字符); 在箱子沿 d 方向推入( x? , y? )的被推次数 > 沿 d 方向推入( x,y )的被推次数 +1(push[x?]][y?]][d]>push[x][y][d]+1)的情况下,则最佳路径为先沿 d 方向将箱子推入(x,y) , 再沿 d 方向推一次箱子 (push[x?][y?]][d]=push[x][y][d]+1; move[x?]][y?]][d]=move[x][y][d]+1) ; ans[x?]][y?]][d]=ans[x][y][d]+d 方向对应字符); ②另换一个方向推 若沿 d 方向推动箱子,则人必须在箱子位置(x,y)的 d 方向的相邻格(x?,y?) ;若 改为 i 方向推箱子(0≤i≤3,i≠d) ,则必须步行到(x,y)的 i 方向的相邻格(x”,y”)。计 算方法如下: 设(x,y)有障碍(P[x][y]=false) ,从(x?,y?)出发进行 BFS,计算所有可达的格子, 并将到达这些格子的行走方向序列记入 way (BFS(x?, y?)) 。 恢复 (x,y) 的无障碍状态 (P[x][y] = true) ; 搜索除 d 外的每个方向 i(0≤i≤3,i≠d),计算(x,y)的 i 方向上的相邻格(x” ,y”): 若(x” ,y”)为界内的一个无障碍格,且由(x?, y?)可达,则分析

? ?

若箱子未沿 i 方向推入(x,y)(push[x][y][i] ==∞) ,则(x,y)和方向 i 进入队列; 在箱子沿 i 方向推入(x,y)的被推次数=沿 d 方向推入(x,y)的被推次数的情况 下(push[x][y][i]==push[x][y][d]),若人从(xs,ys)出发,进入(x” ,y”)的总步数大 于进入(x? ,y? )的总步数+(x? ,y? )走至(x” ,y”) 的总步数(move[x][y][i]>move[x] [y][d]+way[x”][y”]的长度)则最佳路径为(xs,ys)?→(x’,y’)→(x” ,y”)(move[x] [y][i]=move[x][y][d]+ way[x”][y”]的长度,ans[x][y][i]=ans[x][y][d] + way[x”][y”];

?

在箱子沿 i 方向推入(x,y)的被推次数>沿 d 方向推入(x,y)的被推次数的情况 下(push[x][y][i]>push[x][y][d]),则最佳路径为(xs,ys)?→(x’,y’)→(x” ,y”)(mo ve[x][y][i]=move[x][y][d]+way[x”][y”]的长度, ans[x][y][i]=ans[x][y][d]+way[x”][y”], 箱子推至(x” , y”)的被推次数推至(x’ ,y’ )的被推次数 (push[x][y][i]=push[x][y][d]) ;

⑷输出结果 通过上述 BFS 求出了箱子由 4 个方向推入(xt,yt)的最少被推次数(push[xt][yt][i]) 、 人从(xs,ys)出发沿 4 个方向进入(xt,yt)的最少步数 move[xt][yt][i](0≤i≤3)。最佳方案 中最后的推动方向 d 必须满足如下条件: 箱子沿 d 方向推入(xt,yt) (push[xt][yt][d]≠∞) ,并且满足下述两个条件之一: 箱子被推次数是最少的 push[xt][yt][d]= min { push[ xt, yt ][i ]}
0?i ? 3

若被推次数最少的方案有多个,则 move[xt][yt][d]是最小的 计算方法如下: d=-1; for (int i = 0; i < 4; i++) if (push[XT][YT][i]!=∞ T][d]>move[XT][YT][i]))) d = i; if (d == -1) print("Impossible.\n\n"); else print(ans[xt][yt][d] + "\n\n");
【22 Basic Wall Maze】

//最佳方向初始化 //枚举 4 个方向 &&(d

==-1||push[XT][YT][d]>push[XT][YT][i]||(push[XT][YT][d]==push[XT][YT][i]&&move[XT][Y

//箱子未能推入(xt,yt)

//输出输出推的数目最小化的序列

在这个你要解决问题中,有一个非常简单的迷宫,组成如下: 一个 6*6 的方格组成的正方形。 长度在 1 到 6 的 3 面墙,沿着方格,水平或者垂直放置,以分隔方格。 一个开始标志和一个结束标志。 迷宫形为图:

图 你要寻找从开始位置到结束位置的最短路。仅允许在邻接的方格间移动;所谓邻接就是 指两个方格有一条公共边,并且它们没有被墙隔开。不允许离开正方形。 输入: 输入由若干测试用例组成。每个测试用例由 5 行组成:第一行给出开始位置的列和行的 值;第二行给出结束位置的列和行的值;第 3,4,5 行给出 3 面墙的位置;墙的位置或者是 先给出左边的位置点,再给出右边的位置点(如果是水平的墙) ;或者是先给出上方位置点, 然后再给出下方位置点(如果是垂直墙) 。墙端点的位置是以点与正方形左边的距离后面跟 点与正方形上方位置的距离给出。 输出: 3 面墙可以在方格的某一点上相交,但彼此不交叉,墙的端点在方格上。而且,从开始 标志到结束标志一定会有合法的路。样例输入说明上图给出的迷宫。 最后一个测试数据后跟着一行,包含了两个零。 样例输入 16 26 0010 1516 1535 00 注: 试题来源:Ulm 2006 在线测试:POJ 2935
提示

样例输出 NEEESWW

由于墙是沿方格线的一条线段, 因此不仅要将方格作为节点, 而且也要将方格线也作为 节点,使得迷宫扩展为 12*12 的矩阵。显然,方格线的坐标值为偶数,通道的坐标值为奇数 (如图 11.5-5)

图 墙所在的节点设访问标志 visit,避免出现“翻墙而过”的情况。显然对四周的边墙 visit[0][0] = visit[1][0]?visit[12][0] =true visit[0][0] = visit[0][1]?visit[0][12] =true visit[0][12] = visit[1][12]?visit[12][12] =true visit[12][0] = visit[12][1]?visit[12][12] =true 对由方格(x1,y1)至方格(x2,y2)的垂直墙(x1==x2): visit[2*y1][2*x1]= visit[2*y1+1][ 2*x1]=? visit[2*y2][ 2*x1]=true 对由方格(x1,y1)至方格(x2,y2)的水平墙(y1==y2): visit[2*y1][2*x1]= visit[2*y1][ 2*x1+1]=? visit[2*y1][ 2*x2]=true 入口方格(sx, sy )对应节点的坐标为(sx*2-1,sy=sy*2-1), 出口方格(ex,ey )对应节点的坐标 为(ex*2-1,ey*2-1) 。 有了上述图, 我们便可以使用宽度优先搜索计算起点至各节点的最短路的方向序列, 其 中队列 Q 存储已访问节点的坐标位置(除墙外),prev[][]存储队列中每个节点访问时的移 动方向。 既然有了起点至目标节点的最短路的方向序列, 我们就可以从目标节点出发, 沿 prev[][] 指针的指示追溯目标节点至起始节点的路径: 取出当前节点的方向数 d= prev[x][y]; 若 x 和 y 为奇数,则 d 对应的方向字符填入路径串 path 首部; x-=d 方向的水平增量;y-=d 方向的垂直增量; 依次类推,直至(x,y)为起点坐标为止; 最后输出路径串 path。
【23 Firetruck】

中央城消防部门与交通部门协作,一起维护反映城市街道当前状况的地图。在某一天, 一些街道由于修补或施工而被封闭。 消防队员需要能够选择从消防站到火警地点的不经过被 封闭街道的路线。 中央城被划分为互不重叠的消防区域,每个区域设有一个消防站。当火警发生时,中央 调度向火警地点所在的消防站发出警报, 并向该消防站提供一个从消防站到火警地点的可能 路线的列表。 请您编写一个程序, 中央调度可以使用这个程序产生从区域的消防站到火警地 点的路线。 输入: 城市的每个消防区域有一个独立的地图,每张地图的街区用小于 21 的正整数标识,消 防站总是在编号为 1 的街区。 输入给出若干测试用例, 每个测试用例表示在不同的区域发生 的不同的火警。 测试用例的第一行给出一个整数,表示离火警最近的街区的编号。 后面的若干行每行由空格分开的正整数对组成, 表示未封闭街道连接的相邻的街区。 (例

如,如果在一行给出一对数 4 7,那么在街区 4 和 7 之间的街道未被封闭,且在街区 4 和 7 的路段上没有其他街区) 。 每个测试用例的最后一行由一对 0 组成。 输出: 对于每个测试用例,在输出中用数字来标识(CASE #1,CASE #2,等等) ,在一行中 输出一条路线,按路线中出现的顺序,依次输出街区;输出还要给出从消防站到火警地点的 所有路线的总数,其中只包括那些不经过重复街区的路线(由于显而易见的理由,消防部门 不希望他们的车子兜圈子。 ) 不同的测试用例在不同的行上输出。 在样例输入和样例输出中,给出了两个测试用例。 样例输入 6 12 13 34 35 46 56 23 24 00 4 23 34 51 16 78 89 25 57 31 18 46 69 00 注: 试题来源:1991 ACM World Finals CASE 1: 1 1 1 1 1 1 1 2 2 2 2 3 3 3 3 3 4 4 2 4 5 4 5 3 6 4 6 6 6 6 6 5 6 样例输出

There are 7 routes from the firestation to streetcorner 6. CASE 2: 1 1 1 1 1 1 1 1 3 3 5 5 6 6 8 8 2 4 2 7 4 9 7 9 8 5 6 7 2 4 5 3 2 4 3 4 3 8 4 9 6 4 5 7 8 9 6 4

There are 8 routes from the firestation to streetcorner 4.

在线测试:UVA 208,UVA 5147
提示

我们将街区作为节点,未封闭街道连接的相邻街区间连边,构造一个无向图。路线的起 点为节点 1(即消防站所在的街区 1) ,终点为离火警最近的街区编号 en。试题要求计算这 样的路线有多少条以及所有的路线方案。 显然可以用回溯法计算所有可能的路线。但需要注意的是,在扩展路线时,新节点 y 不仅要满足与路线尾节点 x 相邻和未访问的约束条件,还要满足 y 是否与终点 en 连通的约 束条件,否则消防车无法途径 y 到达火警地点。为了提高搜索效率,我们可以预先通过计算 传递闭包的 Warshall 算法,计算出节点 2‥节点 n 中每个节点与节点 en 的连通性。设传递 闭包为 p,其中 p[i][j]为节点 i 与节点 j 间连通的标志 P 初始化为相邻矩阵; for (int i=1;i<=n;i++) p[i][i]=1; for (int k=2;k<=n;k++) for (int i=2;i<=n;i++) 径 k 到达 j for (int i=2;i<=n;i++) if (!p[i][en]) cut[i]=1; //记录节点 i 与终点 en 不连通 这样,我们就可以将 cut[y]作为关键的剪枝条件了,即新节点 y 必须同时满足条件: (相 邻于路线尾节点 x)&&(y 未访问)&&(!cut[y]),方可添入路线中。
【24 Dungeon Master】

//设定对角线元素 //枚举路径的中间节点 k //枚举路径的起点 i

if (p[i][k]) for (int j=2;j<=n;j++) p[i][j]|=p[k][j]; //枚举路径的终点 j,确定 i 可否途

你正身陷一个 3 维的地牢中,需要找到最快的路径离开。地牢由立方体单元组成,这些 单元或者是岩石,或者不是岩石。你可以用一分钟的时间向东,向西,向南,向北,向上, 或者向下,走到下一个单元中。你不能走对角线,迷宫的周围是坚硬的岩石。 可能逃离地牢吗?如果可能,要多长时间? 输入: 输入由许多地牢组成。每个地牢的描述的第一行是 3 个整数 L,R 和 C(大小限制在 30 以内) 。 L 表示地牢的层数。 R 和 C 表示地牢的行和列。 后面跟着 L 块,每块包含 R 行,每行包含 C 个字符,每个字符表示地牢的一个单元。一 个单元如果由岩石构成,用‘#’表示;空的单元用‘.’表示;你所在的起始位置用‘S’ 表示;出口用‘E’表示。每层地牢后跟一空行。输入以为 L,R 和 C 赋 0 结束。 输出: 每个迷宫产生一行输出,如果可以到达出口,输出形式为 Escaped in x minute(s). 其中 x 是逃离的最短时间。

如果不可能逃离,输出 Trapped! 样例输入 345 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 133 S## #E# ### 000 注: 试题来源:Ulm Local 1997 在线测试:POJ 2251,ZOJ 1940
提示

样例输出 Escaped in 11 minute(s). Trapped!

3 维地牢是一个长方体,每个单元在向东,向西,向南,向北,向上,向下 6 个方向上 存在可能的相邻单元, 其中某些单元为障碍物。 我们将每个单元作为节点, 相邻单元间连边, 构建一个无向图。试题要求从起点( sx,sy,sz )出发,判断可否沿无障碍单元行走至出口 (ex,ey,ez) 。如果可以,则计算其中的最短路。显然可采用回溯法计算,设 d[x][y][z]为起点单元至(x,y,z)单元的最短路长。初始时,每个单元的 d 值设一个较大 值 100; 递归函数为 dfs( x, y, z,k),当前单元为(x,y,z) ,准备扩展最短路的第 k 个节点。计算过 程如下:

dfs( x, y, z,k) { d[x][y][z]=k; if(x,y,z)为终点(ex,ey,ez)) return; if ( x ? ex ? y ? ey ? z ? ez ≥d[ex][ey][ez]) return; //重要剪枝:若当前点与终点的曼 哈顿距离过长则跳出 分析(x,y,z)的六个方向上的相邻格,分情形递归: 若当前方向的相邻格(x?,y?,z?)满足如下条件 ((x?,y?,z?)在界内)&&(k+1<d[x?][y?][z?]) &&((x?,y?,z?)无障碍) 则递归 dfs(x?,y?,z?,k+1); } 显然,通过递归调用 dfs(sx,sy,sz,0),便可计算出起点(sx,sy,sz)至每个节点的最短路长。 若 d[ex][ey][ez]≥1600000000,则表明过多次搜索亦未找到出口,应宣布不可能逃离;否则 d[ex][ey][ez]即为逃离的最短时间。

【25 A Knight's Journey】

骑士对于一再看黑白方块非常厌烦,决定周游世界。只要骑士移动,它在一个方向上移 动两个方块,并在垂直的方向上移动一个方块。骑士的世界就是他所生活的棋盘。我们的骑 士生活的棋盘小于 8 * 8 ,但仍然是一个矩形(如图) 。你能帮助这个冒险的骑士制订旅行 计划吗?

图 问题: 寻找一条路径,使得骑士能够访问每个方块一次。骑士可以在棋盘的任何一个方块开始 和结束。 输入: 输入的第一行是一个正整数 n,后面的行包含 n 组测试用例,每个测试用例包含两个正 整数 p 和 q, 使得 1≤p*q≤26, 这表示一个 p*q 棋盘, 其中 p 表示有多少个方块的编号 1, . . . , p 存在,q 表示有多少个方块的字母编号存在,前 q 个拉丁字母是 A, . . . 。 输出: 对于每个测试用例,输出第一行是“Scenario #i:” ,其中 i 是测试用例编号,从 1 开始

编号。然后输出一行给出移动骑士访问棋盘所有方块的路径。这条路径由访问的方块组成。 每个方块由大写字母跟一个数字构成。 如果没有这样的路径存在,就要在这一行输出 impossible。 样例输入 3 11 23 43 Scenario #2: impossible Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4 注: 试题来源:TUD Programming Contest 2005, Darmstadt, Germany 在线测试:POJ 2488
提示

样例输出 Scenario #1: A1

显然,本题可采用回溯法计算遍访所有方格的访问路径。设 v[x][y]为到达(x,y)的步数; 递归函数为 dfs(x,y,step),即路径上第 step 步走入(x,y) ,从这一状态出发,计算遍 访所有方格的可行性。计算过程如下: ? ? ? Step 置入 v[x][y]; 若遍访了所有方格(step==n*m) ,则设成功标志,输出访问路径后退出程序; 否则枚举(x,y)的 8 个方向的相邻格(x?,y?) :若(x?,y?)在界内且未访问 (v[x?][y?]==0) ,则递归 dfs(x?,y?,step+1); 在主程序中,枚举所有可能的出发位置(i,j)(1≤i≤p,1≤j≤q),一旦调用了 dfs(i, j,1)后发现从(i,j)出发可遍访所有方格,则在输出访问路径后退出程序;若调用了 p*q 次 dfs(i,j,1)后仍未找到访问路径,则输出失败信息。 需要注意的是,为了保证输出字典序最小的访问路径,8 个方向的增量数组 dx[]和垂直 增量数组按照 dy[]递增的顺序排列,即 int dx[]={-1,1,-2,2,-2,2,-1,1}; int dy[]={-2,-2,-1,-1,1,1,2,2};

【26 Children of the Candy Corn】

玉米田迷宫是一种流行的万圣节快乐活动。访问者在进入入口之后,要通过面对僵尸、 挥舞着电锯精神病患者、嬉皮士、以及其他恐怖手段的迷宫,最后找到出口。 有一种保证游客最终找到出口的流行的迷宫行走策略,只要选择是沿着左面的墙或者右

面的墙,并一直走下去。当然,不能保证向左或者向右哪一个策略会更好,而且所走的路径 很少是最有效的。 (如果出口不是在边缘上,这一策略就不起作用,但这一类的迷宫不是本 题所论述的。 ) 作为一个玉米田迷宫的所有者,你想有一个计算机程序确定除了最短路径外的向左和向 右路径,使得你可以计算出哪一种布局有最好的惊吓访问者的机会。 输入: 问题输入的第一行给出整数 n,表示迷宫的数量。每个迷宫的第一行给出宽度 w 和高度 h (3 ≤ w, h ≤ 40), 后面的 h 行, 每行有 w 个字符, 每个表示迷宫的布局。 墙用哈希标记( ‘#’ ) 表示,空区域用(‘.’)表示,开始用‘S’表示,出口用‘E’表示。 在每个迷宫中仅有一个‘S’和一个‘E’ ,它们位于迷宫的边墙,不在墙角。迷宫的四 面是墙(‘#’),还有‘S’和‘E’ 。 ‘S’和‘E’之间至少有一个(‘#’)将他们分开。 从起点到终点是可达的。 输出: 对于输入的每个迷宫,输出一行,按序给出沿靠左行走,靠右行走,最短路径行走一个 人经过的方块(不一定是唯一的)的数量(包括‘S’和‘E’ ) ,用空格分开。从一个方块 到另一个方块的移动仅允许水平和垂直方向,不允许对角线方向移动。 样例输入 2 88 ######## #......# #.####.# #.####.# #.####.# #.####.# #...#..# #S#E#### 95 ######### #.#.#.#.# S.......E #.#.#.#.# ######### 注: 试题来源:ACM South Central USA 2006 在线测试:POJ 3083,ZOJ 2787,UVA 3631
提示

样例输出 37 5 5 17 17 9

试题的难度是怎样计算游客沿左面墙或者右面墙一直走下去的路线。设方向 1‥方向 4 (如图)

图 方向 t 逆时针转 90 后的方向为 t1=(t+3)%4,顺时针转 90 后的方向为 t2=(t+1)%4。 我们设计一个递归函数 dfs_left(x, y, t),从游客沿 t 方向走入(x,y)的状态出发,计算 沿左面墙走至出口的步数 step: dfs_left(x, y, t){ 若(x,y)为边墙(x,y 在界外)或内墙((x,y)为?#?),则返回 2; 步数 step +1; 若(x,y)为出口,则返回 1; 成功标志 flag 初始化为 0; 计算 t 逆时针转 90 后的方向 tt=(t+3)%4; for (int i=0;i<3;i++){ //tt 顺时针转 90 4 次
。 。 。 。

计算 dfs_left(x?, y?, tt)的返回值 r((x?, y?)为(x, y)的 tt 方向的相邻格); 若找到出口 (r==1),则设成功标志(flag=1)并退出 for 循环; 否则,若找不到出口(r==0),则步数 step +1;tt 再顺时针转 90 (tt=(tt+1)%4) } 返回成功标志 flag; } 同样, 可以采用类似方法计算游客沿右面墙走至出口的步数 step (递归函数 dfs_right (x, y, t)),只不过是将 t 逆时针旋转 90 改为顺时针旋转 90 ,将 tt 顺时针旋转 90 改为逆时针 旋转 90 。 至于计算游客行走的最短路则比较简单。设 d[x][y]为游客从入口走至(x,y)的最短路长,简称(x,y)的距离值; 递归函数 dfs( x, y, k),从游客第 k 步走至(x,y)的状态出发,计算最短路长 step: dfs( x, y, k){ 若(x,y) 为边墙或内墙,或者其距离值不大于 k(k≥d[x][y]),则退出程序; 设定(x,y)的距离值 d[x][y] =k; 若(x,y)为出口,则设定最短路长 step 为 k 并退出程序 枚举(x,y)四个方向的相邻格(x?,y?),递归 dfs(x?,y?,k+1) }
。 。 。 。 。

在主程序中,我们对入口(xs,ys)的四个相邻格中非边墙或内墙的方块分别执行一次 dfs_left(xs,ys, t),即可统计出人靠左行走经过的方块数;用同样的方法亦可统计出人靠右行 走经过的方块数;至于计算人走最短路经过的方块数,只要执行一次 dfs (xs,ys,1) 即可。

【27 Curling 2.0】

在行星 MM-21,在他们今年的奥运会之后,冰壶(冰上溜石游戏)变得非常流行,但 他们的规则和我们的有些不同, 这一游戏是在一个用正方形方格划分的冰棋盘上进行。 他们 只用一块石头。这一游戏的目标是将石头从开始位置用最少的移动次数移到目标位置。 如图给出了一个游戏的实例。一些正方形方格被阻塞了,存在两个特别的方格,即开始 位置和目标位置,这两个方格不会被阻塞。 (这两个方格不会在同一位置)一旦石头开始移 动,它就会一直向前,直到它撞上一块阻塞物。为了使石头移到目标位置,在石头停止在阻 塞物前的时候,你要再次推动它。

实例(S: 开始位置, G: 目标位置) 图 石头的移动遵循以下规则: 在开始的时候,石头在开始位置。 石头的移动受限于 X 轴,Y 轴方向,禁止沿对角线移动。 当石头停滞的时候,你可以推动它让它移动。只要它没有没阻塞,你可以向任何方向推 动它(如图(a) ) 。 一旦推动了石头,石头就向前走同样的方向,直到出现下列情况之一: 石头遇上了阻塞(如图(b) , (c) ) 。 石头停在阻塞方块前。 阻塞物消失。 石头走出了棋盘。 游戏结束,失败。 石头到达到了目标方格。 石头停止那里,游戏成功结束。 在游戏中,你不能推动石头 10 倍次以上。如果在 10 次以内石头没有到达目标位置,游 戏结束,失败。

石头移动 图 根据这一规则, 我们想知道是否在开始位置的石头可以到达到目标位置, 如果可以到达, 就要给出最低的推动次数。 实例如图 1 所示,将石头从开始位置移动到目标位置要推动石头 4 次,石头运动的路线 如图(a)所示。请注意当石头到达目标位置的时候,棋盘图结构变化如图(b)所示。

石头运动的路线 输入:

棋盘图结构变化

输入是一个数据集合的序列,在输入结束是包含用空格分开的两个零的一行。数据集合 的数目从未超过 100。 每个数据集合的格式如下: 冰棋盘的宽度和高度 h 冰棋盘的第 1 行 ... 冰棋盘的第 h 行 冰棋盘的宽度和高度满足: 2≤w≤20,1≤ ?≤20。 每行包含 w 个用空格分开的十进制数。这一数字描述相应的方块的状态。 0 空方块 1 阻塞 2 开始位置 3 目标位置 图 1 的数据集合如下: 66 100210 110000 000003

000000 100001 011111 输出: 对于每个数据集合,打印一行,给出一个十进制整数,表示从开始位置到目标位置的路 线的移动的最少次数。如果没有这样的路线,输出-1。除了这个数字,输出行没有其他的任 何字符。 样例输入 21 32 66 100210 110000 000003 000000 100001 011111 61 112113 61 102113 12 1 201111111113 13 1 201111111111 3 00 注: 试题来源:Japan 2006 Domestic 在线测试:POJ 3009
提示

样例输出 1 4 -1 4 10 -1

设 ans 为从开始位置到目标位置的最少移动次数, 初始值为 11。 我们通过递归函数 dfs( x, y, k)计算 ans,其中参数的意义是第 k 步行至(x,y) 。计算过程如下: dfs( x, y, k){ 若移动次数不小于上限或者最少移动次数(k>=10|| k>=ans),则退出程序 枚举(x,y)的 4 个方向上的相邻格(x?,y?):

{ 若 (x?, y?) 为非同行或非同列上的阻塞, 则去除; 从 (x?, y?) 递归下去 (dfs(x?,y?,k+1)) ; 恢复递归前相邻格的阻塞状态; 否则若(x?,y?)为目标位置,则更新答案(ans=min{ans,k+1})并退出程序 } } 我们从开始位置(xs,ys)出发,递归调用 dfs(xs,ys ,0)。若得出的 ans 仍为初始值 11,则说明无解;否则 ans 即为最少移动次数。

【28 Shredding Company】

您为碎纸机公司负责开发一种新的碎纸机。一台“一般”的碎纸机仅仅将纸张切成小碎 片,使得其内容不可读,而这种新的碎纸机需要有以下不同寻常的基本特性。 1, 你的碎纸机要以一个目标数作为输入,并在要粉碎的那一张纸上写有一个数字。 2, 你的碎纸机将纸张粉碎(或切割)成碎片,每张碎片上都有这个数字的一位或若干 位。 3, 每张碎片上数字的总和要尽可能地接近目标数,但不能超过目标数。 例如,假设目标数为 50,而纸张上数字为 12346。碎纸机将纸张切碎成四张,第一张碎 片上是 1,第二张上是 2,第三张上是 34,第四张是 6。它们的总和是 43(= 1+ 2+ 34+ 6) , 是所有可能的组合中最接近目标数 50 但不超过 50(如图) 。例如,组合 1,23,4 和 6 则不 成立,因为这个组合的总和是 34(=1 +23 +4+ 6) ,小于上一个组合的总和 43。组合 12,34 和 6 也不成立,因为 52 (= 12 + 34 + 6)大于目标数 50。

图 此外,还有 3 条特定的规则: 1. 如果目标数和纸张上的数字相同,则这张纸就不要粉碎。例如,如果目标数是 100,而 纸张上的数字也是 100,则纸张不会被粉碎。 2. 如果任何组合的总和不可能小于或等于目标数, 则输出 “error” 。 例如, 如果目标数是 1, 而在纸张上的数字是 123,那么不可能存在可以成立的组合,因为具有最小和的组合是 1,2 和 3,它们的和是 6,大于目标数,所以要输出“error” 。 3. 如果有多于一个总和最接近但没有超过目标数的组合,输出“rejected” 。例如,如果目 标数是 15,在纸张上的数字是 111,则有两个最高是 12 的组合:(a) 1 和 11,(b)11 和 1;

所以输出“rejected” 。为了开发这样的碎纸机,请您编写一个小程序来模拟上述的特性 和规则。给出两个数,第一个数是目标数,第二个数是写在要被粉碎的纸张上的数,程 序要计算出碎纸机如何“切割”第二个数。 输入: 输入由若干测试用例组成,每个测试用例一行,形式如下: t1 num1 t2 num2 ... tn numn 00 每个测试用例由两个正整数组成,用一个空格分开: (1)第一个整数(上面标识为 ti) 是目标数; (2)第二个整数(上面标识为 numi)是要粉碎的纸张上的数字。 两个数不能将 0 作为第一位,例如 123 可以,但 0123 则不可以。可以设定两个整数长 度最多 6 位。以一行中给出两个 0 作为输入结束。 输出: 对于输入中的每个测试用例,相应输出为下述 3 种类型之一: ? ? ? sum part1 part2 ... rejected error 在第一种类型中,partj 和 sum 的含义如下: 1. 每个 partj 是一个在一张碎纸片上的一个数。 partj 的次序相应于在纸张上原来的数字的次 序。 2. sum 是纸张被粉碎后数字和,即,sum=part1+part2+... 。 每个数字用一个空格分开。 如果不可能产生组合,输出“error” 。如果存在一个以上的组合,输出“rejected” 。 在每行的开始和结束,没有其他的字符,包括空格。 样例输入 50 12346 376 144139 927438 927438 18 3312 9 3142 25 1299 111 33333 103 862150 6 1104 00 样例输出 43 1 2 34 6 283 144 139 927438 927438 18 3 3 12 error 21 1 2 9 9 rejected 103 86 2 15 0 rejected

注: 试题来源:ACM Japan 2002 Kanazawa 在线测试:POJ 1416,ZOJ 1694,UVA 2570
提示

设目标数为 limit;纸张上的数字为 n;目前所有碎纸片上的最佳数字和为 Max。试题要 求将 n 按位的顺序拆分成若干个数,使其数和 Max 为不超过 limit 的最大数,并判断出数和 为 Max 的拆分方案数 r 是 1 还是大于 1,或者是根本无法拆分(r=0)。 那么,怎样求最佳数字和 Max 呢? 我们从 n 的最低位开始由右而左拆分,若当前拆分出 i 位数,则 n%10i 为当前碎纸片上 的数字,剩余数字 ?

? n ? 待拆分。拆分有两种情况: i ?10 ? ?

不断开情况:当前碎纸片上的数字需继续向左扩展 断开情况:拆分出当前碎纸片上的数字 显然,我们可以采用回溯法分头递归这两种情况。设递归函数 dfs(n,sum, now, k, p),其 中 n 为待拆分的数字,sum 为已经拆分出的数和,当前待拆分出的一个数字为 now,准备填 入第 k 张碎纸片,p 为下一个十进制位的权。 dfs(n,sum,now, k, p){ if (n==0){//若拆分完毕,则最后拆分出的数字 now 填入第 k 张纸条,更新答案并回溯 t[k]=now; if (sum+now >limit) return; if (sum+now==Max) r++; 组合个数+1` else if (sum+now >Max){ Max=sum+ now; r=1; ansk=k; return; } int m=n%10; dfs(n/10,sum,now+p*m,k,p*10); t[k]=now; dfs(n/10,sum+now,m,k+1,10); } //取待拆分数的个位数 //递归不断开的情况 //now 填入第 k 张碎纸片 //递归断开后的情况 //数和为 Max 的组合数为 1 //已填数的碎纸片数和各张碎纸片数的填数记入最佳方案 //回溯 //若拆分出的数和更佳,则调整为 max //若拆分出的数和大于目标数。则退出 //若拆分出的数和相同于 Max, 则数和为 Max 的

for (int i=1;i<=k;i++) ans[i]=t[i];

我 们 在 主 程 序 中 初 始 化 最 佳 数 字 和 与 组 合 数 ( Max=0; r=0 ) , 然 后 递 归 调 用 dfs(n/10,0,n%10,1,10)。若 r>1,则说明拆分出数和为 Max 不止 1 个;若 r=1,则 max 为最佳 数字和,拆分出的数字为 ans[ansk]‥ans[1]。

【29 Be Wary of Roses】

您为您获奖的玫瑰园非常骄傲。然而,一些嫉妒的同行园丁要不择手段地对付您。他们 绑架了您,将您蒙上眼睛,并给您戴上手铐,然后将您丢在您所珍爱的玫瑰花丛中。您要逃 出去,但您不能确保您可以不践踏珍贵的花朵。 幸运的是,您将您花园的布局记在脑中。这是一个 N× N 的平方图(N 为奇数) ,在其 中的一些方格中种有玫瑰。您正好是站在平方图正中心的大理石基座上。不幸的是,你已经 完全迷失了方向,而且不知道您所面对的方向。大理石的基座可以让您调整您的方向,使得 您朝向北,东,南,或西,但你没有办法知道您当前朝哪个方向。 无论您最初面朝哪个方向, 您必须想出一个践踏尽可能少的玫瑰的逃离路径。 您的路径 必须从中心开始,只能水平和垂直移动,以离开方格作为结束。 输入: 每个测试用例首先在一行中给出平方图的大小 N ( 1≤N≤21);然后 N 行,每行 N 个字 符,用于描述花园。`.' 表示方格中没有玫瑰,`R'表示方格中有玫瑰,而`P'代表在中心的大 理石基座。 输入以 N = 0 为结束标志,程序不必进行处理。 输出: 对于每个测试用例,输出一行,给出在您逃离的时候要踩在玫瑰上的最少的次数。 样例输入 5 .RRR. R.R.R R.P.R R.R.R .RRR. 0 注: 试题来源: 在线测试:UVA 10798
提示

样例输出 At most 2 rose(s) trampled.

0、 90 、 180 、 270 , 由于大理石的基座调整有四个方向: 因此设 a[k][i][j]为地图旋转 (k-1)
* 90 时(i,j)的状态,若(i,j)方格中有玫瑰,则 a[k][i][j]=1;否则 a[k][i][j]=0。










假设被踩玫瑰数的上限为 limit,怎样判断你能否在踩到的玫瑰数不超过 limit 的情况下 成功逃离玫瑰园呢?设 f[x][y][r1][r2][r3][r4]为行至(x,y)时,4 个方向上踩到的玫瑰数分别为 r1、r2、r3、r4 的访问标志; v[x][y]为已经过(x,y)的标志; flag 为成功逃离的标志; 我们通过递归过程 dfs(x,y,r1,r2,r3, r4)计算 flag,其中(x,y)为目前行至的方格位置,4 个方向上踩到的玫瑰数分别为 r1、r2、r3、r4,显然经过(x,y)后,4 个方向上踩到的玫瑰 数增加至 r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]。dfs(x,y,r1,r2,r3, r4)的计 算过程如下: dfs(x,y,r1,r2,r3, r4) { if (flag) return; if (v[x][y]) return; if (max(r1,r2,r3,r4)>limit) return; if (out(x,y)) { flag=1; return; } if (f[x][y][r1][r2][r3][r4]) return; //若行至(x,y)、4 个方向上踩到的玫瑰数为 r1、r2、 r3、r4 的状态已访问,则回溯 f[x][y][r1][r2][r3][r4]=1; r3、r4 的状态已访问 v[x][y]=1; 邻方向 dfs(x-1,y,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); dfs(x,y+1,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); dfs(x,y-1,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]); v[x][y]=0; } 在 dfs(x,y,r1,r2,r3, r4)的基础上,便可以计算逃离时踩到的最少玫瑰数: 计算出发位置(ox,oy)(ox=n/2+1,oy=n/2+1); 成功标 flag 志初始化为 0; 被踩玫瑰数的上限/limit 初始化为-1; while (!flag){ //若未成功逃离,则被踩玫瑰数的上限+1 limit++; f 和 v 清零(memset(f,0,sizeof(f)); memset(v,0,sizeof(v))); // //撤去(x,y)的经过标志 //设(x,y)已经过标志 dfs(x+1,y,r1+a[1][x][y],r2+a[2][x][y],r3+a[3][x][y],r4+a[4][x][y]);//递归(x,y)的四个相 //设行至(x,y)、4 个方向上踩到的玫瑰数为 r1、r2、 //成功退出 //若先前经过(x,y),则回溯 //若任一方向上踩到的玫瑰数超过上限,则回溯 //若逃离玫瑰园,则成功退出

dfs(ox,oy,0,0,0,0); 情况下逃离玫瑰园的可能性 }

//从图正中心出发, 递归计算在被踩玫瑰数不超过上限的

输出逃离时踩到的最少玫瑰数 limit;

【30 Monitoring the Amazon】

一个由独立的、用电池供电的、用于数据采集的站所组成的网络已经建成,用于监测 Amazon 地区的气候。 发布指令的站将启动指令传输到测控站, 使得它们改变其当前的参数。 为了避免电池过载,每个站(包括发布指令的站)只能传送指令给另外两个站。通常是选择 与这个站最近的两个站。 如果有多个站符合条件, 则首先选择地图上的最西边 (左边) 的站, 其次选择的最南端(在地图的最下方)的站。 你受 Amazon 州政府委托,编写一个程序,给出每个站的位置,确定是否信息可以传达 到所有的站。 输入: 输入给出一个整数 N,后面给出 N 对整数 Xi, Yi,表示每个站的定位坐标。第一对坐标 给出发布指令的站的位置,而剩下的 N-1 对是其他站的坐标。给出下述限制:-20≤Xi, Yi≤ 20, 以及 1≤N≤1000。输入以 N= 0 结束。 输出: 对每个给出的表达式,输出一行,指出是否所有的站都可以到达(见样例输出的格式) 。 样例输入 4 1 0 0 1 -1 0 0 -1 8 1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1 6 0 3 0 4 1 3 -1 3 -1 -4 -2 -5 0 注: 试题来源:2004 Federal University of Rio Grande do Norte Classifying Contest - Round 1 在线测试:UVA 10687
提示

样例输出 All stations are reachable. All stations are reachable. There are stations that are unreachable.

设测控站为节点。根据题意(选择与这个站最近的两个站。如果有多个站符合条件,则 首先选择地图上的最西边(左边)的站,其次选择的最南端(在地图的最下方)的站) ,每 个节点 k(0≤k≤n-1)的出度为 2(若仅有一个测控站,则出度为 1) 。按照下述方法计算 节点 k 的出边: 按照与节点 k 的欧式距离为第 1 关键字、 x 坐标为第 2 关键字、 y 坐标为第 3 关键字的

递增顺序排列坐标序列 w,节点 k 分别向节点 w[1]和节点 w[2]连边(若仅有一个测控站, 则连边(k,w[1])) 。 构造出有向图后,使用回溯法计算节点 1(发布指令的站)可达的节点集合。若该集合 囊括了除节点 1 外的所有节点, 则表明信息可以传达到所有的站; 否则表明存在未能接受信 息的站。

【31 Graph Connectivity】

考虑一个无向图 G = < V, E >。初始时图中无边。请写一程序判断两个不同节点间是否 连通。程序还要有插入和删除边的功能。 输入: 输入的第一行给出整数 N (2≤N≤1000) ,表示图 G 中的节点数。第二行给出指令数 Q (1≤Q≤20000)。后面的 Q 行每行给出一条指令,有三类指令: I u v: 插入边 (u, v),并保证在执行这一指令时,在节点 u 和 v 之间没有边。 D u v: 删除已有的边 (u, v),并保证在执行这一指令时,在节点 u 和 v 之间存在边。 Q u v: 查询指令,在节点 u 和 v 之间是否连通。 节点的编号从 1 到 N。 输出: 对每条查询指令输出一行。如果两个节点是连通的,输出“Y” ;否则输出“N” 。 样例输入 3 7 Q12 I12 I23 Q13 D12 Q13 Q11 注: 试题来源:POJ Monthly--2006.06.25, Zheng Zhao 在线测试:POJ 2838
提示

样例输出 N Y N Y

由于无向图是动态生成的, 因此该图的存储结构采用邻接表为宜。 我们按照下述方法依 次处理每条命令: 若为插边指令 I x y:y 插入 x 的邻接表,x 的邻接表长+1;x 插入 y 的邻接表,y 的邻 接表长+1;

若为删边指令 D x y:在 x 的邻接表中搜索 y,用表尾节点覆盖该位置,x 的邻接表长度 -1;在 y 的邻接表中搜索 x,用表尾节点覆盖该位置,y 的邻接表长度-1; 若为查询指令 Q x y:若 x==y,则 x 和 y 之间连通;否则从 x 出发,通过 BFS 搜索计算 x 的所有可达节点。若 y 为可达节点,则节点 x 和 y 之间连通;否则不连通。

【32 The Net】

现在考虑 Internet 上一个感兴趣的问题:快速的信息传送已经成为必须。信息传送工作 由位于网络节点上的路由器实现。 每个路由器有它自己的一个路由器列表, 给出它可以直接 到达的路由器(也被称为“传输表” ) 。很明显,信息传送要求经过的路由器最少(也被称为 “跳数” ) 。 对于给出的网络,要求程序发现从信息源头到目标节点的最佳路线(最少跳数) 。 输入: 第一行给出网络中路由器的个数 (n) 。 后面的 n 行给出网络的描述。 每行给出路由器 ID, 然后是一个连字符以及用逗号分开的、可以直接到达的路由器的 ID 列表,这一列表按升序 排列。下一行给出信息传送要走的路线数目(m) ,后面连续的 m 行给出用一个空格分开的 路线的起始路由器和终点路由器。输入数据包含了多个网络的描述。 输出: 对输入中给出的每个网络,先输出一行 5 个连字符;然后对每条路线,输出信息从起始 路由器传送到目的路由器要经过的路由器列表。 如果不可能进行信息传送 (起始路由器和目 的路由器不连通) ,输出字符串“connection impossible” 。如果存在多条有相同“跳数”的路 线,输出低 ID 的路线(由路由器 1 到 2 的路线是 1 3 2 和 1 4 2,则输出 1 3 2)。 数据范围设定为:网络中路由器的数目不超过 300,并且至少有 2 个路由器。每个路由 器最多和 50 个路由器直接相连。 样例输入 6 1-2,3,4 2-1,3 3-1,2,5,6 4-1,5 5-3,4,6 6-3,5 6 16 15 24 25 ----136 135 214 235 36 21 ----9 7 3 4 8 10 connection impossible 962 样例输出

36 21 10 1-2 23-4 4-8 5-1 6-2 7-3,9 8-10 9-5,6,7 10-8 3 9 10 59 92 注: 试题来源: 在线测试:UVA 627
提示

将路由器看作节点,则试题给出的路由器列表实际上是图的邻接表。我们可以使用 flyed 算法计算任意节点对之间的最短路矩阵 dist[][] (最短路矩阵中元素的初始值为∞) 。 计算“跳线”实际上就是计算指定节点对 x 和 y 间的一条最短路。有了最短路矩阵 dist[][],计算便变得十分容易: 若 dist[x][y]为初始值∞, 则 x 路由器和 y 由器不连通; 否则 x 路由器和 y 由器连通。 我们可按照下述方法计算和输出低 ID 的信息传送路线。 输出路线上的首节点 x; while (dist[x][y] != 1) for (int k=1; k≤N; k++) //若 y 非最短路的尾节点 //按照 ID 递增的顺序搜索最短路上 x 的相邻节点 k

if (dist[x][k]==1 && dist[x][k]+dist[k][y]== dist[x][y]) { 输出节点 k; x=k; break; } 输出最短路上的尾节点 y; //继续找最短路上 k 的相邻节点

【33 The Warehouse】

特工 007 找到了疯狂的科学家 Dr. Matroid 的秘密武器仓库。仓库里放满了大箱子(可能 致命武器就在箱子内) 。在对仓库进行检查的时候,007 意外地触发了警报系统。仓库有一 种针对入侵者的非常有效的保护: 如果触发警报, 那么地板上就充满了致命的酸。 因此, 007 可以逃脱的唯一的办法是爬到箱子上面, 并达到在顶部的出口。 出口是一个在天花板上的洞, 如果 007 可以爬上通过这个洞,他便可以使用停在屋顶上的直升机逃脱。在洞的下方,有一 个梯子和一个箱子,因此,目标就是到达这个箱子。 仓库的地板可视为 n?n 单元格的一个网格,每个单元格的大小为 1 米×1 米。每个单元 格或者是完全被一个箱子占用或没有放东西。 每个箱子是长方体: 占据地面的大小为 1 米× 1 米,高度可以是 2 米,3 米,或者 4 米。在图(a)中,可以看到一个仓库的实例,数字表 示箱子的高度,E 表示出口,圆表示特工 007 目前在该箱子的顶部。

图 007 可以做两件事: 如果他正站在一个箱子的顶部,并在相邻的单元格中还有另外一个箱子,那么他可以移 动到另一个箱子的顶部。例如,在图(a)所示的情况中,他可以向北部或向东移动,但不 能向西或向南移动。请注意,只允许这四个方向的移动,对角线方向移动是不允许的。两个 盒子之间的高度差并不重要。 007 能够做的第二件事情是他能够向 4 个方向推倒他所站的箱子。用一个例子来表示推 倒箱子的情况: 007 的情况如图(b)所示,他可以向西推翻箱子(如图(c)所示) ,或向 北推倒箱子(如图(d)所示) 。如果箱子的高度为 H,向北(或向西,向南,等等)推倒箱 子,则箱子在向北(或者向西,向南,等等)方向上占据连续的 H 个单元格。箱子原来占 据的位置将被空置(但还可以推翻另外的箱子,重新占据这个位置) 。如果在箱子倒下的位 置上没有被其他箱子占据,箱子才可以朝这个方向被推倒,例如,在(a)中,007 所站的 箱子不能朝任何一个方向被推倒。 推倒了一个箱子后, 007 可以朝推倒箱子的方向上跳一步跳到被推倒的箱子上 (见图 (c) (d)项) 。如果一个箱子被推倒了,那么它不可能被再一次推倒。在出口的下方有一个箱子 (在图中标记了 E 的单元格),因此不可能推翻一个箱子压在这个单元格上。警报系统不久还 将放出突变体的毒蝙蝠, 因此 007 必须尽快离开仓库。 请你写一个确定到达出口的最少步数 的程序,以帮助 007。跳上邻近的箱子,推翻一个箱子都被计算为一步。 输入: 输入包含若干个测试用例。 每个测试用例的第一行给出 3 个整数: 仓库的大小 1≤n≤8; 两个整数 i , j ,给出了特工 007 的开始位置,这些整数在 1 到 n 之间,行数由 i 给出,列数 由 j 给出。后面的 n 行描述仓库,每行给出一个 n 个字符组成的字符串。每个字符对应仓库

的一个单元格,如果字符是`.‘,则单元格没有被占据,字符‘2’ , ‘3’和‘4’分别对应 于高度为 2, 3 和 4 的箱子。字符`E‘表示出口的位置。 输入结束用 n = i = j = 0。 输出: 对每个测试用例,输出一行,给出一个整数:到达出口的最少的步数。如果不可能到达 出口,则输出‘Impossible.’(没有引号)。 样例输入 553 .2..E ...2. 4.... ....4 ..2.. 000 注: 试题来源:ACM Central Europe 2005 在线测试:POJ 2946,UVA 3528
提示

样例输出 18

显然,该题是计算出发位置至出口的最短路。由于 007 推倒一次箱子被视为一步,因此 仓库状态对应的图是一个无权图,采用 BFS 搜索的方法计算这条最短路是最合时宜的。 ① 采用哈希技术判重 BFS 搜索的难度有 2 个: 存储量大:由于每一步是在先前仓库状态的基础上进行的,因此需要存储所有产生过 的仓库状态,这也是出题者之所以将仓库上限设为 8 的原因。 需要判重:若当前的仓库状态和以前计算出的仓库状态重复,则继续搜索下去势必出 现死循环。我们采用哈希技术判重: 按照自上而下、有左而右顺序给每个格子位置编号

当前仓库状态的哈希函数 m=

? ((位置i的字符) * 126
i ?1

n*n

i ?1

)% 3000007 。若走入空格

(x,y),则新的仓库状态的哈希函数 m’=(m+(x+126*y))% 3000007。 对 哈 希 表 中 所 有 已 计 算 出 仓 库 状 态 的 元 素 值 置 当 前 测 试 用 例 编 号 id hash[m]=hansh[m’]=?= id。若新计算出仓库状态 k,查询哈希表时发现 hash[k]=id,则

表明仓库状态 k 以前曾经产生过,应重新选择新的移动方向。 ① 扩展队首节点的方法 队列 Q 存储目前搜索到的非空格(出发点、目标点和堆有箱子的方格) ,元素包括当前 仓库状态 Q[].p、位置值 Q[].d((x,y)的位置值为 x*100+y)和步数 Q[].m。 若准备第 m 步走入(x,y),走前仓库状态为 p,则按照下述方法进行判重、目标判断和 入队操作: Viod add( p,x, y, M) { if ((x,y) 为出口标志 'E'){ flag = true; //返回成功标志和最少步数 m ans = M; return; } 计算 p 的哈希函数值 m 和新仓库状态的哈希函数值 m’=(m+(x+126*y))% 3000007; if (Hash[m’]==当前测试用例编号 id) return; Hash[m’] = id; ++Tail; //仓库状态 p、 (x, y)的位置值和步数 M 进入队列 Q //判重处理

Q[Tail].p= p;Q[Tail].d=x*100+y;Q[Tail].m=m; };

有了以上基础,我们便可得到扩展队首节点的办法了: void update(p,x,y,M) { //扩展队首节点(当前仓库状态为 p,位置为(x,y) ,步数为 m) for (int i=0; i<4; i++) //将(x,y)的 4 个相邻方向上的界内非空格送入队列 Q

{ 计算(x,y)的 i 方向上的相邻格(x’,y’) ; if ((x’,y’)在界内) &&( (x’,y’)!='.')add(p, x’,y’,M+1); } if ((x,y)为数字 c) for (int i = 0; i < 4; i++) { 统计 i 方向上相邻(x,y)的连续空格数 ok; if (ok == c){ //推倒(x,y)上的 c 个箱子

i 方向上 ok 个连续空格改为数字 1, (x,y)改为'.',得到新仓库状态 p’ add(p’,x’,y’,M+1); 恢复推前的仓库状态 p; } //进行判重、目标判断和入队操作

} ② 主程序

初始化: 输入初始仓库状态 p; if (出发位置(x,y)== 出口标志'E' 输出到达出口的最少步数为 0; 最少步数 ans =20 ;队列首尾指针 head=0,tail=-1; add(p,x,y,0);//将初始的仓库状态 p、出发位置(x,y)和步数 0 送入队列 Q 成功标志 flag=false; BFS 搜索: while (head<=tail && !flag) { //若队列非空且未到达出口 update(Q[head].p,Q[head].d/100,Q[head].d %100,Q[head].m); //扩展队首节点 ++head; } 输出结果: if (ans == 20 )
20 20

//队首元素出队

//若出发位置仍为初始值,则无解;否则输出解

输出"Impossible."; else 输出最少步数 ans;


更多相关文档:

信息学奥赛试题精选33题(附带题解)

信息学奥赛试题精选33题(附带题解)_学科竞赛_高中教育_教育专区。信息学奥赛试题精选33题(附带题解) 基础题:【1 Prime Frequency】 【问题描述】给出一个仅包含...

(信息学奥赛辅导)程序设计试题汇编(答案)

35页 免费 信息学奥赛试题精选33题(附... 53页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

信息学奥赛试题及答案

信息学奥赛试题 一、填空题(共 20 题,每题 1.5 分,共计 30 分。每题有 5 个备选答案,前 10 个题为单选题(即每题 有且只有一个正确答案,选对得分),...

信息学奥赛基础知识习题

信息学奥赛试题精选33题(附... 53页 免费 1999年—2011年信息学奥赛... 120页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...

信息学奥赛历年试题(解答)

信息学奥赛试题精选33题(附... 53页 免费 (信息学奥赛辅导)程序设计... 51...历年全国青少年信息学奥赛选择题每题有且仅有一个正确答案) 一、单项选择题(共...

信息学竞赛典型例题程序汇集

信息学竞赛习题 4页 1下载券 基本程序题集(信息学...(i6=i5+1;i6<=33;i6++) { a[6]=i6; for...不是解 // printf("输出检测到得位置,不是解")...

noip信息学奥林匹克竞赛初赛阅读程序题c++版本真题练习

noip信息学奥林匹克竞赛初赛阅读程序题c++版本真题练习_学科竞赛_小学教育_教育专区。noip信息学奥林匹克竞赛初赛阅读程序题c++版本。...

(信息学奥赛)选拔考试试题A卷

(信息学奥赛)选拔考试试题A卷_学科竞赛_初中教育_...(1)时量:40 分钟; (2)每道题简要写出关键过程,...13=1;23=3+5;33=7+9+11;43=13+15+17+19?...

信息学奥赛初赛复习题

信息学奥赛初赛复习题_学科竞赛_高中教育_教育专区。内部资料 注意保密 信息学...))) A) 13 B) 33 C) 18 D) 50 13、奔腾的地址线是 32 根,最大存储...

(信息学奥赛辅导)程序设计试题汇编(答案)

(信息学奥赛辅导)程序设计试题汇编(答案)_IT认证_...试题属于程序设计试题基础级别的思考题,五★级难度...(保留 2 为小数);(2)338350;(3)2550;(4)1717...
更多相关标签:
中学生信息学奥赛试题 | 信息学奥赛初赛试题 | 小学信息学奥赛试题 | 信息学奥赛复赛试题 | 信息学奥赛试题 | 初中信息学奥赛试题 | 小学生信息学奥赛试题 | 信息学奥赛2015年试题 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com