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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

练习题  

2010-08-31 20:56:56|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
应yjy的要求,我出了一套针对noip2010的练习题。
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/Exercise^_noip2010^_fromfhq.zip
标程和数据不保证对,发现错误者请迅速和我联系。
难度说实话比较大,不过骗高分很容易。
主要考察了搜索优化、dp、Hash、图论的内容。

NOIP练习题(来自fhq)

名称

语言识别

字符串搜索

构造数列

抢劫

时限

1s

2s

1s

1s

内存限

256M

256M

256M

256M

代码长度限

50K

10K

50K

50K

输入文件名

lang.in

ssearch.in

mklist.in

rob.in

输出文件名

lang.out

ssearch.out

mklist.out

rob.out

程序名

lang.*

ssearch.*

mklist.*

rob.*

备注

禁止打表

注:定义1s为以下语句在测评机上运行时间的1/4

for (register int i=1;i;i++);

语言识别

【题目描述】

自然语言理解是一个新兴的领域。其中,判断一个给定的文本是什么语言就是一个非常基础但重要的问题。

给定一段文本,请输出它是中文、英文还是俄文。

【输入文件】

输入文件包含5行文字,每行至少30个字节,至多1000个字节。每行中可能有空格。

【输出文件】

对于输入的每行,请输出它的语言类型(中文/English/Русский )

【输入样例】

我爱信息学!信息学是一个有趣的学科。

I love informatic!Informatic is an interesting subject.

Я люблю информатикиИнформация наука интересная тема.

这题源自IOI2010,不过已经被我大大简化了(原题可是有56种语言的)。

This problem comes from IOI2010, but it has been greatly simplified (there are 56 languages in the original problem). 

【输出样例】

中文

English

Русский 

中文

English

【备注】

为了避免字符编码产生问题,输入输出样例文件应当被附带给你。

20%的数据满足:只有中文和英文。

字符串搜索

【题目描述】

如果一个字符串可以写成某个字符串重复自身N次,那么我们叫它N重复的。例如:ABABAB3重复的,但不是2重复的。

请找出有多少个由前K个大写字母组成的长度不超过N的字符串是A重复的但其任何连续子串(不包括本身)都不是A重复的。

【输入文件】

一行三个正整数

N K A

【输出文件】

一个整数,表示最终答案数。方便起见,你只用输出最终答案模1000003的余数即可。

【输入样例】

10 2 2

【输出样例】

4

【备注】

满足样例的字符串:

AB

BA

ABAB

BABA

禁止打表!一经发现此题0分。请注意代码长度限制!

对于50%的输入数据,KN次方小于1000000

对于90%的输入数据,(K/A)N次方小于1000000

对于100%的输入数据,N22K262A26

温馨提示:这题拿90分就挺好了,不要太贪心。注意为剩下的题留出时间。

构造数列

【题目描述】

为了补偿上面2题太恶心,fhq决定出一个dp水题。

请你计算一下一共有多少个N个整数组成的数列满足以下的性质:

1.第一个数是0

2.相邻两个数之间的差的绝对值是1

3.整个数列的和等于S

【输入文件】

一行两个整数

N S

【输出文件】

一行一个整数,总共的数列个数。方便起见,你只用输出答案模1000003的余数即可。

【输入样例】

4 0

【输出样例】

2

【备注】

满足样例要求的数列是

0 1 0 -1

0 -1 0 1

一共2

对于40%的数据满足:N16

100%的数据满足:N100,|S|2147483647

抢劫

【题目描述】

一个职业大盗xyj来到了一个陌生的国家抢劫。这个国家由若干个城市组成,城市之间由一些单行路连接起来。xyj来到了城市S,并且打算在这个国家“旅游”一圈,最后从城市T坐飞机离开。他每到达一个城市就把这个城市的所有井盖都抢走。注意:xyj可以到某个城市“旅游”好多次,但每个城市的井盖只能被他抢劫一次。

城市是从0编号到N-1的。

例如下图:

(贴图片比较费劲,自己看样例吧)

他打算从城市0出发,到城市5离开。

每个城市的井盖数目为:

城市

0

1

2

3

4

5

6

7

井盖数

2

3

6

9

8

7

4

5

他的一条可能的旅游线路是:

