NOIP提高组初赛历年试题及答案完善题篇

NOIP 提高组初赛历年试题及答案提高组初赛历年试题及答案 （完善题篇完善题篇） 完善程序，每年两题，每题每空完善程序，每年两题，每题每空 2-4 分，共分，共 28 分。分。 【数学题目】【数学题目】 1、变量赋初值，如果以后用到的是加减运算，则赋初值 0；如果以后用到的是 乘除运算，则赋初值为 1。 2、循环条件的填空，分析表达式的规律，看表达式中的最后一项的值是否到了 第 m 项或者是第 n 项，如果到了，则在循环中的第二个表达式中用到的是 i=。 3、循环条件中如果用的是 while 语句，则循环变量的初值应该在 while 的外面 定义和赋初值，在循环语句中必须给变量自加或者是自减，即 i+或 i-。 【字符串题目】【字符串题目】 1、把一个数字字符转变成对应的数值的格式是：ch=1-0;把大写字母转变为小 写字母的格式：c h=c h+32 ;把小写字母转变为大写字母的格式为：ch=ch-32 。 2、区分好字符数组中的指针和指针所指的值的关系。在循环语句中，当指针往 后走一个位置的时候，用的是指针的自加，而不是指针所指的值的自加。 【结构体题目】【结构体题目】 1、注意定义结构体变量时的格式。 2、结构体中成员的调用格式。结构体中的成员分为多种类型，调用结构体中的 成员，使用的是“.”或者是“”运算符。 3、如果返回的是结构体的话，函数的返回类型必须是结构体类型。调用函数的 格式中，调用的若是结构体数组，则只用写结构体数组名。 【函数题目】【函数题目】 1、看函数的返回类型，函数的返回类型必须和 return 语句返回的表达式的类型 一致。 2、函数的调用的情况，函数调用时只用写函数的名称，以及函数的参数。如： f1(x)和 f2(x,y)。 【数组题目】【数组题目】 1、求一个数值数组中的所有值的平均值和把大于或者小于平均值的数放到另外 一个数组中。首先定义一个变量来存放平均值，如果变量 avg 已经定义但是没 有赋初值，那么这个空填写的内容的为：avg =0; 2、 求平均值时有两种方法， 如果在 for 语句的后面有 avg=avg /N;则第二个空一 般的填写时 avg+=si;如果说没有 avg=avg /N;则填写的是：avg +=si/N。 3、二维数组遍历时，使用的是两个循环，使用的是循环的嵌套使用，第二个循 环填写的内容为：j=0。 NOIP2011-1. 大整数开方（同普及组 2011-2） 输入一个正整数 n ( 1 n10100)，试用二分法计算它的平方根的整数部分。 #include #include using namespace std; const int SIZE=200; struct hugeint int len,numSIZE; ; / 其中 len 表示大整数的位数; num1 表示个位，num2 表示十位，以此类推 hugeint times(hugeint a,hugeint b) / 计算大整数 a 和 b 的乘积 int i,j; hugeint ans; memset(ans.num,0,sizeof(ans.num); for(i=1;i=a.len;i+) for(j=1;jb.len) ans.len=a.len; else ans.len=b.len; for(i=1;i0) ans.len+; return ans; hugeint average(hugeint a,hugeint b) / 计算大整数 a 和 b 的平均数的整数部分 int i; hugeint ans; ans=add(a,b); for(i=ans.len;i=2;i-) ans.numi-1+=(ans.numi % 2)*10; ans.numi/=2; ans.num1/=2; if(ans.numans.len=0) ans.len-; return ans; hugeint plustwo(hugeint a) /计算大整数 a 加 2 之后的结果 int i; hugeint ans; ans=a; ans.num1+=2; i=1; while( (i=10) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+10) ans.len+; return ans; bool over(hugeint a,hugeint b) / 若大整数 ab 则返回 true ，否则返回 false int i; if(a.lenb.len ) return true; for(i=a.len;i=1;i-) if(a.numib.numi) return true; return false; int main() string s; int i; hugeint target,left,middle,right; cins; memset(target.num,0,sizeof(target.num); target.len=s.length(); for(i=1;i=1;i-) coutleft.numi; return 0; NOIP2011-2. 笛卡尔树 对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先， 它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次， 它的中序遍历恰好就是给定的序列。例如，对于序列 7、2、12、1、10、5、15、 3，下图就是一棵对应的笛卡尔树。现输入序列的规模 n（1nmaxDeep) maxDeep=deep; num=1; else if(deep=maxDeep) num+; min= INFINITY; for(i=left;iai) min=ai; j = i; if(leftn; for(i=1;iai; maxDeep=0; solve(1,n,1); coutmaxDeep numnm; memset(used, false, sizeof(used); for (i = 1; i = m; i+) datai = i; usedi =true; flag = true; while (flag) for (i = 1; i= m-1; i+) coutdatai ; coutdatam= 1; i-) useddatai = false; for (j =datai+1; j = n; j+) if (!usedj) usedj =true; datai = j; flag = true; break; if (flag) for (k = i+1;k element; if(next(head)=tail) n+; sn = qtail; tail=next(tail); if(empty) empty=false; else head=next(head); qhead=element; void pop() if(empty) coutError:thestackisempty!endl; return; coutqhead0) tail=previous(tail); qtail=sn; n-; voidreverse() int temp; if(next(head)=tail) direction = !direction; temp=head; head=tail; tail=temp; else coutError:lessthancelementsinthestack!c; n= 0; tail=1; head=1; empty=true; direction=true; do cinr; switch(r) case1:push();break; case2:pop();break; case3:reverse();break; while(r!=0); return 0; NOIP2013-1. 序列重排 全局数组变量 a 定义如下： Const intSIZE = 100; int aSIZE,n; 它记录着一个长度为 n 的序列 a1,a2,an。 现在需要一个函数，以整数 p(1pn)为参数，实现如下功能：将序列 a 的前 p 个数与后 np 个数对调，且不改变这 p 个数（或 np 个数）之间的相对位置。 例如，长度为 5 的序列 1,2,3,4,5，当 p=2 时重排结果为 3,4,5,1,2。 有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n)、空间复杂度为 O(n)： void swap1(int p) int i, j, bSIZE; for (i = 1; i = p; i+) bnp+i = ai; for (i = p + 1; i = n; i+) bi - p = ai; for (i = 1; i = n; i+) ai = bi; 我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算 法： void swap2(int p) int i, j, temp; for (i = p + 1; i =ip+1; j-) aj = aj - 1; ai p = temp; 事实上，还有一种更好的算法，时间复杂度为 O(n)、空间复杂度为 O(1)： void swap3(int p) int start1, end1, start2, end2, i, j, temp; start1 = 1; end1 = p; start2 = p + 1; end2 = n; while (true) i = start1; j = start2; while (i = end1) ai = aj; aj = temp; i+; j+; if (i = end1) start1 = i; else if ( jn; for (i = 1; i ai; i = 1; j = 1; /i, j 分别表示当前子序列的首尾，并保证其中至多有两个不同整数 while (j 0) if (ai = cur1) count1- else count2- i+; cur1= aj count1 = 1; if (ans_length j - i + 1) ans_length = j - i + 1; ans_start = i; ans_end = j; for (i = ans_start; i = ans_end; i+) coutai ; return 0; NOIP2014-1. 双栈模拟数组 只使用两个栈结构 stack1 和 stack2，模拟对数组的随机读取。作为栈结构， stack1 和 stack2 只能访问栈顶(最后一个有效元素)。栈顶指针 top1 和 top2 均指向栈顶元素的下一个位置。 输入第一行包含两个整数，分别是数组长度 n 和访问次数 m，中间用单个空格 隔开。第二行包含 n 个整数，依次给出数组各项(数组下标从 0 到 n-1)。第三 行包含 m 个整数， 需要访问的数组下标。 对于每次访问， 输出对应的数组元素。 #include usingnamespace std; constint SIZE = 100; intstack1SIZE, stack2SIZE; inttop1, top2;int n, m, i, j; voidclearStack() int i; for (i = top1; i n m; for (i = 0; i stack1i; top1= n ; top2= 0; for (j = 0; j i; while (i top1 - 1) top2-; stack1top1=stack2top2; top1+; clearStack(); cout stack1top1-1 m n; for (i = 1; i matrixij; ans = matrix11; for (i = 1; i = m; i+) rowsumi0=0; for (i = 1; i = m; i+) for (j = 1; j= n; j+) rowsumij = rowsumij-1+matrixij; for (first = 1; first = n; first+) for (last = first;last = n; last+) area=0; for (i = 1; i ans) ans = area; if (area 0) area = 0; cout ans n; for (i = 0; ixi; lmax0 =x0; for (i = 1; i n; i+) if (lmaxi -1 = 0) lmaxi =xi; else lmaxi =lmaxi - 1 + xi; for (i = 1; i n; i+) if (lmaxi= 0; i-) if (rmaxi +1 = 0; i-) if (rmaxi rmaxi + 1) rmaxi=rmaxi+1; ans = x0 +x2; for (i = 1; ians) ans = sum; cout ans n; for (i = 0; iwij; dist0 = 0; for (i = 1; i n; i+) disti = -1; for (i = 0; i n; i+) usedi = 0; while (true) v=-1 ; for (i = 0; i n; i+) if(usedi!=1 if (v = -1) break; usedv=1 ; for (i = 0; i n; i+) if (wvi !=-1 for (i = 0; i n; i+) cout disti endl; return 0; NOIP2016-1. 交朋友 根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有 n 名 身高两两不相同的同学依次走入教室， 调查人员想预测每个人在走入教室的瞬间 最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样 时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入 教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里， 那么这名身高为 1.80 米的同学会更想和身高为 1.81 米的同学做朋友。 对于第 一个走入教室的同学我们不做预测。 由于我们知道所有人的身高和走进教室的次序， 所以我们可以采用离线的做法来 解决这样的问题， 我们用排序加链表的方式帮助每一个人找到在他之前进入教室 的并且和他身高最相近的人。 #include using namespace std; #define MAXN 200000 #define infinity 2147483647 int answerMAXN, heightMAXN,previousMAXN, nextMAXN; int rankMAXN; int n; void sort(int l, int r) int x =heightrank(l + r) / 2, i = l, j = r, temp; while (i =j) while(heightranki x) j-; if(i=j) temp =ranki; ranki = rankj; rankj = temp; i+; j-; if (i n; int i, higher,shorter; for (i = 1; iheighti; ranki = i; sort(1, n); for (i = 1; i= 2; i-) higher =shorter = infinity; if(previousi !=0) shorter =heighti - heightpreviousi; if (nexti !=0) higher=heightnexti-heighti; if (shorterhigher) answeri =previousi; else answeri =n