2008noip普及组复赛--排座位--代码C++

【试题描述】读入二行整数，然后程序要完成如下的操作：第一步将2行数合并在一起，第二步将合并好的数由大到小排序，第三步重新排列，从第一个数起开始编号，然后将奇数号上的数（样例中的13，9，5）从前向后排，偶数号上的数（样例中的12，7，4）从后往前排。

第四步计算，将排好的数，第一个+第二个数的2倍+第三个数的3倍+…第五步：输出计算的结果。

【输入描述】第一行是一个整数 n(1≤n≤10)，第二行有n个整数，整数范围在1~100之间，数与数之间空格隔开。

第三行是一个整数 m(1≤m≤10)，第四行有m个整数，整数范围在1~100之间，数与数之间空格隔开。

【输出描述】一个整数（最后计算的结果）。

【输入样例】412 4 5 9213 7【输出样例】 169【解题提示】样例说明：第一步合并后为：12 4 5 9 13 7第二步上例中的数成为：13 12 9 7 5 4第三步得到：13 9 5 4 7 12第四步计算后为：13+2×9+3×5+4×4+5×7+6×12=169最后输出 169【试题来源】 2008年江苏省小学生信息学（计算机）奥赛program ex1731;var m,n,i,j,s,t,b1,b2:integer;a,b,c:array[1..20] of integer;sum:longint;beginreadln(n);for i:=1 to n do read(a[i]);readln(m);for i:=1 to m do read(a[i+n]);s:=m+n;for i:=1 to s-1 dofor j:=i+1 to s doif a[i]<a[j] then begint:=a[i];a[i]:=a[j];a[j]:=t;end;b1:=0;b2:=0;for i:=1 to s doif i mod 2=1 then begin inc(b1); b[b1]:=a[i];endelse begin inc(b2); c[b2]:=a[i];end;for i:=1 to b1 do a[i]:=b[i];for i:=1 to b2 do a[b1+i]:=c[b2-i+1];sum:=0;for i:=1 to s dosum:=sum+i*a[i];writeln(sum);end.输入 615 34 25 9 22 39423 17 46 57输出1496输入1015 34 25 9 22 39 47 12 33 99823 17 46 57 51 8 38 64输出5687SHLQSH数问题描述：我们把t1 , t2 (包括t1 , t2 (1<=t1<t2<=10000000))之间的所有数的约数个数和n称为t1 , t2的shlqsh数;问题是给出数据t1 , t2后,求t1 , t2的shlqsh数；输入输入文件shlqsh.in 仅包含一行，共有两个整数，表示t1 t2 (用空格分开)输出输出文件shlqsh.out 仅有一个整数，表示t1 , t2之间的shlqsh数。

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

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

1．微型计算机中，控制器的基本功能是（）。

A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C. 获取外部信息D. 存放程序和数据2. 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。

A. (A∧B)∨(C∧D∨?A)B. ((?A∧B)∨C)∧?DC. (B∨C∨D)∧D∧AD. A∧(D∨?C)∧B3. 在下列关于图灵奖的说法中，不正确的是（）。

A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A. ROM和RAMB. CPUC.ROMD. RAM5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1B. NC. 2*ND. 2N-16. 在以下各项中，（）不是操作系统软件。

A. SolarisB. LinuxC. Windows VistaD. Sybase7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。

A. 6B. 5C. 4D. 38. 与十进制数28.5625相等的四进制数是（）。

A. 123.21B. 131.22C. 130.22D. 130.219. 设字符串S=”Olympic”，S的非空子串的数目是（）。

全国青少年信息学奥林匹克联赛复赛模拟试题湖南省长沙市第一中学周祖松1．无限序列(infinit.pas/c/cpp)【问题描述】我们按以下方式产生序列：1、开始时序列是： "1" ；2、每一次变化把序列中的 "1" 变成 "10" ，"0" 变成 "1"。

经过无限次变化，我们得到序列"1011010110110101101..."。

总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。

任务写一个程序回答Q个询问输入第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。

输出共Q行，每行一个回答约定∙ 1 <= Q <= 5000∙ 1 <= a <= b < 263样例分析：我们先看看序列变化规律，S1 = "1", S2 = "10", S3 = "101", S4 = "10110", S5 = "10110101", 等等. Si 是 S（i+1）的前缀。

序列Si 是由序列 S（i-1）和 S（i-2）, 连接而成的。

即Si = Si-1 + Si-2 (实际上上是Fibonacci数列)。

