当前位置:首页 >> 高中教育 >>

2010NOIP模拟测试与题解


1、有故障的打字机 ( typewrt.pas/c/cpp )
【问题描述】 问题描述】 一台打字机准备将 1 到 10n 那的数依次打出。在打印过程中,这台打字机出现了一个故障:数字“3” 打不出来。因此,所有含有数字“3”的数都没有被正确地打出。试问没有被正确打出的数一共有多少个。 输入文件】 【输入文件】 输入文件 typewrt.in 的第一行是一个正整数 n。

( n<=1000 ) 输出文件】 【输出文件】 输出文件 typewrt.out 的第一行也是唯一的一行应输出从 1 到 10n 这些数中不能被正确打印的数的 个数。 【输入样例】 输入样例】 2 输出样例】 【输出样例】 19 #include <fstream> using namespace std; ifstream fin("typewrt.in"); ofstream fout("typewrt.out"); int a[1005],b[1005]; int alen,blen; int n; void mup(int x) {int i,w=0; for(i=1;i<=alen+1;i++) {a[i]=a[i]*x+w; w=a[i]/10; a[i]%=10; } if(a[alen+1]>0) alen++; } void jian() {int i,j; for(i=blen;i>=1;i--) {b[i]-=a[i]; j=i; while(b[j]<0) {b[j]+=10; b[++j]--;} } while(b[blen]==0) blen--; } int main() {int i; fin>>n; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); b[n+1]=1; a[1]=1; blen=n+1; alen=1; for(i=1;i<=n;i++) mup(9); jian(); for(i=blen;i>=1;i--) fout<<b[i]; return 0; }

2、最大约数和 ( maxsum.pas/c/cpp )
【问题描述】 问题描述】 选取和不超过 S 的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入文件】 【输入文件】 输入文件 maxsum.in 输入一个正整数 S。(S<=1000)

-1-

【输出文件】 输出文件】 输出文件 maxsum.out 仅一行包含一个整数,输出最大的约数之和。 输入样例】 【输入样例】 11 输出样例】 【输出样例】 9 【样例说明 (无需输出)】 样例说明 无需输出) 样例 取数字 4 和 6,可以得到最大值(1+2)+(1+2+3)=9。 #include <fstream> using namespace std; ifstream fin("trunc10.in"); ofstream fout("trunc10.out"); unsigned int m[1001][1001]={0}; unsigned int sumgcd(unsigned int i) { unsigned int j,sum=0; for(j=1;j<=i/2;j++) if(i%j==0)sum+=j; return sum; } unsigned int mymax(unsigned int x,unsigned int y) { if(x>y)return x; else return y; } int main() { unsigned int w[1001]={0}, v[1001]={0} ; unsigned int s,i,j; fin>>s; fin.close(); for(i=1;i<s;i++) { w[i]=i; v[i]=sumgcd(i); } for(i=1;i<=s-1;i++) for(j=1;j<=s;j++) if(j<w[i])m[i][j]=m[i-1][j]; else m[i][j]=mymax(m[i-1][j],m[i-1][j-w[i]]+v[i]); fout<<m[s-1][s]; fout.close(); return 0; }

-2-

3、阶乘问题( Fac) 阶乘问题( Fac) (fac fac.pas/c/cpp ) fac
【问题描述】 问题描述】 问题描述 对于小于 25000 的自然数 n,求阶乘 n!,(n-1)!,(n-2)!...3!,2!,1!最右边的非零数之和。 例如:当 n=5 时,5!=120,最右边非零数为 2;4!=24,最右边非零数为 4;3!=6,最右边非零数为 6; 2!=2,最右边非零数为 2;1!=1,最右边非零数为 1,则其最右边的非零数之和为 2+4+6+2+1=15。 输入文件】 【输入文件】 (fac.in) 一个自然数 N(0<N<25000) 输出文件】 【输出文件】 (fac.out) 对应的 N 个阶乘数的最右边的非零数之和。 样例输入】 【样例输入】 5 样例输出】 【样例输出】 15 #include <fstream> using namespace std; ifstream fin ("fac.in"); ofstream fout ("fac.out"); main(){ int c[10000]; int n,s,k,i,j,t,m,y; fin>>n; s=0; k=0; c[k]=1; s+=c[0]%10; for (i=2;i<=n;i++) { t=0; for (j=0;j<=k;j++) { y=c[j]*i+t; c[j]=y%10000; t=y/10000; } if (t>0) c[++k]=t; j=0; while (c[j]==0) j++; m=c[j]; while (m%10==0) m/=10; s+=m%10; } fout<<s; }

