NOIP提高组初赛历年试题及答案阅读题篇.doc

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;
}
输入：
11
4 5 6 6 4 3 3 2 3 2 1
一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]
输出：3

NOIP2011-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 34

NOIP2011-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 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60
一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：

如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，结果如下图：

输出：150

NOIP2011-4．
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
int ans,i;
ans=0;
for(i=1;i<=n;i++)
if( a[u][i]!=a[v][i])
ans++;
return ans;
}
int main()
{
int sum,i,j;
cin>>n;
memset(a,0,sizeof(a));
m=1;
while(1)
{
i=1;
while( (i<=n) &&(a[m][i]==1) )
i++;
if(i>n)
break;
m++;
a[m][i]=1;
for(j=i+1;j<=n;j++)
a[m][j]=a[m-1][j];
}
sum=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
sum+=h(i,j);
cout<<sum<<endl;
return 0;
}
输入：7
根据while(1)的程序功能模拟几行看看，观察m*n的0-1矩阵，此矩阵其实就是所有7位的二进制数（顺序左右颠倒），m=2^n。再根据h(u,v)的程序功能判断出本程序的目的。

每一列中有2^n-1个1和0，在一列里每个1都有2^(n-1)个0与它不同，同样每个0也有2^(n-1)个1与它不同，即每列的结果为2^(2n-2)*2=2^(2n-1)，n列的结果为n*2^(2n-1)，所以本题的结果为2^13*7。
输出：57344

NOIP2012-1.
#include <iostream>
using namespace std;
int n,i,temp,sum,a[100];
int main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>a[i];
for (i=1;i<=n-1;i++)
if(a[i]>a[i+1]){
temp=a[i];
a[i]= a[i+1];
a[i+1]=temp;
}
for (i=n;i>=2;i--)
if(a[i]<a[i-1]){
temp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
}
sum=0;
for (i=2;i<=n-1;i++)
sum +=a[i];
cout<<sum/(n -2)<<endl;
return 0;
}
输入：
8
40 70 50 70 20 40 10 30
两轮冒泡，掐头去尾，求均值。
数据量不大，就直接模拟吧，速度也挺快的。
输出：41

NOIP2012-2.
#include <iostream>
using namespace std;
int n,i,ans;
int gcd(inta,intb)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
int main()
{
cin>>n; ans=0;
for (i=1;i<=n;i++)
if(gcd(n,i)== i)
ans++;
cout<<ans<<endl;
return 0;
}
输入：120
gcd就是求最大公约数，如果gcd(n,i)== i则计数，即求120的因子数。
输出：16

NOIP2012-3.
#include <iostream>
using namespace std;
const int SIZE=20;
int data[SIZE];
int n,i,h,ans;
void merge()
{
data[h-1]=data[h-1]+data[h];
h--;
ans++;
}
int main()
{
cin>>n;
h= 1;
data[h]=1;
ans=0;
for (i=2;i<=n;i++)
{
h++;
data[h]=1;
while(h>1&&data[h]==data[h-1])
merge();
}
cout<<ans<<endl;
return 0;
}
输入：8
继续模拟，while语句中函数调用细心点即可。

输出：7
输入：2012
对前面的模拟进行观察，得出如下规律后计算：
i=2012=512+256+128+64+16+8+4
即data[1]=512data[2]=256 data[3]=128 data[4]=64 data[5]=16 data[6]=8 data[7]=4
ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004
输出：2004

NOIP2012-4.
#include <iostream>
#include <string>
using namespace std;
int lefts[20],rights[20],father[20];
string s1,s2,s3;
int n,ans;
void calc(int x,int dep)
{
ans=ans+dep*(s1[x] -'A'+1);
if(lefts[x]>=0)calc(lefts[x],dep+1);
if(rights[x]>=0)calc(rights[x],dep+1);
} //递归函数，返回ans，累计结点深度*结点权值之和
void check(int x)
{
if(lefts[x]>=0)check(lefts[x]);
s3=s3+s1[x];
if(rights[x]>=0)check(rights[x]);
}
void dfs(int x,int th)
{
if(th==n)
{
s3="";
check(0);
if(s3==s2)
{
ans=0;
calc(0,1);
cout<<ans<<endl;
} //输出递归函数calc(0,1)的值
return;
}
if(lefts[x]==-1&&rights[x]== -1)
{
lefts[x]=th;
father[th]=x;
dfs(th,th+1);
father[th]= -1;
lefts[x]=-1;
}
if(rights[x]== -1)
{
rights[x]=th;
father[th]=x;
dfs(th,th+1);
father[th]= -1;
rights[x]=-1;
}
if(father[x]>=0)
dfs(father[x],th);
}
int main()
{
cin>>s1; //先序遍历序列
cin>>s2; //中序遍历序列
n= s1.size();
memset(lefts, -1,sizeof(lefts));
memset(rights,-1,sizeof(rights));
memset(father,-1,sizeof(father));
dfs(0,1);
}
输入：
ABCDEF
BCAEDF
这是二叉树的遍历题，先根据两个输入的遍历序列确定二叉树。
再根据递归函数计算六个结点深度*权值之和:
ans=1*1+2*2+3*3+4*2+5*3+6*3
输出：55

