MM群2007七夕模拟赛试题
题号 1 2 3 4 5
题目 过去的姫君 找啊找啊找GF 百无禁忌 最遥远的心 美丽的中国结
主文件名 hime gf gene furthest knots
扩展名 pas/c/cpp pas/c/cpp pas/c/cpp pas/c/cpp pas/c/cpp
时间限制 1 sec 1 sec 1 sec 1 sec 1 sec
空间限制 64 MB 64 MB 64 MB 64 MB 64 MB
满分 10*10 10*10 10*10 10*10 10*10
附加文件 N/A N/A N/A N/A N/A
题目类型 传统 传统 传统 传统 传统
注意事项(请认真看完以下事项):
此次测试与NOIP相同,采用文件输入输出,请认真核对您的输入/输出文件名,大小写不限.
关于此次题目的分配问题
这次大家可能都注意到了,一共有5道题.其中,我们把第四题叫做MM题,把第五题叫做GG题.这五道题的分配如下:
如果您没有注册的话,那么您提交的程序将不被评测.
如果您注册时填写的性别是MM,那么您提交的程序只会被评测1,2,3,4题.也就是说,即使您做了第5题,我们也不会将其计算入总分.
如果您注册时填写的性别是GG,那么您提交的程序只会被评测1,2,3,5题.也就是说,即使您做了第4题,我们也不会将其计算入总分.
关于此次比赛的提交问题
此次比赛的提交采用邮件提交,提交邮箱为[email]rlesubmit@gmail.com[/email].具体提交方式如下(请特别注意黑体字):
首先,请建立一个文件夹(文件夹可以在磁盘的任意位置建立,这个对最后的提交没有影响),名称为您注册时使用的用户名.
然后,请打开这个文件夹,并将您完成的所有程序放到这个文件夹下.只有pas/c/cpp扩展名的文件才是有效文件,如果您提交了exe文件,我们将忽略并强制重新编译源文件.这个文件夹下不要建立任何的子文件夹.
接下来,请将此文件夹压缩成zip/rar/7z中的一个格式.我们使用WinMount解压,所以其它格式有可能不被支持.
请将压缩好的文件作为附件使用您注册时的邮箱发送给我们,注意一定不要更改文件名或者邮箱,否则提交无效.
如果不清楚压缩方法,请一定看下面的介绍.如果压缩文件内的内容有误,我们有可能不会手工进行调整.望谅解.
------------------------我是朴素的分割线----------------------
压缩方法(以WinRAR为例):假设您的用户名是test(这个只是假设,请替换成您的实际用户名),而且在硬盘上已经建立了一个名为test的文件夹,并已经将所有源代码放入此文件夹.请在该文件夹的图标上点击鼠标右键,并在弹出的菜单中选择“添加到 "test.rar"一项.用鼠标左键点击,稍等片刻,此时会出现一个名为test.rar的压缩好的文件.
如果您对以上几条有任何疑问,一定要在在线答疑系统上问清楚再答题,我们在oibh,rle,oifans上进行答疑
关于评测系统
此次比赛使用的评测系统是胡伟栋的清澄评测系统1.1.1.1046.编译器为我们自己外接的FPC2.0.4与GCC/G++3.4.2.
关于评测机配置
型号(笔记本): Lenovo 旭日410A
CPU: Core Duo T2050
内存: 1GB DDRII 667
硬盘: 2.5英寸笔记本电脑专用硬盘
过去的姫君
(hime.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
题目背景
忠诚的骑士Rai为他心爱的公主Hon设计钻石组坠.
他正在考虑如何切割能够使钻石最光彩夺目.
他手中有K颗小钻石,他知道应该切出N个顶点.
传说如果每颗钻石上的三角形总数加起来最少时,能够达到最好效果.
题目描述
为了更好的研究问题.
Rai在平面上画了N个点,任意三点不共线.
他要把这N个点分成K组,每组至少三个点.
在分完组后 Rai把同组的任意两点之间都连一条边(即所有点对之间都存在一条边),不同组点不连边.
那么,形成的图形中,总共最少有多少个由连边作为三角形边的三角形?
输入
只有一行,N和K,用空格隔开.
输出
最少的三角形数.
输入样例
9 2
输出样例
14
数据规模
对于100%数据,3*K<=N<=maxlongint.
样例解释
分成两组,一组4,一组5.
Hint
无
出题人
Thunder GG
找啊找啊找GF
(gf.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
题目背景
"找啊找啊找GF,找到一个好GF,吃顿饭啊拉拉手,你是我的好GF.再见."
"诶,别再见啊..."
七夕...七夕...七夕这个日子,对于sqybi这种单身的菜鸟来说是多么的痛苦...虽然他听着这首叫做"找啊找啊找GF"的歌,他还是很痛苦.为了避免这种痛苦,sqybi决定要给自己找点事情干.他去找到了七夕模拟赛的负责人zmc MM,让她给自己一个出题的任务.经过几天的死缠烂打,zmc MM终于同意了.
但是,拿到这个任务的sqybi发现,原来出题比单身更让人感到无聊-_-....所以,他决定了,要在出题的同时去办另一件能够使自己不无聊的事情--给自己找GF.
sqybi现在看中了n个MM,我们不妨把她们编号1到n.请MM吃饭是要花钱的,我们假设请i号MM吃饭要花rmb[i]块大洋.而希望骗MM当自己GF是要费人品的,我们假设请第i号MM吃饭试图让她当自己GF的行为(不妨称作泡该MM)要耗费rp[i]的人品.而对于每一个MM来说,sqybi都有一个对应的搞定她的时间,对于第i个MM来说叫做time[i]. sqybi保证自己有足够的魅力用time[i]的时间搞定第i个MM^_^.
sqybi希望搞到尽量多的MM当自己的GF,这点是毋庸置疑的.但他不希望为此花费太多的时间(毕竟七夕赛的题目还没出),所以他希望在保证搞到MM数量最多的情况下花费的总时间最少.
题目描述
sqybi现在有m块大洋,他也通过一段时间的努力攒到了r的人品(这次为模拟赛出题也攒rp哦~~).他凭借这些大洋和人品可以泡到一些MM.他想知道,自己泡到最多的MM花费的最少时间是多少.
注意sqybi在一个时刻只能去泡一个MM--如果同时泡两个或以上的MM的话,她们会打起来的...
输入
输入的第一行是n,表示sqybi看中的MM数量.
接下来有n行,依次表示编号为1, 2, 3, ..., n的一个MM的信息.每行表示一个MM的信息,有三个整数:rmb, rp和time.
最后一行有两个整数,分别为m和r.
输出
你只需要输出一行,其中有一个整数,表示sqybi在保证MM数量的情况下花费的最少总时间是多少.
输入样例
4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
输出样例
13
数据规模
对于20%数据,1<=n<=10;
对于100%数据,1<=rmb<=100,1<=rp<=100,1<=time<=1000;
对于100%数据,1<=m<=100,1<=r<=100,1<=n<=100.
Hint
sqybi说:如果题目里说的都是真的就好了...
sqybi还说,如果他没有能力泡到任何一个MM,那么他就不消耗时间了(也就是消耗的时间为0),他要用这些时间出七夕比赛的题来攒rp...
出题人
sqybi GG
百无禁忌
(gene.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
题目背景
以现在的认知,猫和狗不能杂交基于以下几点:
1.猫是猫科的,而狗是犬科的;
2.猫有19对染色体,而狗有39对(提醒!!不能说染色体多的比较聪明.因为植物通常比人类的染色体信息量多上上百倍);
3.猫和狗总是打架.这是因为猫和狗的肢体语言和声音语言全都是相反的:摇尾巴和伸出爪子的意思,猫猫认为是狗狗要打它,而狗实际的意思是表示友好;发出呼噜噜的声音,猫猫的意思是"咱们一块玩吧",狗听起来却是挑衅....所以越说越乱了....当然,一出生就生活在一起的猫狗掌握彼此的外语,所以就米有事乐.但是这样的猫狗把彼此当作亲人,基于生物学某些原因(不赘述),所以也不可能产生杂交行为.
但是
乌-龟-天-空-游~
火-星-撞-地-球~
-------------一只木瓜飞过,我是Vitta天才的分割线---------
题目描述
某天,作为冰激凌店主的Vitta由于某些类似于天上掉下一只鸭子地上长出一颗南瓜之类的理由突发奇想,利用一些,或者很多生物工程技术实现了这一跨物种,跨染色体界限,跨世纪,跨时代的胡搞事件.
但是作为一个世界和平爱好者,美的使者和拥护者,自然的维护者,拥有正常健康心态的善良少女.V很不希望搞出一些长得像土豆或者胡萝卜的东西.所有引起食欲不振和消化不良的东西都应该统统不存在,而不是从高尚高贵的V手中被接生到这个世界.
所有恶心和离奇的东西里,V最不接受的是----肥胖!!
可是手底下可以搞的喵喵汪汪太多了丫.....Vitta懒得挨个去分析...写个东西给V吧.可获得免费冰激凌券,和....."猫狗"照片一张.
肥胖(Wi)是数量遗传.毕竟没有东西可以粗暴划分成胖和瘦两种类型.控制该性状的基因w和i是完全不连锁的.即互相不影响.且肥胖是显性的(大写),瘦削是隐性的(小写).且为了保持品种单纯,只进行族内自交.即不可能出现和非原始亲本后代交配的行为.杜绝同性产子.
举例:
父母亲本是 肥胖 ( WWII )× 瘦削 ( wwii)
父亲产生的配子必然是WI 母亲产生的配子必然是wi
第一代产生的全部是中等表现性的 即WwIi
其中选出雌雄各一只个体 杂交
中等雄( WwIi)×中等雌( WwIi)
得到第二代
雄的配子有25%可能性WI,25%可能性Wi,25%可能性wi,25%可能性wI.
雌的配子同上
结合状态
WI Wi wi wI
WI WWII WWIi WwIi WwII
Wi WWIi WWii Wwii WwIi
wi WwIi Wwii wwii wwIi
wI WwII WwIi wwIi wwII
算得有如下概率(ff,f,m,t,tt为性状表示)
性状 肥胖ff 较胖f 中等m 较胖 中等 较瘦t 中等 较瘦 瘦削tt
基因 WWII WwII wwII WWIi WwIi wwIi WWii Wwii wwii
概率 1/16 2/16 1/16 2/16 4/16 2/16 1/16 2/16 1/16
输入
第一行给出一共出现的,已知性状情况的代数,整数n,n<10.
以后连续n行给出每代出生的,有序的动物情况若干个(每代出生动物个数小于10),性别表示为a(雌)b(雄),与性状连续表示为诸如aff,btt.
然后连续n行给出是每代第几只和第几只动物进行再次交配以繁衍出的下一代.每代只选一对进行交配.分别是两个整数.
最后一行给出需要找出的表现型(仅有一个).
输出
n+1代需要找出的表现型的出现概率(保留六位小数).
当出现任何无法计算,不符合题意,以及不可能出现的数据(根据其父母本及以上亲缘关系的表现型不可能杂交出来的该动物表现型)均输出"wrong"(不包括引号).
输入样例1
2
aff btt
am am bm
1 2
2 3
t
输出样例1
0.250000
输入样例2
2
aff btt
am am bm
1 2
2 1
t
输出样例2
wrong
输入样例3
2
aff btt
am af bm
1 2
2 3
t
输出样例3
wrong
数据范围
n<10,每代出生动物个数小于10
Hint
无
出题人
Vitta MM & winsty GG
最遥远的心
(furthest.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
题目背景
大家都知道...这个世界上,zmc小菜最爱的人是-----------------------------------------------外婆.
但是,sqybi大牛把题AC的差不多之后,太无聊了,决定去搞点情报玩玩,不仅带人偷拍zmc小菜的照片...还想搜集zmc小菜的人际关系资料....
题目描述
经过百般花招之后,sqybi牛得到了一张zmc小菜的"人物关系网",但是,sqybi牛今天晚上要陪mm,没有时间,而你作为sqybi牛的助手,这个任务只好交给你来完成.
zmc小菜的"人物关系网"上有n个人及他们的名字,每个人之间都有一定的关系,每2个人间的关系亲密度用一个数字表示,数字越大,表示关系越淡薄,数字越小，关系越亲密(当亲密度>=0时),每个人对自己是最亲密的(可以看作亲密度为0).而且A对B的关系亲密度不一定等于B对A的亲密度,这就像爱情一样,GG对MM好,MM却不一定领情......
在这个关系网中,人可以通过别人来增进感情,比如,如果A对B感情亲密度是3，B对C感情亲密度为2，A对C感情亲密度为7，那么在B的努力下，A对C的感情亲密度将为3＋2＝5而不是7，当然，假定这样的传递只会朝使关系更亲密的方向进行（即让亲密度更小）。
在生活中...暂时没有感情和永远没有感情是不一样的.....所以在这个网中....如果A不能通过任何人到达B,表明A永远不会对B产生感情,如果A对B暂时没有感情,则A到B的数字标记为-1
如果原来A对B暂时没有感情,A对C的亲密度为3,C到B的亲密度为2,则这次改进的结果为A到B的亲密度以5计算
如果原来A对C永远没有感情,A对B暂时没有感情,B对C亲密度为3,则这次改进的结果为A对C也暂时没有感情
Sqybi牛想知道的是...当所有能改进的关系都改进了以后,在这张关系网中，谁对zmc的关系最淡薄，也就是说，谁是最遥远的那一颗心。
注：永远不会产生感情 比 暂时没有感情 淡薄，如果这2种情况都不发生，则认为亲密度最大的关系最淡薄
如果关系最淡薄的不只一人....就以字典序最前的一人名字为最遥远的.....因为..在zmc小菜的字典里.....那个人一定也在前面~!
输入
第一行,m(表示有m行信息)
..m+1行,每行一个2个字符串name1,name2(长度小于等于14)和一个整数c,用空格隔开,表示name1对name2的亲密度为c,保证name1和name2不相等
zmc的名字为"ZMC"(保证存在),每个人的名字只由大写字母组成
输出
一行,有一个字符串name3和一个整数a,用空格隔开
Name3是对zmc关系最淡薄的人的名字,a为Name3是对zmc的关系,如果name3对zmc永远不会产生感情,输出-2,如果name3对zmc暂时没有感情,输出-1,否则则输出name3对zmc的亲密度
输入样例
4
TOM FX 3
FX TOM 2
TOM Q 4
Q ZMC 3
输出样例
FX 9
数据范围
对于30%的数据,1<=m<=10
对于所有数据 1<=m<=100;1<=c<=100或c=-1
Hint
献给世界上最遥远的心
出题人
ddeggzmc MM
美丽的中国结
(knots.pas/c/cpp/in/out)
时限:1 sec | 内存: 64 MB
题目背景
kitty刚刚高三毕业.看到同学们都回家的回家,旅游的旅游,她的心里有些落寞.英俊潇洒风流倜傥迷倒万千KL却仅对kitty感冒的fish看在眼里,急在心里.一天,fish提出和kitty两个人一起外出旅游.kitty犹豫了几天,想好能瞒过家长的理由后（要问是什么……自己猜去）,答应了.fish很高兴地带着kitty去登记了（别想歪,登记旅游团而已……）,日照青岛五日游.
当然啦,他们玩得很高兴.虽然这次旅行是fish先提议的,但kitty因为玩得很畅快（刚高考完嘛）,所以想送给fish一份礼物,一份能让见多识广的fish都无法忘怀的礼物.她从路边 9¾站台的某算命先生那里得知中国结具有增加RP的效果,而这正是fish所需要的,因此她决定动手给fish编一个奇特的中国结.
题目描述
中国结形式多样,fish会喜欢什么样的呢?思考几天后,kitty决定给fish编一个树状的中国结.这个中国结有n个结点（编号1,2,…,n）,这n个结点之间总共恰有n-1条线相连,其中结点1上是树的根.这是一个奇特的中国结,因此它的编织方式也很奇特.在编织过程中的每一步骤,kitty有时需要将一个结点子树里的所有结点i的状态全部取反（如果原来结点i已经打结,则解开i,否则将结点i打结）,有时又需要知道一个结点的子树里有多少已经打结的结点,你能帮助可爱的kitty完成这份礼物吗?
输入
第一行有个整数n,表示这个中国结有n个结点
以下n-1行,每行有两个整数u和v(1≤u,v≤n),表示结点u和v间有一条线相连；
再一行有个整数m,表示kitty要进行的步骤数
以下m行,每行可能为:
"C x":表示将结点x的子树中所有结点的状态取反（包括x）
或
"Q x":表示kitty想知道结点x的子树中有多少已经打结的结点（包括x）
输出
对于每个“Q x”输出一行整数,表示结点x的子树中有多少已经打结的结点（包括x）
输入样例
5
1 2
1 3
2 4
2 5
5
Q 1
C 1
Q 1
C 2
Q 1
输出样例
0
5
2
数据规模
对于40% 的数据,1≤n≤10000, 1≤m≤20000
对于100%的数据,1≤n≤100000, 1≤m≤100000
Hint
无
出题人
菜鱼 GG
特别策划~~
哈哈~~在天才的sqybi的策划下,我们推出了这个栏目~~
一些出题人,每个人都会在这里说一段话...他们会说什么呢?
请看~~
sqybi GG:
我没什么可说的.祝大家七夕幸福.另外对所有知情的人说一句对不起.对zmc MM说一句谢谢.
winsty GG:
MM天天有，敬请关注MM群～～～
vitta MM:
上个七夕有极其猥琐的回忆.....
thunder GG:
你说牛郎和织女无不无聊...
ddeggzmc MM:
bless...祝福世界上的所有人...
菜鱼 GG:
献给没有赶上去年双七夕的couples一个愉快的七夕……
谢谢您--by sqybi
