资源描述：
《noip2013普及组解题报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、N0lp2013普及组解题报告By绍兴文理学院附中任轩笛计数问题(count.pas/c/cpp)TimeLimit:1OOOMsMemoryLimit:131072K昇法一这是一题送分题。初看这道题，你想到了什么？对了，NOIp2010普及组《数字统计》。几乎就是一模一样的题目。一看数据范围，n不是很大，直接上线性复杂度的扫描算法。算法具体就是对于每一个数字转成字符畢后扫描字符畢，统计数字个数即可。PASCAL代码见此。时间效率0(N)空间效率0(1)算法二如果对时间效率实在不放心，也可以用数学方法来完成
2、。但相对复杂了一点。通常NOIp普及组的第一题用不着太高科技的算法。时间效率0(1)空间效率0(1)varx,i,j,k,l,m,n,Ans:Longint;s:Ansistring;BeginAssign(input,▼count.in1);Assign(output,1count.out1);Reset(input);rewrite(output);Readln(n,x);Fori:=1toNdoBeginstr(i,s);Forj:=1toLength(s)doIford(s[j])-48=xthen
3、Inc(Ans);End;writeln(Ans);Close(input);Close(output);End•表达式求值(expr-pas/c/cpp)TimeLimit:1OOOMsMemoryLimit:131072K昇法一表达式求值的题目己经堪称经典了。如果读者尝试过NOIp2005提高组《等价表达式》，那么这道题目其实非常轻松。对于一般的(甚至更复杂的)表达式求值的题目，我们一般采用如下方法：1、设W个栈：符号栈与数字栈；2、扫描表达式，遇到数字则进栈，遇到符号则转第3步，扫描完毕转第4步；3、
4、遇到符号：首先将符号桟中优先级比当前符号大的都弹出，每次取出数字栈顶两个元素，求值后压入数字栈。然后将当前符号压入符号栈。转第2步；4、扫描完毕后数字栈顶便是所求的值。对于本题，只要输出最后4位，由于只包含“+”和“*”，因此可以边处理边mod,甚至根本不用设置栈，直接先算出所有“*”出的值，然后依次相加即可，只不过没有设置栈的方法简单。PASCAL代码见此。时间效率O(Len)//其中Len力表达式的位数空间效率O(Len)代码_算法一vari,j,k,l,m,n,ToTm,ToTf:Longint;s,
5、Ans:Ansistring;03Tmp,Tmpl,Tmp2:Int64;04Dis:array[1ofLongint;05Sm:array[0••200000]ofInt64;06sf:array[0..200000]ofchar;FunctionMath(c:char):Boolean;beginExit((c>=*0')and(c<='9'));End;ProcedureDoit(S:Ansistring);vari,j,k:Longint;ch:char;Begin17i:=1;Whilei<=Le
6、ngth(s)doBegin20IfMath(s[i])thenBegin22Tmp:=0;23WhileMath(s[i])do24Begin25Tmp:=Tmp*10+ord(s[i])-48;26Inc(i);27End;Inc(ToTm);Sm[ToTM]:=Tmpmod10000;29EndElseBeginch:=s[i];WhileDis[sf[ToTf]]<=Dis[ch]doBegin34Tmpl:=Sm[ToTm];35Tmp2:=Sm[ToTm-1];36IfSf[ToTf]=*+*t
7、henTmp:=Tmpl+Tmp2ElseTmp:=Tmpl*Tmp2;38Sm[ToTm-1]:=Tmpmod10000;39Sm[ToTm]:=0;40Dec(ToTm);41Sf[Totf]:=!1;42Dec(ToTf);End;44Inc(ToTf);45Sf[ToTf]:=ch;44Inc(i);45End;46End;49End;Begin52Assign(input,'expr•in1);53Assign(output,*expr•out’)；Reset(input〉；Rewrite(out
8、put);Readln(s);57S:=S+*@，；58Dis['*’]:=l;59Dis[▼+▼]:=2;60Dis[’@’]:=3;61Dis[**]:=4;62Sf[0]:=f*;63Doit(S);64sm[1]:=sm[1]mod10000;65str(Sm[1],Ans);Writeln(Ans);67Close(input);68Close(output);End.小朋友的数字(number.pas
