NOIP 提高组 初赛 四、阅读程序写结果 习题集（三）NOIP2004-NOIP2005
NOIP 提高组 初赛 四、阅读程序写结果 习题集（三）NOIP2004-NOIP2005
1.第十届(NOIP2004)
问题（原文是pascal,按题意，本人改写成C，C++版本）：
1.
//2004.4.1
#include <stdio.h>
int main(){
int u[4];
int a,b,c,x,y,z;
scanf("%d %d %d %d",&u[0],&u[1],&u[2],&u[3]);
a=u[0]+u[1]+u[2]+u[3]-5;
b=u[0]*(u[1]-u[2]/u[3]+8);
c=u[0]*u[1]/u[2]*u[3];
x=(a+b+2)*3-u[(c+3)%4];
y=(c*100-13)/a/(u[b%3]*5);
if((x+y)%2==0)
z=(a+b+c+x+y)/2;
z=(a+b+c-x-y)*2;
printf("%d\n",x+y-z);
}
//输入：2 5 7 4
2.
//2004.4.2
#include <stdio.h>
int number,ndata,sum;
int data[100];//data[101] pascal
void solve(int s,int sign,int n){
int i;
for(i=s;i<ndata;i++){//i<=ndata pascal
sum+=sign*(number/n/data[i]);//number/(n*data[i]) pascal
solve(i+1,-sign,n*data[i]);
}
}
int main(){
int i;
scanf("%d %d",&number,&ndata);
sum=0;
for(i=0;i<ndata;i++)//for(i=1;i<=ndata;i++) pascal
scanf("%d",&data[i]);
solve(0,1,1);//solve(1,1,1); pascal
printf("%d\n",sum);
return 0;
}
//输入：1000 3 5 13 11
3.
//2004.4.3
#include <stdio.h>
char c[3][200];
int s[10];
int m,n;
void numara(){
int cod;
int i,j,nr;
for(j=0;j<n;j++){
nr=0;
cod=1;
for(i=0;i<m;i++)
if(c[i][j]=='1'){
if(!cod){
cod=1;
s[nr]++;
nr=0;
}
}else
if(cod){
nr=1;
cod=0;
}else
nr++;
if(!cod)
s[nr]++;
}
}
int main(){
int i;
scanf("%d %d\n",&m,&n);//scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
gets(c[i]);//scanf("%s",c[i]);
numara();
for(i=0;i<n;i++)//原文for i := 1 to m do pascal有误，应改成 for i := 1 to n do
if(s[i]!=0)
printf("%d %d ",i,s[i]);
return 0;
}
//输入：
//3 10
//1110000111
//1100001111
//1000000011
4.
//2004.4.4 该题pascal转C、C++要注意
#include <stdio.h>
const int u[3]={1,-3,2};
const int v[2]={-2,3};
int n,sum;
int g(int n){
int i,sum;
sum=0;
for(i=1;i<=n;i++)
sum+=u[i%3]*i;
return sum;
}
int main(){
int i;
sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
sum+=v[i%2]*g(i);
printf("%d\n",sum);
return 0;
}
//输入：103
问题解答：
1.
该题比较简单，顺着程序执行就可以了，
答案：263
该题考点，数组，除，模运算。
1简单
2.比较难得递归的题目一次性做对，很是高兴，该题难度中等，是练递归的好题目。
思考过程如下：
答案：328
2中等
3.输出怎么跟想的不一样，跟踪了程序，才发现，敲代码时，缩进格式影响了阅读。
本题找不到s[i]初始化，虽然编译器默认初始化为0，出题者的疏忽吧。
思考过程如下：
写到i=5，就可以大致猜出，在统计列上连续0的个数，s[2]表示连续2个0，s[3]表示连续3个0，s[1]表示单独0。
答案：1 4 2 1 3 3
3中等
4.
本题是一个三岔路，找g(i)规律，找sum规律，还是找g(i)和sum的规律。
本题关键是找g(i)的规律。经验告诉我们，大批量的数据是有规律的，等差，等比，或者能写出递推公式。
http://wenku.baidu.com/link?url=oTA4VH-47iUcjYM_BiQwVqp5-XqZ0ZbUfJmr_TL_F87-fvrHJwRNgK9V-uT5ISZiy3ubVtYzeQafrzz82qWTPc2kYPy-LTpvgC6nZ6x_oZC介绍得比较详细。
算出g(1),g(2),g(3)......g(16)值
-3,1,4,-8,2,8,-13,3,12,-18,4,16,-23,5,20,-28
发现
-3,-8,-13,-18,-23,-28
1,2,3,4,5
4,8,12,16,20
三组等差数列
sum=3*(g(1)+g(3)+g(5)+......+g(103))-2*(g(2)+g(4)+g(6)+......+g(102))
这个题目能做出，数学水平很不一般啊，一般人没有耐心分析到这个程度。
4难
2.第十一届(NOIP2005)
问题
1.
//2005.4.1
#include <stdio.h>
int main(){
int a,b,c,p,q;
int r[3];
scanf("%d%d%d",&a,&b,&c);
p=a/b/c;
q=b-c+a+p;
r[0]=a*p/q*q;
r[1]=r[0]*(r[0]-300);
if(3*q-p%3<=r[0]&&r[2]==r[2])
r[1]=r[r[0]/p%2];
else
r[1]=q%p;
printf("%d\n",r[0]-r[1]);
return 0;
}
//输入：100 7 3
2.
//2005.4.2
#include <stdio.h>
#include <stdlib.h>
int a[50];
int n,sum;
void work(int p,int r){
int i,j,temp;
if(p<r){
i=p-1;
for(j=p;j<r;j++){
if(a[j]>=a[r]){
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
work(p,i);
work(i+2,r);
}
}
int main(){
int i;
sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
work(0,n-1);
for(i=0;i<n-1;i++)
sum+=abs(a[i+1]-a[i]);//abs stdlib.h
printf("%d\n",sum);
return 0;
}
//输入：10 23 435 12 345 3123 43 456 12 32 -100
3.
//2005.4.3
#include <stdio.h>
#include <string.h>
int main(){
char str[60];
int len,i,j;
int nchr[26];
char mmin;
mmin='z';
scanf("%s",str);
len=strlen(str);
for(i=len-1;i>=1;i--)
if(str[i-1]<str[i])
break;
if(i==0){
printf("No result!\n");
return 0;
}
for(j=0;j<i-1;j++)
putchar(str[j]);
memset(nchr,0,sizeof(nchr));
for(j=i;j<len;j++){
if(str[j]>str[i-1]&&str[j]<mmin)
mmin=str[j];
nchr[str[j]-'a']++;
}
nchr[mmin-'a']--;
nchr[str[i-1]-'a']++;
putchar(mmin);
for(i=0;i<26;i++)
for(j=0;j<nchr[i];j++)
putchar(i+'a');
putchar('\n');
return 0;
}
//输入：zzyzcccbbbaaa
4.
//2005.4.4
//该程序无法运行， 但可以根据程序来推测答案
#include <stdio.h>
long g(long k){
if(k<=1)
return k;
return (2002*g(k-1)+2003*g(k-2))%2005;
}
int main(){
long n;
scanf("%ld",&n);
printf("%ld\n",g(n));
return 0;
}
//输入：2005
问题解答：
1.
该题比较简单，按顺序执行即可。p=100/7/3=4
q=7-3+100+4=108
r[0]=100*4/108*108=324
r[1]=324*(324-300)=7776
3*108-4%3<=324 r[2]==r[2]
r[1]=r[324/4%2]=r[1]=7776
r[0]-r[1]=324-7776=-7452
答案：-7453
2.
进行程序模拟：
答案：3223
2中等，递归。
3.思考过程如图所示：
答案：zzzaaabbbcccy
3简单
4.试了g(2005),g(2004),g(0),g(1),g(2),g(3),g(4)发现吃不消做。
搜索http://wenku.baidu.com/view/94eb85d076eeaeaad1f3301c.html摘抄如下：
答案：31
2016-12-18 22:30
提供http://tieba.baidu.com/p/1399841177做法