NOIP2013提高组复赛试题day1+day2

《NOIP2013提高组复赛试题day1+day2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国信息学奥林匹克联赛（NOIP2013）复赛提高组day1CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组day1第0页共4页全国信息学奥林匹克联赛（NOIP2013）复赛提高组day21．转圈游戏(circle.cpp/c/pas)【问题描述】n个小伙伴（编号从0到n-1）围坐一圈玩游戏。按照顺时针方向给n个位置编号，从0到n-1。最初，第0号小伙伴在第0号位置，第1号小伙伴在第1号位置，……，依此类推。游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m号位置，第1号位置小伙伴走到第m+1号位置，……，依此类推，第n−m号位置上的小伙伴走到第0号位置，第n-m+1号位置上的

2、小伙伴走到第1号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。现在，一共进行了10k轮，请问x号小伙伴最后走到了第几号位置。【输入】输入文件名为circle.in。输入共1行，包含4个整数n、m、k、x，每两个整数之间用一个空格隔开。【输出】输出文件名为circle.out。输出共1行，包含1个整数，表示10k轮后x号小伙伴所在的位置编号。【输入输出样例】circle.incircle.out103455【数据说明】对于30%的数据，0

3、队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有n根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中ai表示第一列火柴中第i个火柴的高度，bi表示第二列火柴中第i个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对99,999,997取模的结果。【输入】输入文件为match.in。共三行，第一行包含一个整数n，表示每盒中火柴的数目。第二行有n个整数，每两个整数之间用一个空格

4、隔开，表示第一列火柴的高度。第三行有n个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。第5页共5页全国信息学奥林匹克联赛（NOIP2013）复赛提高组day2【输出】输出文件为match.out。输出共一行，包含一个整数，表示最少交换次数对99,999,997取模的结果。【输入输出样例1】match.inmatch.out4231432141【输入输出样例说明】最小距离是0，最少需要交换1次，比如：交换第1列的前2根火柴或者交换第2列的前2根火柴。【输入输出样例2】match.inmatch.out4134217242【输入输出样例说明】最小距离是10，最少需要交换2次，比如：交

5、换第1列的中间2根火柴的位置，再交换第2列中后2根火柴的位置。【数据范围】对于10%的数据，1≤n≤10；对于30%的数据，1≤n≤100；对于60%的数据，1≤n≤1,000；对于100%的数据，1≤n≤100,000，0≤火柴高度≤231−1。3．货车运输(truck.cpp/c/pas)【问题描述】A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。【输入】输入文件名为truck.in。输入文件第一行有两个用一个空格隔开的整数n，m，表示A国有n座城市和m

6、条道路。接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x不等于y，两座城市之间可能有多条道路。接下来一行有一个整数q，表示有q辆货车需要运货。接下来q行，每行两个整数x、y，之间用一个空格隔开，表示一辆货车需要从x城市运输货物到y城市，注意：x不等于y。【输出】输出文件名为truck.out。输出共有q行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。【输入输出样例】第5页共5页全国信息学奥林匹克联赛（NOIP2013）复赛提高组day2truck.intruck.out43312

7、4-123333113131413【数据说明】对于30%的数据，0