NOIP2013-1.
#include <iostream>
#include <string >
using namespace  std;
int main( )
{
string Str;
cin>>str;
int  n = str.size( );
bool  isPlalindrome = true;
for (int  i =0; i<n/2;i++){
if(str[i] !=str[n-i-1])  isPlalindrome =false;
}
if(isPlalindrome)
cout<< ”Yes” << endl;
else
cout<< ”No” << endl;
}
输入：abceecba
判断输入的是不是一个回文串，字符串左右颠倒，结果不变。
输出：Yes

NOIP2013-2.
#include <iostream>
using namespace std;
int main( )
{
int  a,b,u,v,i, num;
cin>>a>>b>>u>>v;
num  =0;
for  ( i= a; I <=b;  i++)
if(((i%u) ==0)||((i%v)==0))
num ++;
count <<num<<endl;
return  0;
}
输入：1  1000 10 15
1-1000范围内同时是10、15的倍数有多少？注意去重。
输出：133

NOIP2013-3.
#include <iostream>
using namespace std;
int main( )
{
const  int SIZE = 100;
int  height[SIZE], num[SIZE],  n, ans;
cin>>n;
for  (int i=0;  i<n;  i++) {
cin>>height[i];
num[i]=1;
for  (int j=0;  j<i;  j++) {
if((height[j]<height[i])&&(num[j]>= num[i]))
num[i]=num[j]+1;
}
}
ans =0;
for(int  I = 1; i<n;  i++){
if(num[i]>ans) ans =num[j];
}
cout <<ans<<endl;
return 0;
}
输入：
8
3 2 5 11 12 7 4 10
求该字符串的最长上升子序列的长度。
输出：4

NOIP2013-4.
#include <iostream>
#include <string >
using namespace  std;
const  int  SIZE = 100;
int  n,  m, p,  a[SIZE] [SIZE], count;
void  colour  (int x,  int  y)
{
Count++;
a[x][y] = 1;
if ((x > 1)&&(a[x-1][y]  == 0))
colour(x - 1, y);
if ((y> 1)&&(a[x][y-1]  == 0))
colour(x, y- 1);
if ((x < n)&&(a[x+1][y]  == 0))
colour(x +1, y);
if ((y < m)&&(a[x][y+1]  == 0))
colour(x, y+1);
}
int main( )
{
int  i, j,  x,  y, ans;
memset(a,  0, sizeof(a));
cin >>n>>m>>p;
for(i =1 ; I <=p;  i++) {
cin>>x>>y;
a[x][y]  = 1;
}
ans  =  0;
for  (i =1; i <=n; i++)
for  (j =1; j <=m;j++)
if(a[i][j]  ==  0){
count  =  0;
colour  (i , j);
if  (ans <count)
ans<count;
}
count<<ans<<endl;
return  0;
}
输入：
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
根据输入的x和y值画出0-1矩阵，再判断同一区域0最多的个数

输出：7

NOIP2014-1.
#include <iostream>
using namespace std;
int main()
{
int a, b, i, tot, c1, c2;
cin >> a >> b;
tot = 0;
for (i = a; i <= b; i++)
{
c1 = i / 10;
c2 = i % 10;
if ((c1 + c2) % 3== 0)
tot++;  //一个数的各位数之和是3的倍数，它就是3的倍数。
}
cout << tot << endl;
return 0;
} //统计7-31之间有多少数是3的倍数
输入: 7  31
输出: 8