找到规律以后，我们可以可以用递归的方法求出从从位置1到位置X之间所有的1的个数，用一个函数F计算，结果为f(b)-f(a-1)。

时间复杂度为： O(Q * log MAX_VAL)此题需要先找出数学规律，再进用递归实现。

主要考查选手的数学思维能力和递归程序的实现。

源程序：constnn=92; //进行92次的数列扩展后，数列长度就会超过给定的数据范围,varf,ft:array[0..nn] of int64;q,i,j,l1,l2:longint;a,b:qword;procedure prapre;{预处理}var i:longint;beginf[0]:=1;f[1]:=1;ft[0]:=0;ft[1]:=1;for i:=2 to nn dobeginf[i]:=f[i-1]+f[i-2];ft[i]:=ft[i-1]+ft[i-2];end;end;function find(a:int64;ll:longint):int64;{求这个数列的前a个有多少个1}beginif a=0 then exit(0);find:=0;if a=f[ll] then find:=ft[ll] elseif a<=f[ll-1] then find:=find(a,ll-1)else find:=ft[ll-1]+find(a-f[ll-1],ll-2);end;beginassign(input,'infinit.in');reset(input);assign(output,'infinit.out');rewrite(output);prapre;readln(q);for i:=1 to q dobeginreadln(a,b);writeln(find(b,nn)-find(a-1,nn));end;close(input);close(output);end.2．删数(remove.pas/c/cpp)【问题描述】有N个不同的正整数数x1, x2, ... x N排成一排，我们可以从左边或右边去掉连续的i个数（只能从两边删除数），1<=i<=n，剩下N-i个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。

全国信息学奥林匹克联赛（NOIP2008）复赛提高组一、题目概览中文题目名称笨小猴火柴棒等式传纸条双栈排序英文题目名称word matches message twostack可执行文件名word matches message twostack 输入文件名word,in matches.in message.in twostack.in 输出文件名word.out matches.out message.out twostack.out 每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10每个测试点分值10 10 10 10 比较方式全文比较全文比较全文比较全文比较题目类型传统传统传统传统二、提交源程序文件名对于Pascal语言word.pas matches.pas message.pas twostack.pas 对于C语言word.c matches.c message.c twostack.c对于C++语言word.cpp matches.cpp message.cpp twostack.cpp三、编译命令（不包含任何优化开关）对于Pascal语言fpc word.pas fpc matches.pas fpc message.pas fpc twostack.pas对于C语言gcc –o wordword.c gcc –o matchesmatches.cgcc –o messagemessage.cgcc –o twostacktwostack.c对于C++语言g++ -o wordword.cpp g++-o matchesmatches.cppg++ -o messagemessage.cppg++ -o twostacktwostack.cpp四、运行内存限制运行内存上限50M 50M 50M 50M注意事项：1. 文件名（程序名和输入输出文件名）必须使用大写。

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

noip普及组复赛入门训练1答案PASCAL复习21. 字符统计(文件名ZFTJ.PAS)读入一组字符，以“？”作为结束标志，统计其中元音字母、辅音字母、数字和其它符号个数（“？”作为结束标志，不计算个数）。

如输入字符为SouA56#s?,则输出YY=3，FY=2，SZ=2，QT=1。

输入输出样例：输入：SouA56#sEenTk3&?输出：YY=5，FY=5，SZ=3，QT=2var s1,S2,S3,S4,t:longint;c:char;begin S1:=0;S2:=0;S3:=0;S4:=0;while c<>'?' dobegin read(c);if ((c>='a') and (c<='z')) or ((c>='A') AND (C<='Z')) THENif (c='a') or (c='e') or (c='i') OR (c='o') or (c='u') or(c='A') OR (c='E') OR (c='I') OR (c='O') OR (c='U')THEN S1:=S1+1 ELSE S2:=S2+1ELSEIF (c>='0') and (c<='9') then s3:=s3+1ELSE S4:=S4+1;end;writeln('YY=',S1,'FY=',S2,'SZ=',S3,'QT=',S4-1);END.2．取数（QS.PAS）问题描述：我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。

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

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

1．微型计算机中，控制器的基本功能是（）。

A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C. 获取外部信息D. 存放程序和数据2. 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。

A. (A∧B)∨(C∧D∨⌝A)B. ((⌝A∧B)∨C)∧⌝DC. (B∨C∨D)∧D∧AD. A∧(D∨⌝C)∧B3. 在下列关于图灵奖的说法中，不正确的是（）。

