NOIP2011普及组第十七试题(2)

int main() {

int i,j,k1,k2; bool good ,haveAns;

cin>>n1>>m1; for(i=1;i<=n1;i++) for(j=1;j<=m1;j++) cin>>a[i][j];

cin>>n2>>m2; for(i=1;i<=n2;i++) for(j=1;j<=m2;j++) ① ;

haveAns=false;

for(i=1;i<=n1-n2+1;i++)

for(j=1;j<= ② ;j++){ ③ ;

for(k1=1;k1<=n2;k1++)

for(k2=1;k2<= ④ ;k2++){ if(a[i+k1-1][j+k2-1]!=b[k1][k2]) good=false; } if(good){

cout<

cout<<\

return 0; }

2. (大整数开方) 输入一个正整数n（1≤n≤10100），试用二分法计算它的平方根的整数部分。

#include

NOIP2011初赛

普及组 C++ 6

#include using namespace std;

const int SIZE=200; struct hugeint{ int len,num[SIZE]; };

//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推

hugeint times(hugeint a,hugeint b) // 计算大整数a和b的乘积 {

int i,j; hugeint ans;

memset(ans.num,0,sizeof(ans.num)); for(i=1;i<=a.len;i++) for(j=1;j<=b.len;j++)

① +=a.num[i]*b.num[j]; for(i=1;i<=a.len+b.len;i++){ ans.num[i+1]+=ans.num[i]/10; ② ; }

if(ans.num[a.len+b.len]>0) ans.len=a.len+b.len; else

ans.len=a.len+b.len-1; return ans; }

hugeint add(hugeint a,hugeint b) //计算大整数a和b 的和 {

int i; hugeint ans;

memset(ans.num,0,sizeof(ans.num)); if(a.len>b.len) ans.len=a.len; else

ans.len=b.len;

for(i=1;i<=ans.len;i++){

ans.num[i]+= ③ ; ans.num[i+1]+= ans.num[i]/10; ans.num[i]%=10; }

if(ans.num[ans.len+1]>0)

NOIP2011初赛 普及组 C++ 7

ans.len++; return ans; }

hugeint average(hugeint a,hugeint b) //计算大整数a和b的平均数的整数部分 {

int i; hugeint ans; ans=add(a,b);

for(i=ans.len;i>=2;i--){

ans.num[i-1]+=( ④ )*10;

ans.num[i]/=2; }

ans.num[1]/=2;

if(ans.num[ans.len]==0) ans.len--; return ans; }

hugeint plustwo(hugeint a) // 计算大整数a加2之后的结果 {

int i; hugeint ans; ans=a;

ans.num[1]+=2; i=1;

while( (i<=ans.len)&&(ans.num[i]>=10) ){ ans.num[i+1]+=ans.num[i]/10; ans.num[i]%=10; i++; }

if(ans.num[ans.len+1]>0) ⑤ ; return ans; }

bool over(hugeint a,hugeint b) // 若大整数a>b则返回true，否则返回false {

int i;

if( ⑥ )

NOIP2011初赛 普及组 C++ 8

return false; if( a.len>b.len ) return true;

for(i=a.len;i>=1;i--){ if(a.num[i]b.num[i]) return true; }

return false; }

int main() {

string s; int i;

hugeint target,left,middle,right; cin>>s;

memset(target.num,0,sizeof(target.num)); target.len=s.length(); for(i=1;i<=target.len;i++)

target.num[i]=s[target.len-i]- ⑦ ; memset(left.num,0,sizeof(left.num)); left.len=1; left.num[1]=1; right=target; do{

middle=average(left,right); if(over( ⑧ )) right=middle; else

left=middle;

}while(!over(plustwo(left),right) ); for(i=left.len;i>=1;i--) cout<

NOIP2011初赛 普及组 C++ 9