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

NOIP提高组初赛历年试题及答案阅读题篇
NOIP提高组初赛历年试题及答案阅读题篇
阅读程序写结果〔共4 题，每题8 分，共计32 分〕
阅读程序的最好方法并非是依次从头到尾。程序不像迷语，我们无法从末尾几页找到答案，也不像一ns<<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
NOIP2022-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
NOIP2022-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
NOIP2022-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
NOIP2022-3