A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A. ROM和RAMB. CPUC.ROMD. RAM5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1B. NC. 2*ND. 2N-16. 在以下各项中，（）不是操作系统软件。

A. SolarisB. LinuxC. Windows VistaD. Sybase7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。

A. 6B. 5C. 4D. 38. 与十进制数28.5625相等的四进制数是（）。

A. 123.21B. 131.22C. 130.22D. 130.219. 设字符串S=”Olympic”，S的非空子串的数目是（）。

A. 28B. 29C. 16D. 1710．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。

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

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

1．微型计算机中，控制器的基本功能是（）。

，a，则A. 28B. 29C. 16D. 1710．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。

下列网站中，（）是典型的Web2.0应用。

A. SinaB. FlickrC. YahooD. Google11．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。

A. 队列B. 多维数组C. 线性表D. 栈12. (2008)10 + (5B)16的结果是（）。

精心整理A. (833)16B. (2089)10C. (4163)8D. (100001100011)213. 二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 57 3 6，则该二叉树的后根遍历是（）。

A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 114．将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。

等。

二．问题求解（共2题，每题5分，共计10分）1. 书架上有4本不同的书A、B、C、D。

其中A和B是红皮的，C和D是黑皮的。

把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_____种。

满足 A必须比C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有______种摆法。

2．有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1精心整理2．#include<iostream>using namespace std;void foo(int a, int b, int c){if(a > b)foo(c, a, b);else精心整理cout<<a<<','<<b<<','<<c<<endl;}int main(){int a, b, c;cin >> a >> b >> c;foo(a, b, c);}int main(){int a[20], i, m;m=10;精心整理for(i=0; i<m; i++){cin>>a[i];}func(a, m);for (i=0; i<m; i++)cout<<a[i]<<" ";solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1); solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);cout << first[spos_f];}int main(){精心整理char first[MAX], mid[MAX];int len;cin >> len;cin >> first >> mid;solve(first, 0, len - 1, mid , 0, len - 1);cout << endl;return 0;S，第S中的bfor (i = 0;i < 26;i ++){if ( ① )change[i] -= 'A' - 'a';}}精心整理void ChangeString(){int i;for (i = 0;i <strlen(str);i ++){if ( ② )str[i] = change[str[i] - 'A'] -'a' + 'A';6}中int a[1000001],n,ans = -1;void swap(int &a,int &b){int c;c = a; a = b; b = c;}精心整理int FindKth(int left, int right, int n){int tmp,value,i,j;if (left == right) return left;tmp = rand()% (right - left) + left;swap(a[tmp],a[left]);cin >> n;ans = FindKth(1,m,n);cout << a[ans];return 0;}精心整理参考答案一．选择题ABCCB DCDAB DABBB ABABD二．问题解答1.12 4精心整理2.7三．阅读程序1.232. 2.,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. DBGEFCA四．完善程序1.（1）change[i] >= 'A' && change[i] <= 'Z'(只写change[i] <= 'Z'也对)精心整理。

全国信息学奥林匹克联赛（NOIP2008）复赛普及组一.题目概览中文题目名称ISBN号码排座椅传球游戏立体图英文题目名称isbn seat ball drawing可执行文件名isbn seat ball drawing输入文件名isbn.in seat.in ball.in drawing.in输出文件名isbn.out seat.out ball.out drawing.out每个测试点时限1秒1秒1秒1秒测试点数目10 10 10 10每个测试点分值10 10 10 10比较方式全文比较全文比较全文比较全文比较题目类型传统传统传统传统二.提交源程序文件名对于pascal语言isbn.pas seat.pas ball.pas drawing.pas对于C语言isbn.c seat.c ball.c drawing.c对于C++语言isbn.cpp seat.cpp ball.cpp drawing.cpp三.编译命令（不包含任何优化开关）对于pascal语言fpc isbn.pas fpc seat.pas fpc ball.pas fpc drawing.pas对于C语言gcc –o isbnisbn.c gcc –o seatseat.c gcc –o ballball.c gcc –o drawingdrawing.c对于C++语言g++ –o isbnisbn.cpp g++ –o seatseat.cpp g++ –o ballball.cpp g++ –odrawingdrawing.cpp四.运行内存限制运行内存上限50M 50M 50M 50M注意事项：1、文件名（程序名和输入输出文件名）必须使用小写。

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

3、全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。

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

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

）1．微型计算机中，控制器的基本功能是（）。

A．控制机器各个部件协调工作B．实现算术运算和逻辑运算C．获取外部信息D．存放程序和数据2．设A=True，B=False，C=True，D=False，以下逻辑运算表达式值为真的是（）。