NOIP2014-2.
#include <iostream>
using namespace std;
int fun(int n, int minNum, int maxNum)
{
int tot, i;
if(n == 0)
return1;
tot= 0;
for(i = minNum; i <= maxNum; i++)
tot+= fun(n - 1, i + 1, maxNum);
returntot;
}
int main()
{
int n, m;
cin>> n >> m;
cout<< fun(m, 1, n) << endl;
return 0;
}
输入: 6  3
递归边界：当n=0时，fun(n,minNum,maxNum)=1
fun(3,1,6)=(2,2,6)+(2,3,6)+(2,4,6)+(2,5,6)+(2,6,6)+(2,7,6)=20
fun(2,2,6)=(1,3,6)+(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=10
fun(2,3,6)=(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=6
fun(2,4,6)=(1,5,6)+(1,6,6)+(1,7,6)=3
fun(2,5,6)=(1,6,6)+(1,7,6)=1
fun(2,6,6)=(1,7,6)=0
fun(1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,7,6)=4
fun(1,4,6)=(0,5,6)+(0,6,6)+(0,7,6)=3
fun(1,5,6)=(0,6,6)+(0,7,6)=2
fun(1,6,6)=(0,7,6)=1
fun(1,7,6)=0
输出: 20

NOIP2014-3.
#include <iostream>
#include <string>
using namespace std;
const int SIZE = 100;
int main()
{
string dict[SIZE];
int rank[SIZE];
int ind[SIZE];
int i, j, n, tmp;
cin >> n;
for (i = 1; i <= n; i++) {
rank[i] = i;
ind[i] = i;
cin >>dict[i];
}
for  (i= 1; i < n; i++)
for (j = 1; j<= n - i; j++)
if (dict[ind[j]]> dict[ind[j + 1]]){
tmp = ind[j];
ind[j] = ind[j +1];
ind[j + 1] = tmp;
} //冒泡排序
for (i = 1; i <= n; i++)
rank[ind[i]] = i; //输出dict里字符排序后应该在的位置
for (i = 1; i <= n; i++)
cout <<rank[i] << " ";
cout << endl;
return 0;
}
输入:
7
aaa
aba
bbb
aaa
aaa
ccc
aa

输出: 2 5 6 3 4 7 1

NOIP2014-4.
#include <iostream>
using namespace std;
const int SIZE = 100;
int alive[SIZE];
int n;
int next(int num)
{
do {
num++;
if (num > n)
num = 1;
} while (alive[num] == 0);
return num;
}
int main()
{
int m, i, j, num;
cin >> n >> m;
for (i = 1; i <= n; i++)
alive[i] = 1;
num = 1;
for (i = 1; i <= n; i++) {
for (j = 1; j <m; j++)
num = next(num);
cout << num<< " ";
alive[num] = 0;
if (i < n)
num = next(num);
}
cout << endl;
return 0;
}
输入: 11 3
这就是约瑟夫环问题，11个人围一圈，从1开始报数，报到3的出局，再从出局的下一个人开始报1，直到全部出局，依次输出出局人的编号。
输出: 3 6 9 1 5 10 4 11 8 2 7

NOIP2015-1. //同普及组阅读题NOIP2015-2
#include <iostream>
using namespace std;
struct point {
int x;
int y;
};
int main()
{
struct EX{
int a;
int b;
point c;
}e;
e.a= 1;
e.b= 2;
e.c.x= e.a + e.b;
e.c.y= e.a * e.b;
cout<< e.c.x << ',' << e.c.y << endl;
return 0;
}
输出: 3,2 //注意输出有逗号

NOIP2015-2. //同普及组阅读题NOIP2015-4
#include <iostream>
using namespace std;
void fun(char *a, char *b) {
a = b;
(*a)++;
}
int main()
{
char c1, c2, *p1, *p2;
c1 = 'A';
c2 = 'a';
p1 = &c1;
p2 = &c2;
fun(p1, p2);
cout << c1 << c2 << endl;
return 0;
} //指针题，注意*a、&a、'a'的区别。
输出: Ab

NOIP2015-3.
#include <iostream>
#include <string>
using namespace std;
int main()
{
int len, maxlen;
string s, ss;
maxlen = 0;
do {
cin >> ss;
len = ss.length();
if (ss[0] == '#')
break;
if (len >maxlen) {
s = ss;
maxlen = len;
}//输出长度最长的字符串s
} while (true);
cout << s << endl;
return 0;
}
输入:
I
am
a
citizen
of
China
#
输出: citizen

NOIP2015-4.
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos)
{
int t, tot;
if (n == 0)
return 0;
for (t = 1; t <= 3; t++)
if (t != fromPos&& t != toPos)
break;
tot = 0;
tot += fun(n - 1, fromPos, t);
tot++;
tot += fun(n - 1, t, toPos);
return tot;
}
int main()
{
int n;
cin >> n;
cout << fun(n, 1, 3) << endl;
return 0;
}
输入: 5
递归边界：当n=0时，fun(n,fromPos,toPos)=0
fun(5,1,3)=(4,*,*)+1+(4,*,*)=31
fun(4,*,*)=(3,*,*)+1+(3,*,*)=15
fun(3,*,*)=(2,*,*)+1+(2,*,*)=7
fun(2,*,*)=(1,*,*)+1+(1,*,*)=3
fun(1,*,*)=(0,*,*)+1+(0,*,*)=1
输出: 31

NOIP2016-1.
#include <iostream>
using namespace std;
int main()
{
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
intt , i;
while (pi < pj) {
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout<< a[i] << ",";
cout << endl;
return 0;
}//倒序输出，注意逗号
输出：6,5,4,3,2,1,

NOIP2016-2.
#include <iostream>
using namespace std;
int main()
{
char a[100][100], b[100][100];
string c[100];
string tmp;
intn, i = 0, j = 0, k = 0, total_len[100], length[100][3];
cin >> n;
getline(cin, tmp);
for (i = 0; i < n; i++) {
getline(cin, c[i]);
total_len[i] = c[i].size(); //记录c[i]的长度
}
for (i = 0; i < n; i++) {
j = 0;
while (c[i][j] != ':') {
a[i][k] = c[i][j];
//扫描c[i],当c[i]的第j个字符不为":"时，将c[i]的字符存入a[i][k]中，即把c[i]字符串":"前的所有字符存入a[i][k]中，将c[i][0]-->c[i][j]中的字符存入a[i][0]-->a[i][k](k==j)中。
k = k + 1;
j++;
}
length[i][1] = k - 1;
//记录":"前的字符的个数
a[i][k] = 0; //记录":"所在的位置
k = 0;
for (j = j + 1; j < total_len[i]; j++) {
b[i][k] = c[i][j];
//由于j是扫描到":"后的值再+1，所以此时的c[i][j]为":"后输入的字符，并将其存入b[i][k]中
k = k + 1;
}
length[i][2] = k - 1;
//记录":"后的字符的个数
b[i][k] = 0; //记录终点位置
k = 0;
}
for (i = 0; i < n; i++) {
if (length[i][1] >=length[i][2])
cout << "NO,"; //如果":"前的字符比":"后的字符个数多,输出"NO,"
else {
k = 0;
for (j = 0; j < length[i][2];j++) {
if (a[i][k] == b[i][j])
//如果":"前的字符在":"后有出现
k = k + 1;
//找下一个":"前的符是否有出现，是从当前位置往后找
if (k > length[i][1])
break;
//如果k的值比":"前的字符长度大，即已经找完了":"前的所有字符，那么退出循环
}
if (j == length[i][2])
cout << "NO,";
//如果j的值和":"后的字符串长度相等，即在扫描到最后一个点时，无论":"前的字符是否被全部找完，都输出"NO,"
else
cout << "YES,";
//如果在找完字符串之前已经找到了":"前的字符，那么输出"YES,"
}
}
cout << endl;
return 0;
}
输入：
3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
对！就是判断冒号前的字母是否在冒号后的字符串中出现，大小写要区分，注意有逗号。
输出：YES,NO,YES,
（注：输入各行前后均无空格）

NOIP2016-3.
#include<iostream>
using namespace std;
int lps(string seq, int i, int j){
int len1, len2;
if (i == j)
return 1;
//当i=j时，则此时扫描到的项是一定可以放入该回文子序列中，长度贡献为1
if (i > j)
return 0;
//当i>j时，即扫描到的左边的数在右边已经扫描过了，所以该项及往后的所有项都是已经扫描过的项，长度贡献为0
if(seq[i] == seq[j]) //当扫描到相同的字符时
return lps(seq, i + 1, j - 1) + 2;
//此时这两个相同字符必定可以放入回文子序列中，长度贡献为2
len1= lps(seq, i, j - 1);
len2= lps(seq, i + 1, j);
//如果没有扫描到相同字符，则此时有两种情况，一种是此时的第i个字符对最长回文子序列的长度有贡献，另一种是此时的第j个字符对最长回文子序列的长度有贡献
if(len1 > len2)
return len1;
return len2;
//比较上面两种情况的回文子序列的长度大小，返回其中长度较大的回文子序列的长度
}
int main()
{
string seq = "acmerandacm";
int n = seq.size();
cout<< lps(seq, 0, n - 1) << endl;
return 0;
}
//对！就是计算最长回文子序列长度
输出：5

NOIP2016-4.
#include <iostream>
#include <cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
visit[node] = 1;
sum[node] = 1;
int v, maxw = 0;
for (v = 1; v <= n; v++) {
if (!map[node][v] || visit[v])
continue;
dfs(v);
sum[node] += sum[v];
if (sum[v] > maxw)
maxw = sum[v];
}
if (n - sum[node] > maxw)
maxw = n - sum[node];
weight[node] = maxw;
}
int main()
{
memset(map, 0, sizeof(map));
memset(sum, 0, sizeof(sum));
memset(weight, 0, sizeof(weight));
memset(visit, 0, sizeof(visit));
cin >> n;
int i, x, y;
for (i = 1; i < n; i++) {
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
dfs(1);
int ans = n, ansN = 0;
for (i = 1; i <= n; i++)
if (weight[i] < ans) {
ans = weight[i];
ansN = i;
}
cout << ansN << "" << ans << endl;
return 0;
}
输入：11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
对！这是图的深度优先遍历。确定哪个节点是重心，以及最大联通块包含的节点数。根据输入的节点信息画出树型图即可模拟出来。[1][2]、[2][4]、[2][5]、[2][6]，该图连接节点2有四条边，共5个节点。
输出：2 5