noip2015普及组题解最终.doc

noip2015普及组题解by郁庭 from宁波市镇海蛟川书院 2015年11月11日本次试题前2题比较简单，34题容易拿到部分分，但满分有难度1. 金币(coin.cpp/c/pas)【问题描述】国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。请计算在前K天里，骑士一共获得了多少金币。【输入格式】输入文件名为coin.in。输入文件只有1行，包含一个正整数K，表示发放金币的天数。【输出格式】输出文件名为coin.out。输出文件只有1行，包含一个正整数，即骑士收到的金币数。【样例输入】coin.in6【样例输出】coin.out14【输入输出样例1说明】骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到1+2+2+3+3+3=14枚金币。【数据范围】对于100%的数据，1 K 10,000。【题解】关注到K的范围是10000后，就不需要考虑数学公式，纯模拟就行，考点就是for循环了vari,j,count,n,ans:longint;beginassign(input,coin.in);reset(input);assign(output,coin.out);rewrite(output);readln(n);for i:=1 to 1000 dofor j:=1 to i dobegininc(count);inc(ans,i);if count=n then beginwriteln(ans);close(input);close(output);halt;end;end;end.2.扫雷游戏（mine.cpp/c/pas）【问题描述】扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。【输入格式】输入文件名为mine.in。输入文件第一行是用一个空格隔开的两个整数n和m，分别表示雷区的行数和列数。接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符*表示相应格子是地雷格，字符?表示相应格子是非地雷格。相邻字符之间无分隔符。【输出格式】输出文件名为mine.out。输出文件包含n行，每行m个字符，描述整个雷区。用*表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。【样例输入】3 3*？*？【样例输出】*102211*1【数据说明】对于100%的数据，1n100，1m100。【题解】行列数最多100，也就是100*100的单元格数量，一个个判断过去也就100*100*8个方向，判断边界时注意数组的下标别越界就行了。考点还是for循环哦，可以考虑使用增量数组，不过就8个方向手写也很快的。varn,m,i,j,count:longint;a:array0.101,0.101 of char;begin assign(input,mine.in);reset(input); assign(output,mine.out);rewrite(output); readln(n,m);for i:=1 to n dobeginfor j:=1 to m doread(ai,j);readln;end;for i:=1 to n do beginfor j:=1 to m doif ai,j=* then write(ai,j)elsebegincount:=0;if ai-1,j-1=* then inc(count);if ai-1,j=* then inc(count);if ai-1,j+1=* then inc(count);if ai,j-1=* then inc(count);if ai,j+1=* then inc(count);if ai+1,j-1=* then inc(count);if ai+1,j=* then inc(count);if ai+1,j+1=* then inc(count);write(count);end;writeln;end; close(input);close(output);end.3. 求和(sum.cpp/c/pas)【问题描述】一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色（用1，m当中的一个整数表示），并且写了一个数字。定义一种特殊的三元组：(x, y, z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：1. ,都是整数,= 2. = 满足上述条件的三元组的分数规定为(x+z)(+)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输出整个纸带的分数除以10,007所得的余数即可。【输入格式】输入文件名为sum.in。第一行是用一个空格隔开的两个正整数和，代表纸带上格子的个数，代表纸带上颜色的种类数。第二行有个用空格隔开的正整数，第个数字代表纸带上编号为的格子上面写的数字。第三行有个用空格隔开的正整数，第个数字代表纸带上编号为的格子染的颜色。【输出格式】输出文件名为sum.out。共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。【样例输入】6 25 5 3 2 2 22 2 1 1 2 1【样例输出】82【输入输出样例1说明】纸带如题目描述中的图所示。所有满足条件的三元组为：(1,3,5),(4,5,6)。所以纸带的分数为(1+5)(5+2)+(4+6)(2+2)=42+40=82。【数据说明】对于第1组至第2组数据，1100,15；对于第3组至第4组数据，13000,1100；对于第5组至第6组数据，1100000,1100000，且不存在出现次数超过20的颜色；对于全部10组数据，1100000,1100000,1,1100000。【题解】可以理解为n个元素每个元素有三个属性分别是数值Number、颜色和编号，对于任意两个满足2个条件的元素进行相应的统计，第1个条件其实等价于这两个元素的编号都是奇数或都是偶数，第2个条件是相同颜色值。观察数据范围我们可以发现前4组数据的n只有3000，O(N2)的算法就能拿分，直接穷举任意两个元素，这个代码非常简短的：var /预期得 40分的程序 n,m,i,j:longint; a,b:array0.100000 of qword; ans:qword;begin assign(input,sum.in);reset(input); assign(output,sum.out);rewrite(output); readln(n,m); for i:=1 to n do read(ai);readln; for i:=1 to n do read(bi);readln; for i:=1 to n do for j:=i+1 to n do if not odd(i+j) and (bi=bj) then begin ans:=(ans+(ai+aj)*(i+j) mod 10007; end; writeln(ans); close(input);close(output);end.如何避免超时呢？介绍两种满分的方法【第一种方法】从给出公式入手：（假设编号为x1，x2，x3，x4，x5的元素彼此间都符合题目要求的2个条件，其实就是它们的奇偶性相同、颜色相同）(x1+x2)(1+x2)(x1+x3)(1+x3)(x1+x4)(1+x4)(x1+x5)(1+x5)(x2+x3)(2+x3)(x2+x4)*(nu2+x4)(x2+x5)*(nu2+x5)(x3+x4)*(nu3+x4)(x3+x5)*(nu3+x5)(x4+x5)*(nu4+x5)（1）把它们展开来就能发现xi*i的数量都就是5-1=4个，如果这样的元素有N个，则有N-1个xi*i（2）然后是x1(x2+x3+ x4 +x5)+ x2(x3+x4+ x5)+x3 (x4+x5)+ x4 *x5（3）类似的1(x2+x3+x4+x5)+ 2(x3+x4+x5)+ 3(x4+x5)+ 4*x5（2）和（3）我们可以归为一类（考虑有n个符合条件的元素）（2）的推广式是Xi(xi+1+ xn）（3）的推广式是xi(Xi+1 + Xn)有了这个公式的建立，针对N个彼此颜色相同奇偶性相同的元素，可以用O(n)的时间求得题目要求的值：首先O(n)的遍历i然后是O(1)的求取(2)(3)的值：sumidi表示编号的总和，sumni表示number的总和，havidi表示1到i的编号总和，havnii表示1到i的number总和，于是(2)(3)式子中的括号部分可以用sumid-havidi、sumni-havnii来表示。那么如何挑选出这些元素，换句话说就是如何归类出颜色相同奇偶性相同的元素，我们可以用双关键字排序（颜色主关键字，奇偶性次关键字），当然还有其他方式用O(nlogn)、O(n)的排序都可以，二维数组统计颜色、奇偶性都可以，这里我采用了快速排序。最终程序的时间复杂度就是O(NlogN)const cs=10007;/预期满分程序type arr=recordx,y,id:int64; z:boolean;end;vara:array0.100001 of arr; sumid,sumni,sum,ans,tot:int64;tmpc,i,count,n,m:longint; havid,havni:int64; tmpodd:boolean;procedure deal;var j:longint;begintot:=0;havid:=0;havni:=0;/sumid，sumni表示编号、数字总和，havid,havni表示编号、数字前缀和 for j:=count downto 1 do begin inc(havid,ai-j.id);inc(havni,ai-j.x); tot:=(tot+ai-j.x*(sumid-havid)mod cs;/总和-前缀和就能得到我们想要的后缀和，题解中提取的公式运用 tot:=(tot+ai-j.id*(sumni-havni) mod cs;end;ans:=ans+tot;ans:=(sum mod cs)*(count-1)+ans) mod cs;end;procedure qsort(h,t:longint);var x,i,j:longint;tmp:arr;beginx:=random(t-h+1)+h;tmp:=ah;ah:=ax;ax:=tmp;i:=h;j:=t;tmp:=ai;while ij do beginwhile (itmp.y) or (aj.y=tmp.y) and (aj.ztmp.z) do dec(j);if ij then beginai:=aj;inc(i);end;while (ij) and (ai.ytmp.y) or (ai.y=tmp.y) and (ai.ztmp.z) do inc(i);if ij then beginaj:=ai;dec(j);end;end;ai:=tmp;if hi-1 then qsort(h,i-1);if i+1t then qsort(i+1,t);end;begin assign(input,sum.in);reset(input); assign(output,sum.out);rewrite(output); readln(n,m);randomize;for i:=1 to n do read(ai.x);readln;/表示numberfor i:=1 to n do read(ai.y);readln;/表示颜色for i:=1 to n do beginai.id:=i;ai.z:=odd(i);/奇偶end;qsort(1,n);/颜色主关键字，奇偶次关键字排序 i:=1;while i=n+1 do begin if (tmpcai.y) or (tmpoddai.z) then begin/tmpc表示上一段颜色值，tmpodd表示上一段奇偶值if count1 then deal;sumid:=ai.id;sumni:=ai.x;sum:=sumid*sumni;tmpc:=ai.y;tmpodd:=ai.z;count:=1;endelse beginsumid:=(sumid+ai.id);sumni:=(sumni+ai.x);sum:=(sum+(ai.id*ai.x);inc(count);end;inc(i);end;writeln(ans); close(input);close(output);end.【第二种方法】其实题目算式还有一种更彻底的转化：(X1+X2)(1+x2)(X1+X3)(1+X3)(X1+X4)(1+X4)(X1+X5)(1+X5)(X1+Xn)(1+Xn)(X2+X3)(2+X3)(X2+X4)*(nu2+X4)(X2+X5)*(nu2+X5)(X2+Xn)*(nu2+Xn)(Xi+Xi+1)*(nui+Xi+1)(Xi+Xn)*(nui+Xn)(Xn-1+Xn)*(nuXn-1+Xn)为了方便描述以上式子统一表示成(A+B)*(C+D)所有的A*C和B*D最终形成式(n-1)( X1 1+ Xi nui +Xn Xn)所有的B*C和A*D最终形成X1 (x2+Xn)X2(x1+ x3Xn)Xi(x1+xi-1+ xi+1Xn)Xn(x1+Xn-1)通项式为Xi(number总和- xi)=式Xi*number总和-Xi* xi+式即为xi*number总和-（N-2）*(xi* xi)n项求和后就是(X总和*number总和)-(N-2)*(x1* x1+ xn* n)程序如下：const cs=10007;/这里使用一个二维数组统计同种颜色同奇偶性的个数，以及相应和varn,m,i,j,colour:longint;sumid,sumn,sum,count:array0.100001,0.1 of qword;ans:qword;number:array0.100001 of longint;beginassign(input,sum.in);reset(input);assign(output,sum.out);rewrite(output);readln(n,m);for i:=1 to n do read(numberi);readln;for i:=1 to n do beginread(colour);sumidcolour,i mod 2:=(sumidcolour,i mod 2+i) mod cs; inc(countcolour,i mod 2);sumncolour,i mod 2:=(sumncolour,i mod 2+numberi) mod cs; sumcolour,i mod 2:=(sumcolour,i mod 2+(numberi mod cs)*(i mod cs) mod cs) mod cs;end;readln;for i:=1 to m dofor j:=0 to 1 doif counti,j1 then ans:=(ans + sumidi,j*sumni,j mod cs+(counti,j-2)*sumi,j mod cs) mod cs;writeln(ans);close(input);close(output);end.第一种方法对公式转化的要求比较低，代码稍长，使用排序统计划分出同种颜色同奇偶性，时间复杂度就是排序的时间复杂度O(NlogN)；第二种方法对公式转化很彻底，代码很短，使用二维数组分出同种颜色同奇偶性,时间复杂度是O(N)；这两种方法基本涵盖了解决此题的各种方法。4.推销员(salesman.cpp/c/pas)【问题描述】阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。【输入格式】输入文件名为salesman.in。第一行有一个正整数N，表示螺丝街住户的数量。接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1S2Sn108。接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai103。【输出格式】输出文件名为salesman.out。输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。【样例输入1】51 2 3 4 51 2 3 4 5【样例输出1】1519222425【输入输出样例1说明】X=1: 向住户5推销，往返走路的疲劳值为5+5，推销的疲劳值为5，总疲劳值为15。X=2: 向住户4、5推销，往返走路的疲劳值为5+5，推销的疲劳值为4+5，总疲劳值为5+5+4+5=19。X=3: 向住户3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值3+4+5，总疲劳值为5+5+3+4+5=22。X=4: 向住户2、3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值2+3+4+5，总疲劳值5+5+2+3+4+5=24。X=5: 向住户1、2、3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值1+2+3+4+5，总疲劳值5+5+1+2+3+4+5=25。【样例输入2】51 2 2 4 55 4 3 4 1【样例输出2】1217212427【输入输出样例2说明】X=1：向住户4推销，往返走路的疲劳值为4+4，推销的疲劳值为4，总疲劳值4+4+4=12。X=2：向住户1、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4，总疲劳值4+4+5+4=17。X=3：向住户1、2、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4+4，总疲劳值4+4+5+4+4=21。X=4：向住户1、2、3、4推销，往返走路的疲劳值为4+4，推销的疲劳值为5+4+3+4，总疲劳值4+4+5+4+3+4=24。或者向住户1、2、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值为5+4+4+1，总疲劳值5+5+5+4+4+1=24。X=5：向住户1、2、3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳值为5+4+3+4+1，总疲劳值5+5+5+4+3+4+1=27。【样例输入输出3】见选手目录下的salesman/salesman3.in和salesman/salesman3.ans。【数据说明】对于20%的数据，1N20；对于40%的数据，1N100；对于60%的数据，1N1000；对于100%的数据，1N100000。【题解】这道题目距离Si是保证严格不降的，对于前60分，只需要O(N2)的算法O(N2)的算法的关键是要发现找最大疲劳值，要么是在距离点内找疲劳值最大的点，要么是增加距离范围找到一个（疲劳值+增加的往返距离值最大）的点。var i,j,n,k,maX,tot,tmp:longint;get:array0.100000 of boolean;a,s:array0.100000 of longint;begin assign(input,salesman.in);reset(input); assign(output,salesman.out);rewrite(output); readln(n);for i:=1 to n do read(si);readln;for i:=1 to n do read(ai);readln;j:=1; while j=n do beginmaX:=-maXlongint;k:=0;for i:=1 to n doif not geti then beginif simaX then beginmaX:=ai;k:=i;end endelseif (si-tmp)*2+aimaX then beginmaX:=(si-tmp)*2+ai;k:=i;end;end;getk:=true;inc(tot,maX);writeln(tot);if sktmp then tmp:=sk;inc(j);end; close(input);close(output);end.如果要拿到剩下的40分，主要有三种方法：方法一：利用数据结构优化O(NlogN)方法二：前缀和辅助O(NlogN,如果用O(N)排序就是O(N)方法三：计数排序+穷举（时间复杂度O(N*1000)=108,刚好能过）详细如下：【方法一】需要优化选择下一个最优点的时间复杂度，有很多种方式（单调队列、堆、树状数组），这里我采用了树状数组维护区间最值的方法，建立两个树状数组，分别表示当前距离范围内的最大疲劳值、超过距离范围的（疲劳值+增加的往返距离值）最大值。vari,n,j,m,tmp,k1,k2,tot,maX1,maX2,tmp2:longint;a,s,a2,s2,idX,idX2,idXid,idX2id,b:array0.100000 of longint;function lowbit(X:longint):longint;begineXit(X and (-X);end;procedure update(i,X:longint);var j:longint;begin j:=i;while i=n do beginif idXiX then begin idXi:=X; idXidi:=j; end;inc(i,lowbit(i);end;end;procedure update_desc(i,X:longint);/相当于逐个建立树状数组var j:longint;begin j:=i; while i=n do beginif idX2iX then begin idX2i:=X; idX2idi:=j; end;inc(i,lowbit(i);end;end;procedure modify(p,n:longint);var i,j:longint;begini:=p;ai:=0;while i=n do begin idXi:=ai;idXidi:=i; j:=1;while jlowbit(i) do begin if idXi0 do beginif query0 do beginif query2idX2m-stmp*2 then begin /tmp是上次选中的编号query2:=idX2m-stmp*2;k2:=idX2idm;end;dec(m,lowbit(m);end;end;beginassign(input,salesman.in);reset(input);assign(output,salesman.out);rewrite(output);readln(n);for i:=1 to n do read(si);readln;/距离数组for i:=1 to n do read(ai);readln;/疲劳值数组for i:=1 to n do s2n+1-i:=si;for i:=1 to n do a2n+1-i:=ai;for i:=1 to n do update(i,ai);for i:=1 to n do update_desc(i,s2i*2+a2i);tmp:=n+1;for i:=n downto 1 do /bi表示记录相同距离元素的最右边序号if stmpsi then beginbi:=i;tmp:=i;endelsebi:=tmp;j:=1;m:=0;tmp:=0;while jmaX2 then begininc(tot,maX1);tmp2:=k1;endelse begininc(tot,maX2);m:=bn+1-k2;tmp:=n+1-k2;tmp2:=n+1-k2;end;writeln(tot);modify(tmp2,n);inc(j);end;close(input);close(output);end.【方法二】前缀和Pi表示a数组中第i大的数的坐标，sum表示前缀和。 每一个答案都有两种可能来源：sumi-1 +2*spi+api+前i-1个或后i个中距离的最大值（maxssi） 或 前i个之和+前i个中距离最大值*2(maxsy then exit(x) else exit(y);end;procedure qsort(l,r:longint);var i,j,k,t,t1,t2:longint;begin i:=l;j:=r; k:=(i+j) div 2; t:=ak; ak:=ai; t1:=pk;pk:=pi; while ij do begin while (ij)and(ajt) do dec(j); if ij then begin ai:=aj; pi:=pj; inc(i); end; while (it) do inc(i); if il then qsort(l,i-1); if i+1spi then m1i:=m1i-1 else m1i:=pi;/m1