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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

第2天的试题  

2010-07-21 15:13:01|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

 

NOI北京集训

 

 

 

题目一览

 

题目名称

字母游戏

超级斗兽棋

兔子谜题

代号

alphabet

animal

rabbit

输入文件

alphabet.in

animal.in

rabbit.in

输出文件

alphabet.out

animal.out

rabbit.out

时限

1

1

1

 

 

(2010721  5小时完成)

 

 


字母游戏

(alphabet.pas/c/cpp)

时间限制:1s 内存限制:64MB

【问题描述】

    Johnny三岁生日的那天,他的爸爸送他一份生日礼物——一堆刻上'A'~'Z'的字母的小石头。作为一个对未知世界无限渴求的具有丰富想象力的小孩,他创造了一款新的游戏。

    首先,他取出一些石头排成一个圈。他取一个石子作为游戏开始的位置,并取定一个整数k。每一轮,Johnny往逆时针方向数k个石子,然后把一个新的石子插在这个石子后面。这个新石子上所刻的字母必须是放在它之前的石子的字母的后继('Z'的后继是'A')。各种石子的数量足够多,所以不用担心游戏没法进行下去。

    对于Johnny这个词和k=3的情况下,前4轮的情况。

    Johnny渐渐对这个游戏失去了耐心,他现在只想知道第m轮时他放的石子所刻的字母。

    你能帮助他吗?

 

【输入文件】

    输入文件alphabet.in。第一行,数据组数T。接下来T组数据,每组数据:第一行共有三个数:n——初始时石块的数量,k——每轮数石子的个数,m——游戏轮数。第二行是n个大写字母,第一个字母就代表游戏开始的石头。

 

【输出文件】

    输出文件alphabet.out。对于每个数据输出一个数,占一行,表示第m轮插入的石头上的字母。

 

【样例输入】

1

6 3 4

JOHNNY

 

【样例输出】

Z

 

【数据规模】

T<=5

20%的数据m<=1000

70%的数据m<=1000000

100%的数据1<=n<=10000,1<=k<=10000,1<=m<=1000000000 

超级斗兽棋

 (animal.pas/c/cpp)

时间限制:1s 内存限制:64MB

【问题描述】

    斗兽棋是一项有趣的棋类游戏。双方分别控制一些动物,在棋盘上按照一定的规则轮流行动,先占领对方巢穴为胜。任意两种不同的动物AB相遇,要么AB,要么BA

    不过,原先的斗兽棋中动物种类较少,玩久了就会略显无聊。于是,某公司决定开发一种超级斗兽棋,含有N种动物,编号为1,2,……,N,并已经制定好了任意两种不同动物相遇时的胜负关系。

    下一步工作是测试超级斗兽棋的趣味性。经调查发现,若动物间相互制约,则游戏的趣味性将大大增加。所谓动物间相互制约,即可以将动物按某种次序排成一个序列P1P2,……,Pn,满足P1P2P2P3,……,Pn-1)胜PnPnP1。如果动物间不能相互制约,但可以半相互制约(在相互制约的条件中去掉“PnP1,其他条件不变)的话,那么这款游戏虽然趣味性有所降低,但勉强可以接受。不过,如果连半相互制约都不能满足的话,呵呵,对不起,重新设计吧。

    你的任务就是帮助测试这款超级斗兽棋的趣味性。

 

【输入文件】

    输入文件animal.in。第一行是一个整数n,表示动物种类数。接下来是一个n*n的矩阵,为动物间的胜负关系,第i行第j列为1ij,为0ji(保证胜负关系不会矛盾,即不同的ij相遇有且仅有一个胜者;主对角线上全为0)。

 

【输出文件】

    输出文件animal.out。第一行是一个整数s,表示测试结果:0表示动物间相互制约,1表示动物间不相互制约但半相互制约,-1表示都不满足。若测试结果不为-1,则在第二行输出满足响应条件的任一序列P(即测试结果为0时输出满足相互制约条件的序列,为1时输出半相互制约条件的序列)。

 

【样例输入】

5

0 0 1 1 1

1 0 1 1 0

0 0 0 1 0

0 0 0 0 1

0 1 1 0 0

 

【样例输出】

0

1 3 4 5 2

 

【数据规模】

20%的数据,n<=10

100%的数据,2<=n<=200

兔子谜题

(rabbit.pas/c/cpp)

 

【问题描述】

       在一条直线上有三只兔子和三个兔子窝,它们的坐标均为整数,分别是abcnanbnc

       每一次操作你可以选择一只兔子作为起跳兔子,设它的坐标是x,再选择另外一只作为踏板兔子,设它的坐标是y。操作之后起跳兔子的位置变成了y+y-x,即:原来位置关于踏板兔子的对称点。

       需要注意的是,每一次跳跃不允许让这个兔子正好落到另外一只的头上,如下图所示:

       另外的,起跳兔子不能够跨越过两只兔子:

   

       其他的满足上述条件的跳跃都是允许的:

   

       现在给定一个正整数K,问:有多少种操作次数恰好K的操作方式,可以使得操作之后所有的兔子都进入了兔子窝中。(注意,兔子和兔子窝没有对应关系,只需要每一只兔子进入了一个兔子窝即可。)

       这个答案可能非常大,所以,你只需要输出它模1000000007109+7)的值。

【输入文件】

       输入文件为rabbit.in

       第一行三个整数:abc。(a < b < c

       第二行三个整数:nanbnc。(na < nb < nc

       第三行一个正整数:K

 

【输出文件】

       输出文件为rabbit.out

       只有一个自然数:方案数模1000000007109+7)的值。

【输入样例】

0 5 8

0 8 11

3

【输出样例】

5

【输入样例2

5 8 58

13 22 64

58

【输出样例2

0

数据规模和约定

20%的数据中K ≤ 10

70%的数据中K ≤ 50

100%的数据中K ≤ 100-1018 abcnanbnc ≤ 109

 

 第一题:一个约瑟夫 ,注意参考IOI箭术的思想:我们只关注什么

第三题:把它想成一个树,中间兔子往外跳=往儿子走,往里跳=往父亲走

我们只关注:我的深度,我和目标点的lca的深度

第二题:

一定不会有-1

构造链的方法:插入排序!

那怎么构造环呢?

随机化!

随机构造一个链,看是不是

另:正解:扩展环,往一个已有的环里插入一个点,若无法插入,一定是秒了整个环或被整个环秒。如果有了好多个怎么窘的点,

那么他们一起加入这个环就好了!

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

历史上的今天

评论

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

页脚

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