NOIP 提高组 初赛 四、阅读程序写结果 习题集（八）NOIP2012-NOIP2013
NOIP 提高组 初赛 四、阅读程序写结果 习题集（八）NOIP2012-NOIP2013
1.第十八届(NOIP2012)
问题：
1.
//2012.4.1
#include <stdio.h>
int main(){
int n,i,temp,sum;
int a[100];
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&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];
printf("%d\n",sum/(n-2));
return 0;
}
//输入：8
//40 70 50 70 20 40 10 30
2.
//2012.4.2
#include <stdio.h>
int gcd(int a,int b){
if(a%b==0)
return b;//网上流传的pascal有些此处return 0;
else
return gcd(b,a%b);
}
int main(){
int n,i,ans;
scanf("%d",&n);
ans=0;
for(i=1;i<=n;i++)
if(gcd(n,i)==i)
ans++;
printf("%d\n",ans);
return 0;
}
//输入：120
3.
//2012.4.3
#include <stdio.h>
const int size=20;
int data[20];
int n,i,h,ans;
void merge(){
data[h-1]+=data[h];
h--;
ans++;
}
int main(){
scanf("%d",&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();
}
printf("%d\n",ans);
return 0;
}
//(1)
//输入：8
//(2)
//输入：2012
4.
//2012.4.4
#include <stdio.h>
#include <string.h>
int left[20],right[20],father[20];
char s1[20],s2[20],s3[20];
int n,ans,tmpLen;
void check(int x){//本题pascal写法与C差异较大，且有些错误
if(left[x]>=0)
check(left[x]);
tmpLen=strlen(s3);
s3[tmpLen]=s1[x];
s3[tmpLen+1]='\0';
if(right[x]>=0)
check(right[x]);
}
void calc(int x,int dep){
ans=ans+dep*(s1[x]-'A'+1);
if(left[x]>=0)
calc(left[x],dep+1);
if(right[x]>=0)
calc(right[x],dep+1);
}
void dfs(int x,int th){
if(th==n){
s3[0]='\0';
check(0);
if(strcmp(s2,s3)==0){
ans=0;
calc(0,1);
printf("%d\n",ans);
}
return;
}
if(left[x]==-1&&right[x]==-1){
left[x]=th;
father[th]=x;
dfs(th,th+1);
father[th]=-1;
left[x]=-1;
}
if(right[x]==-1){
right[x]=th;
father[th]=x;
dfs(th,th+1);
father[th]=-1;
right[x]=-1;
}
if(father[x]>=0)
dfs(father[x],th);
}
int main(){
scanf("%s",s1);
scanf("%s",s2);
n=strlen(s1);
memset(left,-1,sizeof(left));
memset(right,-1,sizeof(right));
memset(father,-1,sizeof(father));
dfs(0,1);
return 0;
}
//输入：ABCDEF
//BCAEDF
问题解答：
1.就算不熟悉冒泡排序，此题也挺简单，直接模拟，过程如下：
看起来数据量挺大，但写起来挺快，最多5分钟，肯定好了，
答案：41
1简单
2.作了模拟，如图所示：
发现该程序意图是统计n与i能整除的数量。
能被120整除的数：1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120共计16个。
答案：16
该题一不小心，就容易漏数。
2中等
想到一个好办法：
120/1=120,120/2=60,120/3=40,120/4=30,120/5=24,120/6=20,120/8=15,120/10=12.
此种办法，一个不漏，
1,120,2,60,3,40,4,30,5,24,6,20,8,15,10,12.一共16个。
2简单
3.输入8思考过程如下：
答案：7
难度中等，能将输入8做对，水平已经不错，证明具有相当的跟踪程序的水平。此题难在while()而不是if()。
输入2012
参考：https://zhidao.baidu.com/question/580345391.html
n值 数组有效元素（包括转换前和转换后）
i=2 1,1->2
i=3 2,1
i=4 2,1,1->2,2->4
i=5 4,1
i=6 4,1,1->4,2
i=7 4,2,1
i=8 4,2,1,1->4,2,2->4,4->8
至此次转换次数（->）为7次，即ans=7
i=9 8,1
i=10 8,1,1->8,2
i=11 8,2,1
i=12 8,2,1,1->8,2,2->8,4
i=13 8,4,1
i=14 8,4,1,1->8,4,2
i=15 8,4,2,1
i=16 8,4,2,1,1->8,4,2,2->8,4,4->8,8->16
由上可知，数组有效元素的和为n，当n可以表示为2(x)时，转换次数为2(0)+2(1)+2(2)+2(3)+...+2(x-1)
当i从1变到1024时，转换次数为2(0)+...+2(9)=1023
当i从1变到2048时，转换次数为2(0)+...+2(10)=2047，但是i变不到2048，只变到2012（n的值）
所以，最终数组的有效元素是：
i=2012 1024,512,256,128,64,16,8,4 //有效数组元素的和为2012（此处不清楚，还需消化）
所以，当n=2012时，最终的结果是：
t(1024)+t(512)+t(256)+t(128)+t(64)+t(16)+t(8)+t(4) //t(x)表示从数组初始状态变到x状态
=1023+511+255+127+63+15+7+3=2004
答案：2004
此处难度：难 考试中先跳过。
4.程序跟得晕乎乎的，暂时搁置，等实力强劲时再来。
答案：55
1.第十九届(NOIP2013)
问题：
1.
//2013.4.1
#include <stdio.h>
#include <string.h>
const int SIZE=100;
int main(){
int i,n;
char str[SIZE];
int isPlalindrome;
scanf("%s",str);
n=strlen(str);
isPlalindrome=1;
for(i=0;i<n/2;i++){
if(str[i]!=str[n-i-1])
isPlalindrome=0;
}
if(isPlalindrome)
printf("Yes\n");
else
printf("No\n");
}
//输入：abceecba
2.
//2013.4.2
#include <stdio.h>
int main(){
int a,b,u,v,i,num;
scanf("%d%d%d%d",&a,&b,&u,&v);
num=0;
for(i=a;i<=b;i++){
if(i%u==0||i%v==0)
num++;
}
printf("%d\n",num);
return 0;
}
//输入：1 1000 10 15
3.
//2013.4.3
#include <stdio.h>
const int SIZE=100;
int main(){
int n,ans,i,j;
int height[SIZE],num[SIZE];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&height[i]);
num[i]=1;
for(j=0;j<i;j++)
if(height[j]<height[i]&&num[j]>=num[i])
num[i]=num[j]+1;
}
ans=0;
for(i=0;i<n;i++)
if(num[i]>ans)
ans=num[i];
printf("%d\n",ans);
return 0;
}
//输入：8
// 3 2 5 11 12 7 4 10
4.
//2013.4.4
#include <stdio.h>
#include <string.h>
const int SIZE=100;
int n,m,p,count;
int a[SIZE][SIZE];
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 ans,x,y,i,j;
memset(a,0,sizeof(a));
scanf("%d%d%d",&n,&m,&p);
for(i=1;i<=p;i++){
scanf("%d%d",&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;
}
printf("%d\n",ans);
return 0;
}
//输入：
/*
6 5 9
1 4
2 3
2 4
3 2
4 1
4 3
4 5
5 4
6 4
*/
问题解答：
1.思考过程如图所示：
直接跟踪程序，此题两三分钟即可做好。
答案：Yes
1简单
2.思考过程如图所示：
答案：133
耗时：两三分钟
3.思考过程如图所思：
num[i]>ans这段代码是在num中找最大的数。
很快能得出答案：4
耗时：5分钟
3中等
4.思考过程如图所示：
跟踪程序，发现colour函数核心处理部分，如图所示：
很快发现该函数是统计同一区域0的个数。
该程序意图明了：统计同一区域0的个数，找出最多0的个数。
答案：7
耗时：5分钟
4中等
2016-12-31 12:04