4、出栈序列统计 、 (stack.pas/c/cpp )
【问题描述】 问题描述】 栈是常用的一种数据结构,有 n 个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知 道栈的操作有两种:push 和 pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操 作, 由一个操作序列可以得到一系列的输出序列。 请你编程求出对于给定的 n, 计算并输出由操作数序列 1, 2,…,n,经过一系列操作可能得到的输出序列总数。 输入】 输出】 【输入】 【输出】 就一个数 n(1≤n≤1000)。 一个数,即可能输出序列的总数目。 样例】 【样例】 stack.in stack.out 3 5
-3-

【算法分析】 算法分析】 先了解栈的两种基本操作,进栈 push 就是将元素放入栈顶,栈顶指针上移一位,等待进栈队列也上移 一位,出栈 pop 是将栈顶元素弹出,同时栈顶指针下移一位。 #include <fstream> using namespace std; ifstream fin ("stack.in"); ofstream fout ("stack.out"); int c[10000]; int n,i,j,k,ys,len; int main(){ fin>>n; for (i=0;i<=n;i++) c[i]=0; c[1]=1;len=1; for (i=2*n;i>=n+2;i--) { for (j=1;j<=len;j++) c[j]=c[j]*i; for (j=1;j<=len+4;j++) { c[j+1]=c[j+1]+c[j]/10; c[j]=c[j]%10; } 5、流感会结束吗 、 (flu.pas/c/cpp ) 【问题描述】 问题描述】 学校一共有 n 个学生。这 n 个学生里一共有 m 对朋友关系。 在流感发作期, 每个健康学生都要看望当天他生病的朋友 (如果有的话) 并在第二天被传染上疾病 , (除 非他在免疫期内) ; 每个生病的学生在第二天都会痊愈,并在这一天具有免疫性。从第三天起,看望生病的朋友将再次使 他染上流感。 初始时(第一天) ,只有一个学生患有流感。试问多少天后流感会自动结束。 输入文件】 【输入文件】 输入文件 flu.in 中第一行输入两个正整数 n 和 m。 (n,m<=100 000) 接下来 m 行每行两个正整数 x,y,表示编号为 x 的学生和编号为 y 的学生是一对朋友。输入数据保 证每一对朋友关系只描述一次。 最后一行输入一个正整数,代表初始时患有流感的学生的编号。 输出文件】 【输出文件】 输出文件 kitty.out 以一行的形式输出,如果流感永远不会结束,请输出-1,否则输出多少天后流 感会结束。答案保证不超过 2 000 000 000。 样例输入】 【样例输入】 4 4 1 2 2 3 3 4
-4-

} len=len+5; while (c[len]==0) len--; } for (i=n;i>=2;i--) { ys=0; for (j=len;j>=1;j--) { k=c[j]; c[j]=(k+ys*10)/i; ys=(k+ys*10)%i; } while (c[len]==0) len--; } for (i=len;i>=1;i--) fout<<c[i];

