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做法