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

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模拟试题与解析(十五)
冲刺NOIP2010模拟试题与解析(十五)_IT/计算机_专业资料。冲刺NOIP2010模拟试题与解析(十五)NOIP 提高组复赛模拟题(一) 提高组复赛模拟题 组复赛模拟题(题目 试题名...
冲刺NOIP2010模拟试题
冲刺NOIP2010 模拟试题 模拟试题九 普及组) 冲刺 NOIP2010 模拟试题九(普及组)一、题目概览 中文名称 英文名称 可执行文件名 输入文件名 输出文件名 每个测试点...
Noip2010模拟题由朱全民老师提供2
Noip2010 模拟题由朱全民老师提供 题目名称 源文件名 输入文件 输出文件 测试点个数 时间限制 空间限制 校门外的树 tree.pas/c/cpp tree.in tree tree.out 1s...
★冲刺NOIP 2010模拟试题六
★冲刺NOIP 2010模拟试题六_调查/报告_表格/模板_实用文档。模拟题冲刺NOIP 2010 模拟试题与解析(六) 1 油滴扩展(box) 问题描述 在一个长方形框子里,最多有 ...
冲刺NOIP2010模拟试题15
冲刺NOIP2010模拟试题15_学科竞赛_初中教育_教育专区。冲刺 NOIP2010 模拟试题 15 题目 试题名称 程序文件名 输入文件名 输出文件名 时间限制 空间限制 中位数 med...
Noip2010提高组初赛试题及详细解析(C语言)
(); return 0; } 输入: 5 13579 4 2 6 10 14 输出: CCF NOIP2010 提高组(C 语言)参考答案与评分标准一、单项选择题(共 10 题,每题 1.5 分,共计 ...
NOIP2010普及组解题报告
NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书...直接上题解: T1 : two 大水题,主要有如下几种...T2 : water 还是水题 此题其实就是纯模拟,设 a...
NOIP2010模拟赛2
福建省长乐一中 Noip2010 NOIP2010 福建省长乐一中 NOIP2010 模拟赛 2 题目名称 存盘文件名 输入文件名 输出文件名 时限 内存限制 神奇的风 wind.pas wind.pas ...
NOIP2010普及组满分题解
NOIP2010普及组满分题解_IT/计算机_专业资料。【个人题解+代码】NOIP2010 普及组 首先前两题可以说非常水,第三题也是水题。第四题难度和前三题差别有点大……...
NOIP2010初赛普及组C++题目及答案
NOIP2010初赛普及组C++题目及答案_学科竞赛_高中教育_教育专区。本文是noip2010年...Noip2010提高组初赛试题... 8页 1下载券 NOIP2010初赛普及组模拟... 7页 ...
更多相关标签: