下载文档原格式
NOIP复赛模拟题一1、与3和5无关的数（num.cpp）描述一个正整数x,如果它能被x整除,或者它的十进制表示法中某个位数上的数字为x,则称其为与x相关的数.现求所有小于等于n(n<300)的与x无关的正整数的平方和.<300)的与x无关的正整数的平方和.</300)的与X无关的正整数的平方和.输入输入为一行,正整数n,(n<300)输出输出小于等于n的与3和5无关的正整数的平方和样例输入8（8^2+7^2+4^2+2^2+1^2）样例输出1342、小白鼠再排队（mouse.cpp）描述N只小白鼠(1 < N < 100)，每只鼠头上戴着一顶有颜色的帽子。
现在称出每只白鼠的重量，要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。
帽子的颜色用“red”，“blue”等字符串来表示。
不同的小白鼠可以戴相同颜色的帽子。
白鼠的重量用整数表示。
输入输入第一行为一个整数N，表示小白鼠的数目。
下面有N行，每行是一只白鼠的信息。
第一个为正整数，表示白鼠的重量，；第二个为字符串，表示白鼠的帽子颜色，字符串长度不超过10个字符。
注意：白鼠的重量各不相同。
输出按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入330 red50 blue40 green样例输出redgreenblue3、滑雪(skate.cpp)描述Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。
可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长的滑坡。
区域由一个二维数组给出。
数组的每个数字代表点的高度。
下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。
在上面的例子中，一条可滑行的滑坡为24-17-16-1。
NOIP 复赛模拟试题（I ）1. 医院设置（hospital.cpp ）【问题描述】设有一棵二叉树（如下閔，其中圈中的数字表示结点中居民的人口，圈边h 数字表示结 点编号。
现在要求在某个结点上建立一个返院，使所奋佔W 所走的路程之和为最小，同吋约 定，相邻结点之M 的距离为1。
就木阁而言，若医院建在1处，则距离和 =4+12+2*20+2*40=136；若民院建在 3 处，则距离和=4*2+13+20+40=81……【输入格式（hospital.in ）］其中第一行一个整数n,表示树的结点数（n<=100）。
接K 来的n 行 每行描述了一个结点的状况，包含三个整数，整数之间川空格（一 个或多个）分隔，其中：第一个数为店民人口数；第二个数为左链 接，为0表示无链接；第三个数为右链接，为0表示无链接。
【输出格式（hospital.out ）】该文件只有一个整数，表示最小距离和。
【样例输入】 5 1323400 12 4 5 20 0 0 40 0 0【样例输出】812. 而税（area.cpp ）【问题描述】编程计算由“* ”号围成的下列图形的面积。
面积计算方法是统计*号所围成的闭合曲线中 水平线和垂直线交点的数目。
如右K 图所示，在10*10的二维数组中，有“围住了 15个点， 因此面积为15。
在输入中，为了方便起见使用“1”来代替右图中的“*”。
【输入格式（area.in ）】°输入数据保证仅冇一个10*10的01矩阵° 【输出格式（area.out ）】o0 00 0 一个数，表示面积 【样例输入】000000000000001110000000100100 0000010010 0010001010()10101 0 0 1 0010*******0010000100 00011111000000000000【样例输出】153.极值问题(number.cpp)【问题描述】已知m、n为整数，且满足下列两个条件：①m、nG { 1 , 2 ,…，k},即Km, n^k②(n2—m*n —m2) 2=1你的任务是：编程输入正整数k (l<k<109)，求一组满足上述两个条件的m、n，并且使m2+n2的值最大。
全国信息学奥林匹克联赛(NOIP2014)复赛模拟题Day1长乐一中题目名称正确答案序列问题长途旅行英文名称answer sequence travel输入文件名answer.in sequence.in travel.in输出文件名answer.out sequence.out travel.out 时间限制1s1s1s空间限制256M256M256M测试点数目202010测试点分值5510是否有部分分无无无题目类型传统传统传统是否有SPJ无无无1.正确答案【题目描述】小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。
“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。
外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。
之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。
这可让小Y与小H犯了难。
你能帮助他们还原出标准答案吗？如有多解则输出字典序最小的那个。
无解输出-1。
【输入格式】第一行四个整数n,m,p,q，意义如上描述。
接下来n行，每一行m个字符’N’或’Y’，表示这题这个神犇的答案。
【输出格式】仅一行，一个长度为m的字符串或是-1。
【样例输入】2220YYYY【样例输出】YY【数据范围】30%:n<=100.60%:n<=5000,m<=100.100%:1<=n<=30000,1<=m<=500.0<=p,q且p+q<=n.2.序列问题【题目描述】小H是个善于思考的学生，她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。
这两个集合要满足以下的条件：1.两个集合中的元素都为整数，且都在[1,n]里，即Si，Ti∈[1,n]。
2.对于集合S中任意一个元素x，集合T中任意一个元素y，满足x<y。
1.珠心算测验注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。
这样的题意加上100的规模，建议暴力3个for:#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;int n;int a[105];int main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);int res=0;for(int i=1; i<=n; i++){int ok=0;for(int j=1; j<=n && !ok; j++) if(j!=i){for(int k=1; k<=n && !ok; k++) if(a[k]!=a[j]){if(a[j]+a[k]==a[i]) ok=1;}}res+=ok;}printf("%d\n",res);return 0;}2.比例简化L很小，还是枚举，然后比较的话建议用乘法比较，避免精度问题：#include<cstdio>#include<cstring>#include<iostream>using namespace std;int A,B,L;int gcd(int a,int b){if(b==0) return a;return gcd(b,a%b);}int main(){freopen("ratio.in","r",stdin);freopen("ratio.out","w",stdout);scanf("%d%d%d",&A,&B,&L);int ba=1000000,bb=1;for(int i=1; i<=L; i++){for(int j=1; j<=L; j++){if(gcd(i,j)==1 && i*B>=j*A){if(ba*j>=bb*i){ba=i, bb=j;}}}}printf("%d %d\n",ba,bb);return 0;}3.螺旋矩阵没一圈的数量有规律的，最外面一圈(n-1)*4，然后每往里n-2，直到后要么只有一个点，要么4个点。
NOIP复赛模拟练习题（一）1．埃及分数源文件：egfranc.pas/c/cpp可执行文件：egfranc.exe输入文件：egfranc.in输出文件：egfranc.out古代埃及人喜欢用分子为1的分数，即使是普通的分数他们也喜欢将它转为若干个分子为1的分数的和。
如2/5，他们习惯表示为：1/3+1/15。
现要求你将输入的一个分子不为1的真分数转为若干个分子为1的不同的分数的和，输出要求按分母由小到大的顺序，并且是分母尽可能的小。
输入两个自然数A、B，分别表示分子和分母，输出相应的埃及分数。
样例：egfranc.in2 5egfranc.out2/5=1/3+1/152．N个因子的最小自然数源文件：minnat.pas/c/cpp可执行文件：minnat.exe输入文件：minnat.in输出文件：minnat.out一个自然数总有若干个因子，如6有4个因子：1，2，3，6。
现要求你对于给定的自然数n（1<n<=10000），求出有n个因子的最小自然数。
输入就一个数n，输出有n个因子的最小自然数。
样例：minnat.in15minnat.out1443．数字拆成K份源文件：numkd.pas/c/cpp可执行文件：numkd.exe输入文件：numkd.in输出文件：numkd.out将一个正整数n拆成k个正整数之和，如n=5,k=2时，不同的拆分方法有两种：5=1+4=2+3。
现要求根据给定的n和k，求出可能的不同拆分的数目。
输入就一行两个数，分别表示n和k（1<n<1000,0<k<=n），输出就一个数字，表示不同的拆分方法数目。
样例：numkd.in5 2numkd.out24、好心的出租车司机源文件：taxi.pas/c/cpp可执行文件：taxi.exe输入文件：taxi.in输出文件：taxi.out题目描述一位出租车司机向你抱怨：城市发展太快，公路越来越多，他已经疲于计算行驶路线，于是求助你开发一个自动导航的工具。
NOIP2014 题解D1T1 : 生活大爆炸版石头剪刀布(rps)100% : 模拟。
另一种方法，可以先求出na,nb 的最小公倍数l ，在[1,l]的区间里模拟，对于剩下的部分，显然是循环了若干次[1,l]内的胜负情况，并剩余了一小部分，于是只要把两人的分数各自乘n div l,再对剩下的部分模拟即可。
复杂度 : O(na*nb)D1T2 : 联合权值(linp)30% : 穷举三个点，判断是否相邻，再统计权值并更新答案。
复杂度 : O(n^3)60% : 穷举一个点，并以该点为起点搜索，查找距离为2的结点，统计后更新答案。
复杂度 : O(n^2)100% : 记][i fa 为结点i 的父亲, ][i pow 是i 的权值。
题目给出了n 个点，n-1条边，那么这是一棵树。
那么考虑树形dp 。
很显然，距离为2的点在一棵树中有且仅有两种不同的位置，第一种是结点i 与结点]][[i fa fa ，第二种则是结点i 与结点j ，其中][][j fa i fa =。
记∑=][][j pow i sum，]}[{]max[j pow Max i =，其中][j fa i =。
那么有∑∑-+=])[]][[(*][]][[*][*2_j pow j fa sum j pow i fa pow i sum sum ans ，]}[*][]],[[*]{max[max _i y i x i fa pow i Max ans =，其中][],[i y i x 是i 的子节点中权值最大的两个。
复杂度 : O(n)D1T3 : 飞扬的小鸟(bird)30% : 搜索。
70% : 考虑动态规划，记],[j i f 为达到坐标),(j i 至少要点击几次屏幕。
则有]])1[,1[,]]1[*,1[(],[-+-+---=i y j i f k i x k j i f Min j i f ，注意考虑边界情况。
复杂度 : O(nm^2)100% : 上述动态规划超时的原因在于转移复杂度太高，如果能将转移复杂度降为O(1)，那么就可以轻松将此题AC ，仔细想想发现对于所有可以用于更新],[j i f 的状态的高度都与j 同余(mod x[i-1])，那么在实际实现上述动态规划时，我们可以先穷举同余系，并以高度从低到高进行动态规划，在同一同余系中，记一个变量temp 为已经访问的状态中可以用于更新的最小值，每穷举到一个新的状态，把temp 更新为]),1[,1(j i f temp Min -+，并且只用temp+1更新其他状态。
活动园地NOIP2014复赛普及组第一题题解原题一、题目简化：求N个正数中有多少个数是这些数中其它两个数的和。
3<=N<=100; 每个正整数M：1<=M<=10000;二、过程分析：试题显然可以分成三个步骤求解：1、先求出N个数中每两个数的和；2、判断这些和中有没有重复，重复的数只留下一个；3、N个数中的每一个数都与这些和比较，若相等些记下，比较完成，即得其解。
三、算法与策略：三个步骤都采用一一列举所有可能的方法，是典型的枚举。
四、程序设计思路：1、一维数组A存放N个数，一维数组B存放两两相加的和；求和、判断重复、比较两数是否相等，都采用两重循环，i 控制外循环，j 控制内循环，k表示数组B的下标变化，ans表示题目答案。
数组a最多100个元素，考虑到用循环，为防止下标越界，可适当把数组开大一些，a[0..101]；数组b中元素数是N个数两个数两两相加的和的个数，由于N最大是100，所以和的个数最多是1+2+3+……99＝4950个，则b[0..5000]五、程序设计：program count;vara:array[0..101] of longint;b:array[0..5000] of longint;n,ans,i,j,k:longint;beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);readln(n);for i:=1 to n doread(a[i]);fillchar(b,sizeof(b),0);**下面开始步骤1：a中的数两两相加放在b中**k:=1;for i:=1 to n-1 dofor j:=i+1 to n dobeginb[k]:=a[i]+a[j];inc(k);end;**下面开始步骤2：筛掉b中的重复数据：**for i:= 1 to (k-1)-1 do for j:=i+1 to k-1 do begin if b[i]:=b[j] then b[j]:=0; end;**下面开始步骤3：比较a 数组中有多少个数与b 数组中的数相等：** ans:=0; for i:=1 to n dofor j:=1 to k-1 do begin if (a[i]=b[j]) then inc(ans); end;**比较结束，结果已得出，下面输出结果，关闭文件，结束程序** write(ans); close(input) close(output); end.六、时间复杂度分析：三个步骤采用了三个双重循环，每个双重循环运行约N ·∑-=11n i i 次，若N ＝100，则整个程序运行约150万次操作，T （N ）＝0（N 3）理论上讲，还可以忍受。
【问题描述】请统计某个给定范围[L,R]的所有整数中，数字N出现的次数。
【输入格式】共1行，为三个正整数L、R和N，之间用空格隔开。
(1≤L≤R≤10000)。
【输出格式】仅1行，表示数字N出现的次数。
如输入2 22 2 则输出6var a,b,c,d,e,f,n:integer;beginassign(input,'two.in');reset(input);assign(output,'two.out');rewrite(output);readln(a,b,n);f:=0;d:=0;for c:=a to b dobegine:=c;repeatd:=e mod 10;e:=e div 10;if d=n then inc(f);until e=0;end;writeln(f);close(input);close(output);end.输入2 100 5输出 20 输入 1 1000 9 输出 300输入 2222 2223 2 输出 7 输入 9993 10000 2 输出 02.用自然数1，2，3，4，5，。
构成连续数1234567891011…9899100101…从键盘输入整数m(20000m)，输出第m位数字。
样例输入输出：输入：m=15输出：2①m=11②m=194③m=100007④m=199992var p,d,i,j,w,c,m:integer;beginwrite('m=');readln(m);c:=1;i:=1;while c<m do begini:=i+1;w:=1;j:=i;while j>=10 do beginj:=j div 10;w:=w+1;end;c:=c+w;end;d:=c-m+1;for j:=1 to d do beginp:=i mod 10;i:=i div 10;end;writeln(p);end.3.聪明的囚犯：传说从前有一个残暴的国王，喜欢杀戮百姓。
有一次，他抓到30个百姓并要一一杀掉。
在这30个百姓中间有一个聪明人，他站出来对国王说：“请国王打发慈悲，赦免两个人不死。
”国王问：“赦免哪两个人不死？”那个聪明人回答说：“我们30个人围成一圈，从1开始报数，凡数到5的人就拉出去杀掉，剩下的人继续从1开始报数，循环反复，直到剩下两个人为止，这两个人被赦免。
”国王一听很有意思，就同意了聪明人的建议，叫这30个百姓围成一圈，依依报数，凡数到5的就杀掉。
最后只剩下两个人没有被杀掉，而聪明人就是其中之一。
编写程序，输入N个百姓，由计算机判断一下，聪明人要站在什么位置，才能躲过这场屠杀。
vara:array[1..1000] of 0..1;n,m,s,f,t,S1:integer;beginreadln(n,m);for t:=1 to m do a[t]:=0;f:=0;t:=0;s:=0;repeatt:=t+1;if t=n+1 then t:=1; if a[t]=0 then s:=s+1;if s>=m thenbegin s:=0;S1:=S1+1;IF S1>=N-1 THEN write(t,’’);a[t]:=1;f:=f+1; end;until f>=n;readln;end.输入45 5（11 41）56 5（12 49）83 5（234 786）4. 算盘，这个古老的计算工具是我国古代的重要发明。
在算盘上，一个档相当于整数的一位，高位在左边，所以，从右向左数，各档依次表示个位、十位、百位、……，在每个档上，靠框的珠不参与计数，靠梁的珠参与计数，且梁上面的珠每个表示5，梁下面的珠每个表示1，并规定0用本档上所有的珠都靠框来表示。
根据这个规则，上面的算盘就表示拨入了一个整数123456789（其它的档，认为是0）。
算盘的初始状态是所有的珠都靠框，即所有档上都是0。
请编写程序计算一下，从初始状态拨入一个整数n（位数≤17），一共需要拨动多少个珠？样例输入：8102样例输出：7varc:char;sum,n:integer;beginsum:=0;repeatread(c);if ord(c)=13 then break;n:=ord(c)-ord('0');if n>=5 then n:=n-4;sum:=sum+n;until false;writeln(sum);end.1、输入：12345678901234567输出：412、输入：700输出：33、输入：1000005输出：24、输入：47688798803132输出：425.现在有一个长度为N(1<=N<=1000)的并且每个数只可能是1或2或3的数列，求至少要交换多少次，才能得到一个升序的序列。
如输入N=5, 1 3 3 2 2则输出2var a:array[1..1000] of integer;n,i,j,t,n1,n2,m:longint;beginassign(input,'sort3.in');assign(output,'sort3.out');reset(input);rewrite(output);fillchar(a,sizeof(a),0);readln(n);n1:=0;n2:=0;m:=0;for i:=1 to n dobeginread(a[i]);if a[i]=1 then inc(n1);if a[i]=2 then inc(n2);end;for i:=1 to n1 doif a[i]=2 thenbegininc(m);j:=n1;repeat inc(j) until a[j]=1;t:=a[i];a[i]:=a[j];a[j]:=t;endelse if a[i]=3 thenbegininc(m);j:=n+1;repeat dec(j) until a[j]=1;t:=a[i];a[i]:=a[j];a[j]:=t;end;for i:=n1+1 to n1+n2 doif a[i]=3 thenbegininc(m);j:=n+1;repeat dec(j) until a[j]=2;t:=a[i];a[i]:=a[j];a[j]:=t;end;writeln(m);close(input);close(output);end.输入8 1 2 2 3 3 1 2 3 输出3输入12 3 2 2 1 2 3 3 2 1 1 2 3 输出5输入20 3 3 2 2 3 3 1 1 3 2 2 2 3 1 1 1 3 3 2 1 输出7输入30 2 2 1 3 2 3 2 2 1 1 3 3 3 3 2 2 3 1 1 2 1 3 3 1 2 3 3 3 1 3 输出126.一个果园主种植了一批果树，果树在二个方向上被均匀地种植在一个矩形空间内，所以，这些树形成了矩形的网格，而且我们假定每棵树都恰巧种植在整数坐标位置，坐标系统的原点位于左下角，如下图所示：现在考虑将一些三角形覆盖在此网格上，三角形的顶点为任意从0.0到100.0的实数坐标，树的坐标范围为1到99，上图给出了一个可能的实例。
设计一个程序，计算包含在给定三角形之内的树的数量。
为了便于解题，可以假定每棵树仅为一个点的大小，并且任意位于三角形边界上的树（点）可看作位于三角形之内。
输入：程序的输入包含6个大小从0.00到100.00的实数x1 y1 x2 y2 x3 y3)，代表一个三角形的三个顶点坐标。
输出：输出一行，表示该三角形覆盖的树的数量。
输入输出样例一：1.5 1.5 1.5 6.8 6.8 1.515输入输出样例二：10.7 6.9 8.5 1.5 14.5 1.517varx1,y1,x2,y2,x3,y3,x4,y4,s0,s1,s2,s3 : real;i,j,t : word; function area(x1,y1,x2,y2,x3,y3 :real) :real;var a,b,c,d :real;begina := sqrt(sqr(x1-x2)+sqr(y1-y2));b := sqrt(sqr(x2-x3)+sqr(y2-y3));c := sqrt(sqr(x1-x3)+sqr(y1-y3));d := (a+b+c)/2;area := sqrt(d*(d-a)*(d-c)*(d-b));end;beginwriteln('Input x1,y1,x2,y2,x3,y3 : ');readln(x1,y1,x2,y2,x3,y3);t := 0;s0 := area(x1,y1,x2,y2,x3,y3);for i := 1 to 99 dofor j := 1 to 99 do beginx4 := i; y4 := j;s1 := area(x1,y1,x2,y2,x4,y4);s2 := area(x1,y1,x3,y3,x4,y4);s3 := area(x2,y2,x3,y3,x4,y4);if abs(s1+s2+s3-s0) < 0.0000001 then inc(t); end;writeln(t);readln;end.输入 8.5 9.4 7.8 6.2 10.6 9.3 输出 4输入 7.9 6.5 4.8 2.3 10.8 4.2 输出 10输入 5.6 9.7 4.7 3.9 8.4 5.1 输出 11输入 88.5 99.4 90.6 78.8 92.1 89.5 输出 278. 多项式输出【题目描述】一元n 次多项式可用如下的表达式表示：其中，a i x i称为i 次项，a i称为i次项的系数。
给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。
2. 多项式中只包含系数不为0 的项。
3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系数为负，则多项式以“-”号开头。
4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。
紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。
如果x 的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。
5. 多项式中，多项式的开头、结尾不含多余的空格。
