历年题目训练problemset

1、ljs_yali2017 年 9 月 5 日时间：3.5 小时提交程序文件名编译选项对于 C+ 语言-lm,-O2-lm,-O2-lm,-O2对于 C 语言-lm,-O2-lm,-O2-lm,-O2对于 Pascal 语言-lm,-O2-lm,-O2-lm,-O2对于 C+ 语言problem.cpptracks.cppballmachine.cpp对于 C 语言problem.ctracks.cballmachine.c对于 Pascal 语言problem.pastracks.pasballmachine.pas题目名称序列问题雪地行踪发球机器题目类型传统型传统型传统型目录problemt

2、racksballmachine输入文件名problem.racks.inballmachine.in输出文件名problem.outtracks.outballmachine.out每个测试点时限1.0s2.0s1.0s内存限制512MB512MB128MB测试点数目102025每个测试点分值1054序列问题(problem.cpp/c/pas)【问题描述】Brunhilda 十分喜欢序列, 她喜欢观察序列的性质。现在 Brunhilda 手上有 n 个不同的数, 于是她尝试将这 n 个数字填到长为 n 的序列 A 中。在她看来当序列 A 的第 i 位上数字在原来 n 个数中恰好是第 i 大

3、时,i 号位置就是稳定的。并且, 当序列中恰好有 m 个位置是稳定时, 她的开心度就会加 1。那么, 她想知道, 她的开心度最大可能是多少。由于 Brunhilda 的开心度可能会很大，所以你只要输出开心度除以 1000000007 的余数。【输入格式】从文件 problem.in 中读入数据。输入文件第一行包括一个整数 T , 表示数据组数。接下来 T 行, 每行两个整数, 表示 N 和 M 。【输出格式】输出到文件 problem.out 中。输出文件包括 T 行, 每行一个整数, 表示 Brunhilda 最大的开心度。【样例输入】51 02 15 2100 5010000 5000【样

4、例输出】0第 2 页, 共 10 页02057802888760695423【提示】 1 mod p, 其中 p 为质数,x 1, p)。xp1【子任务】对于 100% 的数据满足1 N 106, 0 M N 106。每个测试点还满足如下约束：第 3 页, 共 10 页测试点编号NMT1 5 5= 12 8 8= 5 1053 10 10= 14 2000= 0= 5 1055 106= 16 3000 3000= 5 1057= 18 106 106= 5 1059= 110= 5 105雪地行踪(tracks.cpp/c/pas)【问题描述】森林里有一块矩形的草地, 大雪刚至, 草地如盖上

5、了洁白的毛毯一般。四处望去一片渺茫, 没有植物, 没有生机。住在森林里的若干只小兔 (R) 和狐狸 (F) 正在经过这片草地, 当然, 草地上也留下了它们的足迹。“这个是小兔的。” “那些是狐狸们的吧！”兔子和狐狸总是从草地的左上角进入, 并从右下角离开。在草地中时, 它们可能会来回的走动甚至经过自己的足迹。任何时候, 草地上最多只能有 1 只动物, 每只动物只会经过草地一次。每只动物的行踪可以通过将矩形草地分成若干小格来进行描述。小动物们不会斜着走或跳过一小格来到下一格。当一个小动物经过草地时, 它会把在它之前的所有足迹全部覆盖。例如, 一开始一只小兔从左上角穿过草地到达右下角（如中图）。在

6、这之后, 一只狐狸也来到了草地, 并且将小兔的一部分足迹覆盖了（如右图）。.RRR.RRR.R.RRRR.R.RRRFFR.FRRR.FF.RRRFFR.一段时间后, 你拥有了这个草地的地图, 地图上显示着每一格是否有足迹并且那些足迹分别是由小兔还是狐狸留下的。你对当地的野生动物数量十分感兴趣。现在, 请你写一个程序尝试得出最少需要 N 只动物穿过草地才可以在雪地中留下这样的行踪。第 4 页, 共 10 页【输入格式】从文件 tracks.in 中读入数据。输入文件的第一行包含两个整数 H 和 W , 分别表示草地地图的长和宽。接下来 H 行每行 W 个字符描述这个地图：.表示没有被留下印记的

7、空白雪地,R表示一格中小兔的足迹留在了最上面,F表示狐狸的足迹留在了最上面。地图中至少有一个足迹。【输出格式】输出到文件 tracks.out 中。输出包含一个整数, 表示可以满足输入中行踪的最少的动物数 N 1。【样例输入】 5 8 FFR.FRRR.FF.RRRFFR.【样例输出】2【子任务】对于 100% 的数据,1 H, W 4000。每个测试点还满足如下约束：第 5 页, 共 10 页第页, 共 10 页测试点编号HW特殊性质1 10 10地图全为 R 或 F2N 23N 34 4000 40005 20 20N 567 500 500N 2008910 4000 4000N 101

8、1 10 4000N 300012 4000 15N 600013 4000 4000N 30014无15发球机器(ballmachine.cpp/c/pas)【问题描述】有一个可看成有根树的发球机器, 树上的节点被编号成 1 N , 每个节点为空或包含一个球。初始时, 所有的节点都是空的。当机器运行时, 它可以支持如下的两种操作：1. 向发球机器中添加 k 个球：球被一个一个分别放在了根节点。只要有一个空节点在球的下方, 它就会滚下去。如果一个点有多个空的子节点, 机器会选择将球向其子树中最小节点最小的节点滚下去。因此, 如果一个球会掉下多层, 那么机器会在每一层都作出决定。例如：如果我们向

9、下图的根节点放置两个球, 它们会停在 1 和 3 号节点：第一个球会从 4 号点滚向 3 号点因为 3 号点是空的并且它拥有 1 号点在其子树中；然后它会滚向 1 号节点。第二个球从 4 号点滚向 3 号点然后停在那里。2. 从一个特定的节点移除一个球：这个节点将会变空, 并且它上面的所有节点上的球都会顺次掉下来 (如果有的话)。如果我们如下图依次从发球机器中移除 5,7 和 8 号节点的球,1,2 和 3 号节点将会变空。第 7 页, 共 10 页【输入格式】从文件 ballmachine.in 中读入数据。输入的第一行包含两个整数 N 和 Q, 分别表示这棵树的节点个数和操作的总个数。接下

10、来的 N 行描述这个发球机器。每一行包含一个描述该节点的整数：第 i 行是 i 号节点的父亲节点, 如果 i 号节点是根节点, 则该数会是 0。接下来的 Q 行每行包含两个整数描述一次操作。其中 1 k 表示 1 号操作,k 表示需要将 k 个球放入发球机器。2 x 表示 2 号操作,x 表示被移除的球所在的节点编号。数据保证所有的操作都是合法的, 即：操作不会要求加入多于当前空节点数的球, 也不会从一个空节点移除一个球。【输出格式】输出到文件 ballmachine.out 中。对于操作 1, 输出一个整数表示最后一个加入发球机器的球停在了哪里。对于操作 2, 输出一个整数表示在移除当前节点的球后会有多少个球掉落。【样例输入 1】2 5011 22 11 12 21 1【样例输出 1】10111第 8 页, 共 10 页【样例输入 2】8 401223346【样例输出】22【子任务】对于 100% 的数据,1 N, Q 105。每个测试点还满足如下约束：第 9 页, 共 10 页第 10 页, 共 10 页测试点编号NQ特殊性质1 2 2无2 300 300345= 1023= 500每