2011年浙江省省队选拔二试题目.doc

NOI2011 浙江省队选拔赛 第二试 道馆之战NOI2011 浙江省队选拔赛第二试竞赛时间：2011年5月28日上午8:00-13:00题目名称细胞营救皮卡丘道馆之战目录cellrescuefight可执行文件名cellrescuefight输入文件名cell.inrescue.infight.in输出文件名cell.outrescue.outfight.out每个测试点时限2秒1秒4秒内存限制256 M256 M256 M测试点数目201010每个测试点分值51010是否有部分分否否否题目类型传统传统传统附加文件无无无提交源程序须加后缀对于Pascal语言cell.pasrescue.pasfight.pas对于C 语言cell.crescue.cfight.c对于C+ 语言cell.cpprescue.cppfight.cpp注意：最终测试时，所有编译命令均不打开任何优化开关。细胞【问题描述】2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为n的数字串，且仅含有19这9种数字，沿着细胞的躯干从头到尾排列着。首先，细胞会经历一次分裂。细胞将沿躯干方向分裂成若干个球体，躯干将退化成丝状物，连接着相邻的球体。在分裂过程中，质量是均匀分布的。换句话说，若分裂成k个球体，每个球体的质量为原来的1/k。然而，密码的分布是不确定的。若分割成k个球体，密码会被切割成k段（每段长度至少为1），并按从头到尾的顺序分布在各个球体中。如图，为其中一种合法的一次分裂：接下来，细胞会经历二次分裂。对于每个球体，其中会含有一小段密码（注意他是有序的），我们把它看作一个十进制的数T。这个球体会被分割成T个小球体，并排成一排，之间用躯干退化成的丝状物相连接，并且质量仍然是均匀分布的，每个小球体的质量都是原球体的1/T。至此，密码已经发挥了它的作用，便消失了。如图，为二次分裂：最后，细胞会进行变异。相邻小球体之间的丝状物可能会退化掉，这两个小球体便会以相切的方式直接连接。显然，二次分裂后，除两端外的每个小球体都有两段丝状物与其连接（头尾两端的小球体只有一段丝状物与其相连）。对于每个小球体，必须至少退化一段与其相连的丝状物，否则这个结构不稳定，会继续变异。如图，为一种稳定的变异：现在，我们想知道，对于一个给定密码的细胞，总共有多少种稳定的结构。两种结构被认为相同，当且仅当他们拥有相同个数的小球体，从头到尾每个小球体的质量相同，并且从头到尾每对相邻小球体之间的连接方式相同（都是通过丝状物相连或都是通过相切直接相连）。你只需要回答这个结果 mod 1000000007即可。【输入格式】输入文件cell.in包含两行，其中：第一行为一个正整数n，表示细胞密码的长度。第二行共n个数字，为给定的细胞密码，中间没有空格。【输出格式】输出文件cell.out只包含一个整数，为细胞的种数 mod 1000000007的结果。【样例输入一】11【样例输出一】0【样例输入二】15【样例输出二】3【样例输入三】211【样例输出三】56【数据规模】对于5%的数据满足，n 6；对于25%的数据满足，n 25；对于60%的数据满足，n 100；对于70%的数据满足，n 300；对于100%的数据满足，n 1 000。营救皮卡丘【问题描述】皮卡丘被火箭队用邪恶的计谋抢走了！这三个坏家伙还给小智留下了赤果果的挑衅！为了皮卡丘，也为了正义，小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点，据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发，营救被困在N号据点的皮卡丘。为了方便起见，我们将真新镇视为0号据点，一开始K个人都在0号点。由于火箭队的重重布防，要想摧毁K号据点，必须按照顺序先摧毁1到K-1号据点，并且，如果K-1号据点没有被摧毁，由于防御的连锁性，小智一行任何一个人进入据点K，都会被发现，并产生严重后果。因此，在K-1号据点被摧毁之前，任何人是不能够经过K号据点的。为了简化问题，我们忽略战斗环节，小智一行任何一个人经过K号据点即认为K号据点被摧毁。被摧毁的据点依然是可以被经过的。K个人是可以分头行动的，只要有任何一个人在K-1号据点被摧毁之后，经过K号据点，K号据点就被摧毁了。显然的，只要N号据点被摧毁，皮卡丘就得救了。野外的道路是不安全的，因此小智一行希望在摧毁N号据点救出皮卡丘的同时，使得K个人所经过的道路的长度总和最少。请你帮助小智设计一个最佳的营救方案吧！【输入格式】输入文件rescue.in的第一行包含三个正整数N，M，K。表示一共有N+1个据点，分别从0到N编号，以及M条无向边。一开始小智一行共K个人均位于0号点。 接下来M行，每行三个非负整数，第i行的整数为Ai，Bi，Li。表示存在一条从Ai号据点到Bi号据点的长度为Li的道路。【输出格式】输出文件rescue.out仅包含一个整数S，为营救皮卡丘所需要经过的最小的道路总和。【样例输入】3 4 20 1 11 2 12 3 1000 3 1【样例输出】3【样例说明】小智和小霞一起前去营救皮卡丘。在最优方案中，小智先从真新镇前往1号点，接着前往2号据点。当小智成功摧毁2号据点之后，小霞从真新镇出发直接前往3号据点，救出皮卡丘。【数据规模】对于10%的数据满足 K = 1，且N = 3，小智将独自前去营救皮卡丘；对于20%的数据满足 K 3，且N 20，被小智单挑剿灭的火箭队加强了防御，增加了据点数；对于40%的数据满足 K 3，且N 100，面对加强的防御，小智拉来了好朋友小霞和小刚，一同前去营救；对于另外20%的数据满足任意一对据点之间均存在道路，并且对任意的0 X,Y,Z N，有不等式L(X,Z) L(X,Y) + L(Y,Z)成立；对于100%的数据满足N 150, M 20 000, 1 K 10, Li 10 000, 保证小智一行一定能够救出皮卡丘。至于为什么K 10，你可以认为最终在小智的号召下，小智，小霞，小刚，小建，小遥，小胜，小光，艾莉丝，天桐，还有去日本旅游的黑猫警长，一同前去大战火箭队。道馆之战【问题描述】口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前，冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后，到下一个冰地的楼梯才会被打开。三个冰地分别如下：l 第一个冰地l 第二个冰地l 第三个冰地当走出第三个冰地之后，就可以与馆主进行道馆战了。馆主发现这个难度太小，导致经常有挑战者能通过，为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两个房间之间均有且仅有一条路径相连，即这n个房间构成一个树状结构。每个房间分成了A和B两个区域，每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域(即若你现在在这个房间的A区域，那么你只能移动到相邻房间的A区域)或这个房间的另一区域。现在挑战者从房间u出发，馆主在房间v，那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间u的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值(即没有一种方案踩过的冰块数更多了)，那么当挑战者走到最后一个冰块上时，他会被瞬间传送到馆主面前与馆主进行道馆战。自从馆主修改规则后已经经过了m天，每天要么是有一个挑战者来进行挑战，要么就是馆主将某个房间进行了修改。对于每个来的挑战者，你需要计算出他若要和馆主进行战斗需要经过的冰块数。【输入格式】输入文件fight.in的第一行包含两个正整数n和m。第2行到第n行，每行包含两个正整数x和y，表示一条连接房间x和房间y的边。房间编号为1n。接下来n行，每行包含两个字符。第n + k行表示房间k的两个区域，第一个字符为A区域，第二个字符为B区域。其中“.”(ASCII码为46)表示是薄冰块，“#”(ASCII码为35)表示是障碍物。最后的m行，每行一个操作：l C u s：将房间u里的两个区域修改为s。l Q u v：询问挑战者在房间u，馆主在房间v时，挑战者能与馆主进行挑战需要踩的冰块数。如果房间u的两个区域都是障碍物，那么输出0。【输出格式】输出文件fight.out 包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。【样例输入】5 31 22 32 41 5.#.#.#.Q 5 3C 1 #Q 4 5【样例