A．(A∧B)∨(C∧D∨﹁A)B．((﹁A∧B)∨C)∧﹁DC．(B∨C∨D)∧D∧A D．A∧（D∨﹁C）∧B3．在下列关于图灵奖的说法中，不正确的是（）。

A．图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B．图灵奖有“计算机界诺贝尔奖”之称C．迄今为止，还没有华裔计算机科学家获此殊荣D．图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A．ROM和RAM B．CPU C．ROM D．RAM5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A．N-1B．N C．2*N D．2N-16．在以下各项中，(）不是操作系统软件。

A．Solaris B．Linux C．Windows Vista D．Sybase7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。

A．6B．5C．4D．38．与十进制数28.5625相等的四进制数是（）。

A．123.21B．131.22C．130.22D．130.219．设字符串S=”Olympic”，S的非字串的数目是（）。

A．28B．29C．16D．1710．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。

下列网站中，（）是典型的Web2.0应用。

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

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

）1．微型计算机中，控制器的基本功能是（）。

A．控制机器各个部件协调工作B．实现算术运算和逻辑运算C．获取外部信息D．存放程序和数据2．设A=True，B=False，C=True，D=False，以下逻辑运算表达式值为真的是（）。

A．(A∧B)∨(C∧D∨﹁A) B．((﹁A∧B) ∨C)∧﹁DC．(B∨C∨D) ∧D∧A D．A∧（D∨﹁C）∧B3．在下列关于图灵奖的说法中，不正确的是（）。

A．图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B．图灵奖有“计算机界诺贝尔奖”之称C．迄今为止，还没有华裔计算机科学家获此殊荣D．图灵奖的名称取自计算机科学的先驱、英国科学家阿兰•图灵4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A．ROM 和RAM B．CPU C．ROM D．RAM5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A．N-1 B．N C．2*N D．2N-16．在以下各项中，( ）不是操作系统软件。

A．Solaris B．Linux C．Windows V ista D．Sybase7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。

A．6 B．5 C．4 D．38．与十进制数28.5625相等的四进制数是（）。

A．123.21 B．131.22 C．130.22 D．130.219．设字符串S=”Olympic”，S的非字串的数目是（）。

A．28 B．29 C．16 D．1710．Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。

P1055[NOIP2008普及组]ISBN号码题⽬描述每⼀本正式出版的图书都有⼀个ISBN号码与之对应，ISBN码包括99位数字、11位识别码和33位分隔符，其规定格式如x-xxx-xxxxx-x，其中符号-就是分隔符（键盘上的减号），最后⼀位是识别码，例如0-670-82162-4就是⼀个标准的ISBN码。

ISBN码的⾸位数字表⽰书籍的出版语⾔，例如00代表英语；第⼀个分隔符-之后的三位数字代表出版社，例如670670代表维京出版社；第⼆个分隔符后的五位数字代表该书在该出版社的编号；最后⼀位为识别码。

识别码的计算⽅法如下：⾸位数字乘以11加上次位数字乘以22……以此类推，⽤所得的结果\bmod 11mod11，所得的余数即为识别码，如果余数为1010，则识别码为⼤写字母XX。

例如ISBN号码0-670-82162-4中的识别码44是这样得到的：对067082162这99个数字，从左⾄右，分别乘以1,2,...,91,2,...,9再求和，即0×1+6×2+……+2×9=1580×1+6×2+……+2×9=158，然后取158 \bmod 11158mod11的结果44作为识别码。

你的任务是编写程序判断输⼊的ISBN号码中识别码是否正确，如果正确，则仅输出Right；如果错误，则输出你认为是正确的ISBN号码。

输⼊格式⼀个字符序列，表⽰⼀本书的ISBN号码（保证输⼊符合ISBN号码的格式要求）。

输出格式⼀⾏，假如输⼊的ISBN号码的识别码正确，那么输出Right，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符-）。

1//2// Created by Administrator on 2022/1/8.3//45 #include <iostream>6 #include <string>7 #include <cstdio>8using namespace std;910int main()11 {12char a[14], mod[12] = "0123456789X";13 scanf("%s" , a);14int i, j = 1, t = 0;15for (i = 0; i < 12; i++)16 {17if (a[i] == '-')18 {19continue;20 }21 t += (a[i] - '0') * j;22 j++;23 }24if (mod[t % 11] == a[12])25 { printf("Right"); }26else27 {28 a[12] = mod[t % 11];29 puts(a);30 }31return0;32 }。