2 4 1 【样例输出】 样例输出】 3 【样例说明 样例说明】 样例说明 第一天 1 号学生生病,2 号学生访问他; 第二天 2 号学生生病,其它三个学生访问他,由于 1 号处于免疫期,未患流感; 第三天 3、4 号学生生病,2 号学生访问他们。 第四天 3、4 号学生痊愈,流感结束。 #include <cstdio> using namespace std; int n,m,a[100000][2],b[100001],s,temp; int main() { freopen("flu.in","r",stdin); freopen("flu.out","w",stdout); int j,k; scanf("%d %d",&n,&m); for(j=0;j<m;j++) scanf("%d %d",&a[j][0],&a[j][1]); for(j=0;j<=n;j++) b[j]=0; scanf("%d",&b[0]); b[b[0]]=1; s=0; while(1) { for(j=1;j<=n;j++) if(b[j]==1) for(k=0;k<m;k++) { if(a[k][0]==j&&b[a[k][1]]==0) b[a[k][1]]=2; if(a[k][1]==j&&b[a[k][0]]==0) b[a[k][0]]=2; } temp=0; for(j=1;j<=n;j++) { if(b[j]==1) { b[j]=-1; continue; } if(b[j]==2) { temp=1; b[j]=1; continue; } if(b[j]==-1) { b[j]=0; continue; } } s++; if(temp==0) break; for(j=1;j<=n;j++) if(b[j]==2&&j!=b[0]) break; if(j<=n) { printf("-1\n"); return 0; } } printf("%d\n",s); return 0; }

-5-


相关文章:
2010NOIP模拟测试与题解
备战2010NOIP举行的模拟测试与相应题解备战2010NOIP举行的模拟测试与相应题解隐藏>> 1、有故障的打字机 ( typewrt.pas/c/cpp )【问题描述】 问题描述】 一台打...
冲刺NOIP2010模拟试题与解析(一)
冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育...equation.out 有且只有一行,为方程的正整数解组数...小学假期趣味题目综合 小学四年级趣味数学题文档...
冲刺NOIP2010模拟试题与解析(一)
模拟试题与解析 试题与解析( 冲刺 NOIP2010 模拟试题与解析(一)题目(提高组时间:3 个小时) 难易指数:★★★ 题目名称题目程序名 淘汰赛制 种树 方程的解 物流...
清北学堂NOIP2010模拟试题与详细解析(13)
解开密码的第一道工序就是解压缩密码,外 星人对于连续的若干个相同的子串“x...冲刺NOIP2010模拟试题与... 8页 免费 清北学堂模拟题一解析 115页 1下载券喜欢...
NOIP2010模拟试题与解析
冲刺NOIP2010模拟试题与解... 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
冲刺NOIP2010模拟试题与解析(十五)
冲刺NOIP2010模拟试题与解析(十五)_IT/计算机_专业资料。冲刺NOIP2010模拟试题与解析(十五)NOIP 提高组复赛模拟题(一) 提高组复赛模拟题 组复赛模拟题(题目 试题名...
NOIp2010题解程序
NOIp2010题解程序_初一政史地_政史地_初中教育_教育专区。NOIp2010题解程序源...后一阶段是在寒假中了,上了两个星期,模拟考试和知识讲解交替进行。每一天 大概...
冲刺NOIP2010模拟试题与解析6
冲刺NOIP2010模拟试题与解... 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
冲刺NOIP2010模拟试题与解析(二)
冲刺NOIP2010模拟试题与解析(二)_IT/计算机_专业资料。冲刺NOIP2010模拟试题与解析(二)NOIP 提高组复赛模拟题(四) 提高组复赛模拟题 组复赛模拟题(题目 试题名称...
冲刺NOIP2010模拟试题15
冲刺NOIP2010模拟试题15_学科竞赛_初中教育_教育专区。冲刺 NOIP2010 模拟试题 15...以下 Q 行,每行一个询问 X 和 Y,如题意所诉。 【输出格式】 对于每个...
更多相关标签:
noip2010测试数据 | noip2010提高组复赛 | noip2016测试数据 | noip2010 | noip模拟赛 | noip2016复赛测试数据 | noip2010引水入城 | noip2013测试数据 |