冲刺NOIP2012模拟试题（十一）

习题

1. 2. 3. 4.

骰子 ......................................................................................................................................... 2 约数和 ..................................................................................................................................... 4 旅行 ......................................................................................................................................... 5 逆序统计 ................................................................................................................................. 5

骰子

【源程序名】 dice.pas 【输入文件】 dice.in 【输出文件】 dice.out 【问题描述】

让我们一起来看下，一个放在桌面上的骰子，如图1所示：

初期配置 North（北） West（西） East（东） South（南） 图1 初始方位 数字1在上方，数字2在South(南)方位，数字3在East（东）方位。每一对相反方向

的数字之和是7，按照上述规则，数字5在North（北）方位，数字4在West（西）方位，数字6在下方，如图1所示，数字4，5，6在图1中是看不到的。

骰子的初始位置如图1所示，按照下列6条规则旋转骰子，规则如图2和图3所示：

操作：North 操作：North 操作：East 操作：West 操作：South 图2：旋转规则North（北）、East（东）、West（西）、South（南）

图2中所示的4条旋转规则是将骰子按照指定的方位旋转90度。

操作：Right 操作：Left 图3：旋转规则Left（左）、Right（右）

图3中所示的4条旋转规则是将骰子沿水平方向分别向Left或Right方位旋转90度。

你的任务是编写一个程序，从图1所示的方位开始，根据给定的一系列规则连续的旋转骰子，程序要求输出旋转骰子过程中位于上方的数字之和（包括图1所示的初始方位上方的数字1）。 【输入】

第一行输入一个整数n（n≤1000），表示执行旋转的总步数。 第2~n+1行分别输入6条旋转规则中6个方位中的一个。 【输出】

最后一行输出旋转过程中位于骰子上方的数字之和。 【样例输入输出】

dice.in 5 North North East South West 8 West North Left South Right North Left East

约数和

【源程序名】 factor .pas 【输入文件】 factor .in 【输出文件】 factor .out 【问题描述】

给你一个数N，需要你算出这个数所有约数的和。（N的约数指能整除N的正整数），例如12的约数有1，2，3，4，6，12.所有约数和为1+2+3+4+6+12=28。 【输入】

本题有多组数据，第一行一个T，表示有T组数据；下面T行，每行一个正整数N，表示要处理的数。 【输出】

T行，每行一个正整数，表示输入中对应的数的约数和。 【样例输入输出】 factor.in factor.out 1 28 12 【数据范围】 对于20%的数据，T=1。 对于50%的数据，T≤5000。 对于80%的数据，T≤50000。

对于100%的数据，T≤50000；N≤5000000。 最后两个点时限1.5秒。

dice.out 21 34 旅行

【源程序名】 j5 .pas 【输入文件】 j5 .in 【输出文件】 j5 .out 【问题描述】

你要进行一个行程为7000KM的旅行，现在沿途有些汽车旅馆，为了安全起见，每天晚上都不开车，住在汽车旅馆，你手里现在已经有一个旅馆列表，用离起点的距离来标识，如下：

0， 990， 1010， 1970， 2030， 2940， 3060 3930， 4060， 4970， 5030， 5990， 6010， 7000

但在出发之前可能还要增加一些旅馆。

现在旅行社为了节约成本，要求每天至少行驶A公里，国家旅行社为了安全起见，要求每天最多只能行驶B公里。

你想知道一共有多少种旅行方案。 【输入】

第一行输入A，第二行输入B，第三行输入N（0≤N≤20），表示在出发之前又新增N个汽车旅馆；接下来N行，每行一个整数m，表示旅馆离起点的距离（0

输出一共有多少种旅行方案。

逆序统计

【源程序名】 count .pas 【输入文件】 count .in 【输出文件】 count .out 【问题描述】

我们说（i，j）是a1，a2，…，aN的一个逆序对当且仅当ia j。例如2，4，1，3，5的逆序对有3个，分别为（1，3），（2，3），（2，4）。现在已知N和K，求1…N的所有特定排列，这些排列的逆序对的数量恰好为K。输出这些特定排列的数量。

例如N=5，K=3的时候，满足条件的排列有15个，它们是：

1，2，5，4，3 1，3，4，5，2 1，3，5，2，4 1，4，2，5，3 1，4，3，2，5 1，5，2，3，4 2，1，4，5，3 2，1，5，3，4 2，3，1，5，4 2，3，4，1，5 2，4，1，3，5 3，1，2，5，4 3，1，4，2，5 3，2，1，4，5 4，1，2，3，5 【输入】

从文件count.in输入。输入第一行有两个整数N和K。（N≤100，K≤N*(N-1)/2） 【输出】

将1…N的逆序对数量为K的特定排列的数量输出到文件count.out。为了避免高精度计算，请将结果mod 10000以后再输出！ 【样例输入输出】 count.in count.out 样例1 5 3 15 样例2 10 7 4489 样例3 10 10 1670

本文来源：https://www.bwwdw.com/article/up8x.html