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

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-


相关文章:
冲刺NOIP2010模拟试题与解析6
冲刺NOIP2010模拟试题与解... 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP2010通知
NOIP2010题解 33页 2财富值 NOIP2010 模拟试题 4页 免费喜欢此文档的还喜欢 NOIP2010训练 38页 1财富值 冬令营讲稿 52页 免费 NOIP2010模拟题 4页 免费 NOIP...
冲刺NOIP2010模拟试题四
冲刺NOIP2010 模拟试题与解析(四)题目 题目名称 文件名 输入文件名 输出文件名...方程的解 Equation Equation.in Equation.out 1s 64M 64M 64M 64M 空间限制 1...
冲刺NOIP2010模拟试题15
冲刺NOIP2010模拟试题15_学科竞赛_初中教育_教育专区。冲刺 NOIP2010 模拟试题 15 题目 试题名称 程序文件名 输入文件名 输出文件名 时间限制 空间限制 中位数 med...
冲刺NOIP2010模拟试题
冲刺NOIP2010模拟试题_公务员考试_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 冲刺NOIP2010模拟试题_公务员考试_资格考试/认证_教育专区。...
冲刺NOIP2010模拟试题
冲刺NOIP2010 模拟试题 模拟试题九 普及组) 冲刺 NOIP2010 模拟试题九(普及组)一、题目概览 中文名称 英文名称 可执行文件名 输入文件名 输出文件名 每个测试点...
NOIP2010 模拟试题
冲刺NOIP2010模拟试题与解... 11页 免费 冲刺NOIP2010冲刺模拟试题 4页 5财富...试题四 贪婪大陆 【题目描述】 面对蚂蚁们的疯狂进攻,小 FF 的 Tower defence...
NOIP2010初赛练习(4)
NOIP2010训练 38页 1财富值 NOIP2010考前训练题1 3页 2财富值 NOIP2010模拟4 5页 5财富值 冲刺NOIP2010模拟试题四 3页 5财富值 冲刺NOIP2010模拟试题与解.....
冲刺NOIP2010模拟试题六
冲刺NOIP2010 模拟试题六 (提高组 复赛) 试题: 1.油滴扩展 油滴扩展 【问题描述】 问题描述】 问题描述 在一个长方形框子里,最多有 N(0≤N≤6)个相异的...
NOIP2010普及组解题报告
NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书...直接上题解: T1 : two 大水题,主要有如下几种...T2 : water 还是水题 此题其实就是纯模拟,设 a...
更多相关标签: