NOIP历年复赛提高组试题(2004-2013)

【最新整理，下载后即可编辑】NOIP提高组初赛历年试题及答案求解题篇问题求解题（每次2题，每题5分，共计10分。

每题全部答对得5分，没有部分分）注：答案在文末提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。

NOIP2011-1．平面图可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。

4个顶点的平面图至少有6条边，如图所示。

那么，5个顶点的平面图至多有_________条边。

NOIP2011-2．定义一种字符串操作，一次可以将其中一个元素移到任意位置。

举例说明，对于字符串“BCA”可以将A移到B 之前，变字符串“ABC”。

如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。

NOIP2012-1. 本题中，我们约定布尔表达式只能包含p,q, r三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。

如果无论p, q,r如何取值，两个布尔表达式的值总是相同，则称它们等价。

例如，(p∨q)∨r和p∨(q∨r)等价，p∨¬p 和q∨¬q 也等价；而p∨q 和p∧q不等价。

那么，两两不等价的布尔表达式最多有_________个。

NOIP2012-2. 对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。

例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。

那么，图3有_________个不同的独立集。

NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。

密码是n个数s1,s2,…,sn，均为0或1。

该系统每次随机生成n个数a1,a2,…,an，均为0或1，请用户回答(s1a1+s2a2+…+snan)除以2的余数。

如果多次的回答总是正确，即认为掌握密码。

该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

CCF 全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day11．转圈游戏(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 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

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

【输入】输入文件名为circle.in。

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

【输出】输出文件名为c ircle.out。

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

【输入输出样例】circle.in circle.out10 3 4 5 5【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

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

第一题题库NOIP20071．统计数字(count.pas/c/cpp)【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。

已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【输入】输入文件count.in包含n+1行：第1行是整数n，表示自然数的个数。

第2~n+1行每行一个自然数。

【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

【输入输出样例】【限制】40%的数据满足：1<=n <=100080%的数据满足：1<=n <=50000100%的数据满足：1<=n <=200000，每个数均不超过1 500 000 000（1.5*109）NOIP20081. 笨小猴(wird.pas/c/cpp)【问题描述】笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。

但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn 是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn 是一个质数，那么笨小猴就认为这是个Lucky Word ，这样的单词很可能就是正确的答案。

【输入】输入文件word.in 只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。

【输出】输出文件word.out 共两行，第一行是一个字符串，假设输入的的单词是Lucky Word ，那么输出“Lucky Word ”，否则输出“No Answer ”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn 的值，否则输出0。

第十届信息学奥林匹克联赛复赛试题（NOIP2004）一、津津的储蓄计划(save.pas/c/cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580二、合并果子(fruit.pas/c/cpp)【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。

程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。

因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。

1、分层读：高层入手，逐层深入，正确理解程序。

2、写注解：固化、总结、提炼已有的理解成果。

3、先模拟：根据代码顺序跟踪变量，模拟运算。

4、找规律：先模拟几次循环后，找出背后的规律。

5、看功能：从代码结构和运算结果判断程序功能。

6、猜算法：有时不知道算法，通过结构和函数猜一猜。

7、换方法：了解程序本质后，换一个熟悉的方法试试。

对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。

其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。

阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。

如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。

当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。

祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#include <iostream>#include <cstring>using namespace std;const int SIZE = 100;int main(){int n,i,sum,x,a[SIZE];cin>>n;memset(a,0,sizeof(a));for(i=1;i<=n;i++){cin>>x;a[x]++;}i=0;sum=0;while(sum<(n/2+1)){i++;sum+=a[i];}cout<<i<<endl;return 0;}输入：114 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#include <iostream> using namespace std; int n;void f2(int x,int y); void f1(int x,int y) {if(x<n)f2(y,x+y);}void f2(int x,int y) {cout<<x<<' ';f1(y,x+y);}int main(){cin>>n;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include <iostream>using namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(len>ans)ans=len;for(i=1;i<=n;i++)if( (!visited[i]) &&(e[x][i]!=-1) ) dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++)e[i][j]=-1;for(i=1;i<=m;i++){cin>>a>>b>>c;e[a][b]=c;e[b][a]=c;}for(i=1;i<=n;i++)visited[i]=false;ans=0;for(i=1;i<=n;i++)dfs(i,0);cout<<ans<<endl;return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。

历年真题：2004年第十届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言 二小时完成 ）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●一、 单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案.）。

1. 设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f,g}，那么集合)(~)(B C B A ⋂⋃-为（ ）。

A. {a, b, c, d}B. {a, b, d, e}C. {b, d, e}D. {b, c, d, e}E. {d, f, g} //注意顺序，没有难度了选a2. 由3个a ，5个b 和2个c 构成的所有字符串中，包含子串“abc ”的共有（ ）个。

A. 40320B. 39600C. 840D. 780E. 60//1abc,2a,4b,1c →8！/（2！*4！*1！*1！*1！）=840-2abc,3b,1a →6!/(2!*3!*1!)=60 选d3.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。

已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。

假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。

A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 3, 5, 4, 6D. 1, 3, 5, 6, 7E. 1, 3, 6, 5, 7//栈操作，显然是e4. 满二叉树的叶结点个数为N ，则它的结点总数为（ ）。

A. NB. 2 * NC. 2 * N – 1D. 2 * N + 1E. 2N– 1//需要知道满二叉树的概念，画图就可知道，选c5. 二叉树T ，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。

第十届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案.）。

1.设全集I = {a, b, c, d, e, f, g}，集合A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合BA⋂⋃-为（）。

C)(~)(BA. {a, b, c, d}B. {a, b, d, e}C. {b, d, e}D. {b, c, d, e}E. {d, f, g}2.由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。

A. 40320B. 39600C. 840D. 780E. 603.某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。

已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。

假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。

A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 3, 5, 4, 6D. 1, 3, 5, 6, 7E. 1, 3, 6, 5, 74.满二叉树的叶结点个数为N，则它的结点总数为（）。

A. NB. 2 * NC. 2 * N – 1D. 2 * N + 1E. 2N– 15.二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（）。

A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 4 2 7 5 3 6 1D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 16.十进制数100.625等值于二进制数（）。

A. 1001100.101B. 1100100.101C. 1100100.011D. 1001100.11E. 1001100.017.下面哪个部件对于个人桌面电脑的正常运行不是必需的（）。

CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day1（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+，2.71GHz，内存2G，上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、特别提醒：评测在NOI Linux下进行。

1．转圈游戏(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号位置上的小伙伴走到第1号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。

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

【输入】输入文件名为circle.in 。

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

【输出】输出文件名为circle.out 。

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

【输入输出样例】【数据说明】对于30%的数据，0<k <7； 对于80%的数据，0<k <107；对于100%的数据，1<n <1,000,000，0<m <n ，0≤x <n ，0<k <109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有n 根火柴，每根火柴都有一个高度。

第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

全国信息学奥林匹克联赛（2014）复赛提高组11．生活大爆炸版石头剪刀布()【问题描述】石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。

如果两个人出拳一样，则不分胜负。

在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：斯波克：《星际迷航》主角之一。

蜥蜴人：《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。

现在，小A和小B尝试玩这种升级版的猜拳游戏。

已知他们的出拳都是有周期性规律的，但周期长度不一定相等。

例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……”已知小A和小B一共进行N次猜拳。

每一次赢的人得1分，输的得0分；平局两人都得0分。

现请你统计N次猜拳结束之后两人的得分。

【输入】输入文件名为。

第一行包含三个整数：N，，，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。

数与数之间以一个空格分隔。

第二行包含个整数，表示小A出拳的规律，第三行包含个整数，表示小B出拳的规律。

其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”，4表示“斯波克”。

数与数之间以一个空格分隔。

【输出】输出文件名为。

输出一行，包含两个整数，以一个空格分隔，分别表示小A、小B的得分。

【输入输出样例1】【输入输出样例2】【数据说明】对于100%的数据，0 < N ≤200，0 < ≤200，0< ≤200。

2．联合权值()【问题描述】无向连通图G有n个点，1条边。

点从1到n依次编号，编号为i的点的权值为，每条边的长度均为1。

N O I’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。

N-1），N1数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。

<3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，82个。

例如n=2时的比赛安排：队 1 2 3 4比赛 1==2 3==4 一天1==3 2==4 二天1==4 2==3 三天2．数制转换（20分）设有一个字符串A$的结构为：A$=’m<n>p’其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。

程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。

例如：A$=’48<10>8’其意义为：将10进制数48，转换成8进制数输出。

输出结果为：48<10>=60<8>4．挖地雷（30分）在一个地图上有N 个地窖（N<=20），每个地窖中埋有一定数量的地雷。

同时，给出地窖之间的连接路径。

[题目要求] 当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接，当设计一（表示1g 砝码有a1个，2g 砝码有a2个，…，20g 砝码有a6个）输出方式：Total=N（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格）输出：TOTAL=3 表示可以称出1g ，2g ，3g 三种不同的重量。

CCF 全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day11．转圈游戏(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 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

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

【输入】输入文件名为circle.in。

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

【输出】输出文件名为c ircle.out。

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

【数据说明】对于30%的数据，0 < k < 7；对于80%的数据，0 < k < 107；对于100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队(match.cpp/c/pas)【问题描述】涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。

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

请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组 day2（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU AMD Athlon(tm) 64x2 Dual Core CPU 5200+，2.71GHz，内存2G，上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、特别提醒：评测在NOI Linux下进行。

1．积木大赛(block.cpp/c/pas)【题目描述】春春幼儿园举办了一年一度的“积木大赛”。

今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是ℎi。

在搭建开始之前，没有任何积木（可以看成n块高度为0的积木）。

接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块到第R块之间（含第L块和第R块）所有积木的高度分别增加1。

小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。

但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。

【输入】输入文件为block.in输入包含两行，第一行包含一个整数n，表示大厦的宽度。

第二行包含n个整数，第i个整数为ℎi。

【输出】输出文件为block.out仅一行，即建造所需的最少操作数。

【样例解释】其中一种可行的最佳方案，依次选择[1,5] [1,3] [2,3] [3,3] [5,5]【数据范围】对于30%的数据，有1≤n≤10；对于70%的数据，有1≤n≤1000；对于100%的数据，有1≤n≤100000，0≤ℎi≤10000。

(flower.cpp/c/pas)【问题描述】花匠栋栋种了一排花，每株花都有自己的高度。

花儿越长越大，也越来越挤。

全国信息学奥林匹克联赛（2013）复赛提高组 11．转圈游戏()【问题描述】n 个小伙伴（编号从 0 到 1）围坐一圈玩游戏。

按照顺时针方向给 n 个位置编号，从 0 到 1。

最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第m 号位置，第 1 号位置小伙伴走到第 1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第1 号位置上的小伙伴走到第 1 号位置，……，第 1 号位置上的小伙伴顺时针走到第1 号位置。

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

【输入】输入文件名为。

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

【输出】输出文件名为。

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

【输入输出样例】10 3 4 5 5【数据说明】对于 30%的数据，0 < k < 7；对于 80%的数据，0 < k < 107；对于 100%的数据，1 < n< 1,000,000，0 <m <n ，0 ≤ x ≤ n，0 < k< 109。

2．火柴排队()【问题描述】涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。

现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中表示第一列火柴中第 i 个火柴的高度，表示第二列火柴中第 i 个火柴的高度。

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

请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对99,999,997 取模的结果。

【输入】输入文件为。

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