注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

2008烟台oi夏令营信息学夏令营的考试...(2) (2009-03-15 20:56:19)  

2014-09-02 10:30:46|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
标签: 

杂谈

提高1,测试题..

 

一.剔除多余括号(delkh.pas/.in/.pas)

给定一个含有+、-、*/、(、)六种符号的运算表达式,表达式中可能含有多余的括号,编成整理该表达式,去掉所有多余的括号,原表达式中所有的变量和运算符的相对位置和顺序保持不变,并保持与原表达式等价。

如:

输入表达式         输出表达式

a+(b+c)            a+b+c

(a*b)+c/d          a*b+c/d

a*(b+d)            a*(b+d)

a+b/(c-d)          a+b/(c-d)

((a+b)*f)-(i/j)    (a+b)*f-i/j

说明:所有的变量均为单个的小写字母;只要求去掉多余的括号,不要求对表达式化简。

输入格式:一行,待处理的表达式

输出格式:一行,删除多余括号后的表达式。

样例输入:a+(b+c)

样例输出:a+b+c

题解:字符串处理

 

 

二.金字塔(Pyramid.pas/.in/.out)

问题描述:

有一盗墓者潜入一金字塔盗宝。当她(难道是Lara Croft ?)打开一个宝箱的时候,突然冒出一阵烟(潘多拉的盒子?),她迅速意识到形势不妙,三十六计走为上计…… 由于她盗得了金字塔的地图,所以她希望能找出最佳逃跑路线。地图上标有N个室,她现在就在1室,金字塔的出口在N室。她知道一个秘密:那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线,使得在最坏的情况下所用的时间最少。

 

输入格式:

从文件PYRAMID.IN读入数据,文件第一行有两个正整数N(3 ≤ N ≤ 100)和M(3 ≤ M ≤ 2000),下面有M行,每行有三个数正整数U、V、W,表示直接从U室跑到V室(V室跑到U室)需要W(3 ≤ W ≤ 255)秒。

 

输出格式:

输出所求的最少时间(单位为秒)。

 

样例

PYRAMID.IN

PYRAMID.OUT

7 8

1 2 10

2 3 12

3 4 20

4 7 8

1 7 34

2 5 10

5 6 12

6 4 13

 

66

 

 

说明

基本上有三种路线:

一:1 -> 2 -> 3 -> 4 -> 7   

总时间为 10 + 12 + 20 + 8 = 50,最坏的情况是 3->4 那一段,要多花20秒(因为行走速度减半),所以这条路选最坏需要 70 秒

二:1 -> 2 -> 5 -> 6 -> 4 -> 7 

总时间为 10 + 10 + 12 + 13 + 8 = 53,最坏的情况是 6->4 那一段,要多花13秒(因为行走速度减半),所以这条路选最坏需要 66 秒

三:1 -> 7                 

总时间为 34 = 34,最坏的情况是 1->7 那一段,要多花34秒(因为行走速度减半),所以这条路选最坏需要 68 秒

题解:图论+枚举

 

 

三.海明码(hamming.pas/.in/.out)

给出 N,B 和 D:找出 N 个编码(1 <= N <= 64),每个编码有 B 位(1 <= B <= 8),使得两两编码之间至少有 D 个单位的“海明距离”(1 <= D <= 7)。“海明距离”是指对于两个编码,他们的二进制表示法中的不同二进制位的数目。看下面的两个编码 0x554 和 0x234 之间的区别(0x554 表示一个十六进制数,每个位上分别是 5,5,4):

       0x554 = 0101 0101 0100

       0x234 = 0010 0011 0100

不同的二进制位: xxx xx

因为有五个位不同,所以“海明距离”是 5。

输入格式:一行,包括 N, B, D。

输入样例:

16 7 3

输出格式:

N 个编码(用十进制表示),升序排列,十个一行。如果有多解,你的程序要输出这样的解:假如把它化为 2^B 进制的数,它的值要最小。

输出样例:

0 7 25 30 42 45 51 52 75 76

82 85 97 102 120 127

题解:搜索

 

 

四.盒子与球(boxball.pas/.in/.out)

现有r个互不相同的盒子和n个互不相同的球,要将这n个球放入r个盒子中,且不允许有空盒子。问有多少种放法?

例如:有2个不同的盒子和3个不同的球(分别编为1、2、3号),则有6种不同的放法:

((1),(2、3));    ((1、2),(3));    ((1、3),(2));

((2),(1、3));    ((2、3),(1));    ((3),(1、2));

输入格式:一行,两个整数n和r,中间用一个空格分隔。(0<=n,r<=10)

输出格式:一个整数(保证在长整数范围内),表示n个球放入r个盒子的方法。

样例:

输入:3 2

输出:6

 

 

题解:数学/递推(第二类斯特灵数)

  评论这张
 
阅读(30)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017