全国赛2008年浙江省省选第二试

1、2008 年浙江省省选第二试竞赛时间：2008 年 6 月 13 日上午 8:00 12:00提交源程序须加后缀：对于Pascal 语言party.pastowasmovement.pasknight.pas对于C语言party.ctower.cmovement.cknight.c对于C+语言party.cpptower.cppmovement.cppknight.cpp题目名称生日聚会瞭望塔无序运动骑士程序文件名partytowermovementknight输入文件名party.ower.ovement.inknight.in输出文件名party.outtower.outmovement.

2、outknight.out每个测试点时限1 sec2 sec3 sec2 sec测试点数目10101010每个测试点分值10101010生日聚会【问题描述】是 hidadz 小朋友的生日，她邀请了许多朋友来参加生日 party。不至于无聊，就hidadz 带着朋友们来到花园中，打算坐成一排玩座的方案应满足如下条件：。为了对于任意连续的一段，男孩与的数目之差不超过 k。很快，小朋友便找到了案坐了下来开始。hidadz 的好朋友 Susie发现，这样的就座方案其实是很多的，所以大家很快就找到了一种，那么到底有多少种呢？热爱数学的hidadz 和朋友们开始思考这个问题假设参加party 的人有n 个

3、男孩与m 个，你是否能解答Susie 和hidadz的疑问呢？由于这个数目可能很多，他们只想知道这个数目除以 12345678 的余数。【输入文件】输入文件 party.in 仅包含一行共 3 个整数，分别为男孩数目 n,常数 k。数目 m,【输出文件】输出文件party.out 应包含一行，为题中要求的。【输入样例】1 2 1【输出样例】1【数据规模】对于 30%的数据，n , m 20；对于 100%的数据, n , m 150，k 20。瞭望塔【问题描述】致力于建设示范和谐小村庄的H 村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。H 村抽象为一维的轮廓。如下图所示可以

4、用一条山的上方轮廓折线(x1, y1), (x2, y2), . (xn, yn)来描述H 村的形状，这里 x1 x2 xn。瞭望塔可以建造在x1, xn间的任意位置,但必须满足从瞭望塔的顶端可以看到 H 村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi 村长希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi 村长计算塔的最小高度。【输入文件】输入文件 tower.in 第一行包含一个整数 n，表示轮廓折线的节点数目。接下来第一行 n 个整数,为 x1 xn. 第三行 n 个整数，为 y1 yn。【输出文件】输出文件tower.out 仅包

5、含一个实数，为塔的最小高度，精确到小数点后三位。【输入样例一】61 2 4 5 6 71 2 2 4 2 1【输出样例一】1.000【输入样例二】410 20 49 590 10 10 0【输出样例二】14.500【数据规模】对于 60%的数据， N 60；对于 100%的数据， N 300，输入坐标绝对值不超过 106，注意考虑实数误差带来的问题。无序运动【问题描述】D 博士对物理有着深入的，经典物理、天体物理、量子物理都有着以他的名字命名的定理。最近 D 博士着迷于粒子运动的无规则性。对深信不疑的他相信，上帝创造的任何事物必然是有序的、有理可循的，而不是无规则的、混沌的。经过长时间的，D

6、博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。定义一个粒子的轨迹为二维平面上的一个点列（P1, P2, 为清楚起见，PN）。点列 P 的一个子列i, j定义为P 中一段连续的子序列（Pi, Pi+1, Pj）。点列 P 的一个子列u, v被称为点列Q = (Q1, Q2 Qv-u+1)在P 中的一次出现，当且仅当Q 经过有限次的平移、旋转、翻转、放缩之后得到 Q满足Qk = Pu+k-1（k = 1 u v + 1）。对平面X-Y 进行四种操作的解释平移设平移向量为(dx,

7、 dy)，则任意点(x,y)平移后的结果为(x+dx, y+dy)旋转设旋转角为t，则任意点(x,y)旋转后的结果为 (x cos t y s, x s+ y cos t)翻转任意点(x,y) 翻转后的结果为(x, -y)放缩设放缩比例为p (p 0)，则任意点(x,y)放缩后的结果为(px, py)【输入文件】输入文件 movement.in 第一行两个整数 N、M，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。接下来 M 行依次给出每个轨迹片断。每行先是一个正整数 K，表示该轨迹片断点列的长度。然后 2K 个整数，依次描述点列中的 K 个点的横坐标与纵坐标。接下来一行 2

8、N 个整数，依次描述待处理的粒子运动轨迹的点列中 N 个点的横坐标与纵坐标。注：输入中的每条轨迹中任意相邻两点不会相同。【输出文件】输出文件 movement.out 应包含 M 行，依次给出每个片段在待处理运动轨迹中的出现次数。【输入样例】3 221 -10 0 1 0 1 1【输出样例】21【数据规模】对于 30%的测试数据，N, M, K 100，片段总长度 500;对于 50%的测试数据，N, M, K 1 000，片段总长度 5 000;对于 100%的测试数据，满足 N, K 200 000，片段总长度 200 000，输入中给出所有点坐标绝对值均不大于 10 000。骑士【问题描

9、述】Z 国的骑士团是一个很有的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y 国发动了一场针对Z 国的。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶的能力的，但是骑士们互相之间往往有一些。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛 盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。骑士按照 1 至 N为了描述战斗力，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。【输入文件】输入文件knight.in 第一行包含一个正整数 N，描述骑士团的人数。接下来 N 行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。【输出文件】输出文件 knight.out 应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。