01254345

这样,他可以抢走城市0 1 2 3 4 5的所有井盖,一共35个。

他已经自己设计好了一条旅游线路,想让你帮他算算这个旅游线路是否合法,以及最终可以抢到多少个井盖。同时,他也许要求你帮他算算他的线路是不是最优的。

【输入文件】

第一行两个整数N M S T,表示城市数和单行路的个数,以及出发和离开的城市编号。

下面一行N个非负整数A[0],A[1]...A[N-1],分别表示每个城市的井盖数量(所有的井盖数之和小于2147483648)。

下面M行,每行2个整数X Y,表示有一条单行路从X走到Y

接下来一行有一个字符串。

1)如果这个字符串是“Judge”(没有引号),那么你要帮他算算他的线路是否合法以及最终收益:

接下来一行有一个整数RR2N),表示他设计的线路经过的城市数。

下面一行有R个位于[0,N)之间的正整数,表示他的线路依次经过的城市编号。

2)如果这个字符串是“Compute”,那么你要计算最优线路能抢到的井盖数并输出。

【输出文件】

如果字符串是“Judge”,你要输出一个整数他的线路能抢到的井盖数。如果他的线路不合法,且至少存在一个合法线路,输出-1.如果他的线路不合法,但根本不存在合法线路,输出0.

如果字符串是“Compute”,你要输出一个整数表示最优线路能抢到的井盖数。如果不存在合法的线路,输出-1.

【输入样例1

8 10 0 5

2 3 6 9 8 7 4 5

0 1

1 2

2 5

1 3

3 4

4 3

5 4

4 5

6 3

4 7

Judge

8

0 1 2 5 4 3 4 5

【输出样例1

35

【输入样例2

8 10 0 5

2 3 6 9 8 7 4 5

0 1

1 2

2 5

1 3

3 4

4 3

5 4

4 5

6 3

4 7

Judge

12

0 1 2 5 4 3 4 5 4 7 4 5

【输出样例2

-1

【输入样例3

8 10 0 5

2 3 6 9 8 7 4 5

0 1

1 2

2 5

1 3

3 4

4 3

5 4

4 5

6 3

4 7

Compute

【输出样例3

35

【输出样例4

8 10 0 6

2 3 6 9 8 7 4 5

0 1

1 2

2 5

1 3

3 4

4 3

5 4

4 5

6 3

4 7

Compute

【输出样例4

-1

【备注】

一共10个输入文件,其中前5个文件的字符串都是Judge,且这10个文件的分值之和是60分。

对于40%的数据,N100M1000

对于100%的数据,N10000M100000

温馨提示:JudgeCompute的设置是为了送分的,因为计算最优答案的代码真的好长。这题拿60分就已经可以让你的总分很高了,请注意时间!

另:猜猜xyj代表的是哪位同学?


基本思路:

第1题:送分,不过想拿到手是有挑战的。

我的方法:先判断它是不是英文或俄文。判断方法是统计英文/俄文字母出现的频率,如果在0.4以上,就认为是相应语言。

注意以下句子:

《算法导论》是一本优秀的算法书。

NOI是“中国青少年信息学奥林匹克”的简称。

Be carefull! There may be numbers (0123456789) and some special characters (!@#$%^&*) in the data.


第2题:搜索!

如果有神牛有多项式算法欢迎讨论。

不过搜索是有技巧的。我的优化方法是:搜索“本质不同”的解。

例如:我们把

zbzzc和eaeed等等字符串都“抽象”成12113这个“模板”,只搜索模板,之后排列组合一下即可。


第3题:dp

设由i个数组成的和为j的满足题目要求的数列个数为f[i][j],则

f[i][j]=f[i-1][j-i+1]+f[i-1][j+i-1];

至于为什么请自己想。


第4题:Hash+图论

第1问就是送分用的。可以写任何一种方法判断边是否存在(我在标程里用的方法其实是二分查找,没有Hash,随便啦),之后bfs判断连通性(dfs也行)

第2问的代码比较长,不过思想很简单,

就是把每个强连通分量都缩成一个点,

之后dp就行了。

  评论这张
 
阅读(1136)| 评论(4)
推荐 转载

历史上的今天

评论

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

页脚

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