全国信息学奥林匹克联赛（NOIP2013）复赛 提高组 day1答案及解析.pdfVIP

一、实操题

1、转圈游戏

【问题描述】

n个小伙伴（编号从0到n-1）围坐一圈玩游戏。按照顺时针方向给n

个位置编号，从0到n-1。最初，第0号小伙伴在第0号位置，第1号小伙伴在第

1号位置，……，依此类推。

游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m号位置，第1

号位置小伙伴走到第m+1号位置，……，依此类推，第n−

m号位置上的小伙伴走到第0号位置，第n-m+1号位置上的小伙伴走到第1

号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。

现在，一共进行了10k轮，请问x号小伙伴最后走到了第几号位置。

【输入】

输入文件名为circle.in。

输入共1行，包含4个整数n、m、k、x，每两个整数之间用一个空格隔开。

【输出】

输出文件名为circle.out。

输出共1行，包含1个整数，表示10k轮后x号小伙伴所在的位置编号。

【输入输出样例】

【数据说明】

对于30%的数据，0k7；

对于80%的数据，0k10^7；

对于100%的数据，1n1,000,000，0mn，1≤x≤n，0k10^9。

参考答案：对于此题，我们需要模拟每一轮小伙伴的移动，然后计算10k轮后x号小

伙伴所在的位置编号。由于小伙伴的编号和位置编号都是从0开始的，我们可以使

用取模运算来简化计算。具体步骤如下：1.

初始化变量pos为x，表示x号小伙伴当前所在的位置。2.

对于每一轮（共10k轮），计算小伙伴移动后的新位置：-

对于第i号小伙伴（i从0到n-1），计算其应该走到的位置j=(i+m-1)%n。-

更新pos为j，表示x号小伙伴移动后的新位置。3.

输出pos，即为10k轮后x号小伙伴所在的位置编号。

解析：【喵呜刷题小喵解析】：

此题是一个经典的数学问题，涉及到模运算和周期性。由于小伙伴的编号和位置编

号都是从0开始的，每一轮小伙伴的移动可以通过取模运算来简化计算。

具体来说，每一轮小伙伴的移动可以看作是一个循环的过程，即小伙伴按照顺时针

方向走到一个新的位置，这个位置可以通过取模运算得到。具体来说，对于第i号

小伙伴，其应该走到的位置j可以通过以下公式计算：

j=(i+m-1)%n

其中，i表示小伙伴的编号，m表示每一轮小伙伴移动的步数，n表示小伙伴的总数

。由于小伙伴的编号和位置编号都是从0开始的，所以需要进行取模运算，以保证

位置编号在0到n-1的范围内。

因此，我们可以通过模拟每一轮小伙伴的移动，然后计算10k轮后x号小伙伴所在的

位置编号。具体实现时，我们可以使用一个变量pos来记录x号小伙伴当前所在的位

置，然后对于每一轮，更新pos为小伙伴移动后的新位置，最后输出pos即可。

需要注意的是，由于小伙伴的总数n可能非常大，如果直接模拟每一轮小伙伴的移

动，时间复杂度可能会非常高。因此，在实际实现时，我们需要优化算法，尽可能

减少计算量。一种可能的优化方法是在每一轮中，只更新x号小伙伴的位置，而不

是更新所有小伙伴的位置。这样可以大大减少计算量，提高算法的效率。

2、火柴排队

【问题描述】

涵涵有两盒火柴，每盒装有n

根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴

的高度互不相同，两列火柴之间的距离定义为：

其中ai表示第一列火柴中第i个火柴的高度，bi表示第二列火柴中第

i个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距

离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请

输出这个最小交换次数对99,999,997取模的结果。

【输入】

输入文件为match.in。

共三行，第一行包含一个整数n，表示每盒中火柴的数目。

第二行有n个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有n个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

【输出】

输出文件为match.out。

输出共一行，包含一个整数，表示最少交换次数对99,999,997取模的结果。

【输入输出样例1】

【输入输出样例说明】

最小距离是0，最少需要交换1次，比如：交换第1列的前2根火柴或者交换第2

列的