《NOIP2013参赛总结.doc》由会员分享，可在线阅读，更多相关《NOIP2013参赛总结.doc（25页珍藏版）》请在金锄头文库上搜索。
1、NOIP2013参赛总结安阳市七中常可一、 题解1、 count这道题其实并不难，不过是简单的模拟。那些做不出来的真不知道是怎么学的。程序：program count;vars:string;c:char;i,j,n,k,sum:longint;beginassign(input,count.in);reset(input);assign(output,count.out);rewrite(output);readln(n,j);c:=chr(j+48);for i:=1 to n dobeginstr(i,s);for k:=1 to length(s) do if sk=c then in
2、c(sum);end;writeln(sum);close(input);close(output);end.我的程序采用了字符串，这样可以使程序稍短一些，不过不用的话也没有问题，大家可以自己想想。2、 expr这道题不算简单，和前几年的相比还是有些难度的，标准算法是栈，当然也有很多其他的方法。一种比较好理解的是：从头开始搜索字符串，发现“+”的话把之前（我们这里的意思是从上一个加号到这一个加号，都不含加号）的字符串进行乘法运算。由于这个字串里都是乘法运算，只需类似于第一步处理加号时的运算，在搜到乘号时乘上两乘号之间的数即可。为了防止奇葩的数据，我们要在字符串后加上一个“+”，在每个加号前都加
3、上一个“*”。举个例子吧：1*2*3*4这个字串里没有加号，程序会因搜不到加号而得不出结果。因此，要先在末尾加一个“+”，变成这样：1*2*3*4+这样程序搜到加号后，就会正常的运算。乘号的道理是一样的。接下来我们模拟一下程序的执行过程（以样例为标准）：1+1234567890*1 1、添加号，变成1+1234567890*1+ 2、添乘号，变成1*+1234567890*1*+ 3、搜到第一个加号，加号前的字串是1*，乘法运算得到1，累加变量+1 4、搜到第二个加号，加号前的字串是1234567890*1*，乘法运算得到7890，累加变量+7890 5、结束，输出累加变量7891。 当然，添
4、加乘号的工作也可以在大循环中进行，可以让代码短一点。程序：program expr;vars,q,m,a:ansistring;i,j,k,l,sum,ls,ls2:longint;beginassign(input,expr.in);reset(input);assign(output,expr.out);rewrite(output);readln(s);s:=s+;j:=1;for i:=1 to length(s) dobeginif si=+ then begin k:=1; l:=k; ls2:=1; a:=a+*; repeat while (ak*) do inc(k); m:
5、=copy(a,l,k-l); val(m,ls); ls:=ls mod 10000; ls2:=(ls2*ls) mod 10000; inc(k); l:=k; until klength(a);sum:=(sum+ls2) mod 10000;a:=;endelse a:=a+si;end;writeln(sum);close(input);close(output);end.3、 number这题其实不难，考验的就是读题的认真程度。我就因为少看了两个字丢了90分啊首先是特征值的计算。这个特征值是连续若干个（最少有一个）小朋友手上的数字之和的最大值，既然是连续的，我们可以用模拟的方法，
6、把第几个到第几个的数值都算一遍，然后比较，就像这样（样例）：12345112323653410974515141295横着的为起点，竖着的为终点，那表中的就是从横的哪个数开始，一直到竖着的那个数之和。所以每个数的特征值就是起点和终点都不大于它的所有数中的最大值。所以1的特征值为1，2的为3,3的为6,4的为10,5的为15。这个数据太特殊了，我们换一个有正有负的（就是第一组数据）：-409-40197-96-301-409-409-401-810-40197-713-30497-96-809-4001-96-301-1110-701-300-397-301所以-409的特征值为-409，-40
7、1的特征值为-401,97的特征值为97，-96的特征值为97，-301的特征值为97。这种算法比较容易实现，但有两个问题，一是空间要用二维数组，在1000000的数据下一定会爆；二是每次找最大值是n2的时间复杂度，可能超时，于是我们一定要优化。首先，我们从后往前，找到以最后一个数为终点，最大的连续区间，把这个数的特征值暂定为这个连续区间的和。然后把连续区间的起点一直到终点前的一个数的特征值暂时改为它后面一个数的特征值减它后面的一个数。然后把起点前的一个数作为终点计算。整个数组计算完后，从前到后进行扫描，确保每个数的特征值都不小于它前面那个数的特征值。什么意思呢？我们还是用这组数据：先求出-3
8、01前的最大连续子区间（97，-96，-301），和为-300，把它的特征值暂定为-300，-96的暂定为-3000-（-301）=1,97的暂定为1-（-96）=97。然后把起点前的-401作为终点，它前面的最大连续子区间为（-401），它的特征值定为-401.然后把终点定为-409,得到它的特征值暂定为-409。最后进行扫描，发现97的特征值97大于-96的特征值1，因此把-96的特征值修正为97，同理把-301的特征值修改为97。这个算法显然是正确的，至于为什么留给大家证明。特征值算好了，分数就很好算了，不需优化都是O(n)的算法，扫描一遍就行了。但是，在计算特征值的过程中，有可能会出现
9、大于maxint64的情况，所以我们要选用double来存储特征值，计算分数时可以取模。程序：program number;vara,b,c:array0.1000000 of int64;d:array1.1000000 of double;i,j,n,p,ls:longint;max:int64;sum:double;beginfillchar(a,sizeof(a),0);assign(input,number.in);reset(input);assign(output,number.out);rewrite(output);readln(n,p);for i:=1 to n do r
10、ead(ai);j:=n;while j=1 dobeginls:=j;dj:=aj;sum:=dj;for i:=j-1 downto 1 dobeginsum:=sum+ai;if sum=dj then begin dj:=sum; ls:=i; end;end;for i:=j-1 downto ls do di:=di+1-ai+1;j:=ls-1;end;for i:=2 to n do if dimax then begin max:=ci-1+bi-1; ls:=i-1; end;ci:=max;end;max:=-maxlongint;for i:=1 to n do if
11、cimax then max:=ci;writeln(max mod p);close(input);close(output);end.4、 level 这题很有水平，我是看了网上的教程才会写的。乍一看这道题，很多人都会想着是贪心或模拟，其实这两者都不能AC。标准的算法是图论算法（据说是拓扑排序，不过很好理解）。根据输入，我们可以进行构图：如果在任意一辆车次中，a是车站而b不是车站（b在这辆车的起止点之间），那么b与a之间有一条边。如果b与a之间已有一条边，那么不再添加边。拿样例2来说，我们可以画这样一个图（画的很烂）：第一辆车次中，我们可以得到这样一个图：第二辆车次中，所有的边都画上了，就
12、不用画了。第三辆车次中，我们可以得到这样一个图：我们用一个邻接矩阵表示为：123456789100000000021010110013100010001410101100150000000006100010001710001000181000100019000000000然后，由于所有车次都进行完了，开始处理。首先，我们很容易得到每个点的入度为（6,0,2,0,6,2,0,0,6），把所有起点为入度为0的边删去，把所有入度为0的点删去，得到这样一幅图：邻接矩阵表示为13569100000310101500000610101900000 再计算每个点的入度（2,0,2,0,2），重复上述操作，得到这样一幅图：显而易见，每个点入度都为0，全部删去。结束。这样，我们一共进行了3次操作，输出3。回顾整个过程，等级为1的就是第一次删去的2,4,7,8号车站，等级为2的就是第二次删去的3,6号车站，等级为3的就是第三次删去的1,5,9号车站。这样，这道题就清晰起来了，我们只要把这些描述转换为代码。当然，这个程序不是我自己写的。程序：program level;var ans,i,j,k,l,m,n,t,r:integer;w:array0.1000,0.1000of boolean;s,into,q:array0.1000of intege
