当前位置:首页 >> 学科竞赛 >>

noip2015普及组题解最终


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.in 6 【样例输出】coin.out 14 【输入输出样例1说明】 骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每 天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。 【数据范围】对于 100%的数据,1 ≤K ≤10,000。 【题解】 关注到 K 的范围是 10000 后,就不需要考虑数学公式,纯模拟就行,考点就是 for 循环 了 var i,j,count,n,ans:longint; begin assign(input,'coin.in');reset(input); assign(output,'coin.out');rewrite(output); readln(n); for i:=1 to 1000 do for j:=1 to i do begin inc(count); inc(ans,i); if count=n then begin writeln(ans); close(input);close(output); halt;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

end; end; end.

2.扫雷游戏
(mine.cpp/c/pas)

【问题描述】 扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称 之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该 格将会出现一个数字——提示周围格子中有多少个是地雷格。 游戏的目标是在不翻出任 何地雷格的条件下,找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。 注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上 与之直接相邻的格子。 【输入格式】 输入文件名为mine.in。 输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。 接下来n行,每行m个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是 地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。 【输出格式】 输出文件名为mine.out。 输出文件包含 n 行,每行 m 个字符,描述整个雷区。用’*’表示地雷格,用周围的地 雷个数表示非地雷格。相邻字符之间无分隔符。 【样例输入】 3 3 *?? ??? ?*? 【样例输出】 *10 221 1*1 【数据说明】 对于 100%的数据,1≤n≤100,1≤m≤100。 【题解】 行列数最多 100,也就是 100*100 的单元格数量,一个个判断过去也就 100*100*8 个方 向,判断边界时注意数组的下标别越界就行了。考点还是 for 循环哦,可以考虑使用增 量数组,不过就 8 个方向手写也很快的。 var n,m,i,j,count:longint;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

a:array[0..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 do begin for j:=1 to m do read(a[i,j]); readln; end; for i:=1 to n do begin for j:=1 to m do if a[i,j]='*' then write(a[i,j]) else begin count:=0; if a[i-1,j-1]='*' then inc(count); if a[i-1,j]='*' then inc(count); if a[i-1,j+1]='*' then inc(count); if a[i,j-1]='*' then inc(count); if a[i,j+1]='*' then inc(count); if a[i+1,j-1]='*' then inc(count); if a[i+1,j]='*' then inc(count); if a[i+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都代表纸带上格子的编号,这里的三元组要

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

求满足以下两个条件: 1. ,,都是整数,<<,?= ?

2. =
满足上述条件的三元组的分数规定为(x+z)?(+)。整个纸带的分数规定为 所有满足条件的三元组的分数的和。 这个分数可能会很大, 你只要输出整个纸带的分数除以 10,007所得的余数即可。 【输入格式】 输入文件名为sum.in。 第一行是用一个空格隔开的两个正整数和,代表纸带上格子的个数,代表纸带上颜色 的种类数。 第二行有个用空格隔开的正整数, 第个数字代表纸带上编号为的格子上面写的数 字。 第三行有个用空格隔开的正整数,第个数字代表纸带上编号为的格子染的颜色。 【输出格式】 输出文件名为sum.out。 共一行,一个整数,表示所求的纸带分数除以 10,007 所得的余数。 【样例输入】 6 2 5 5 3 2 2 2 2 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组数据,1≤≤100,1≤≤5; 对于第3组至第4组数据,1≤≤3000,1≤≤100; 对于第5组至第6组数据,1≤≤100000,1≤≤100000,且不存在出现次数超过20的颜 色; 对于全部 10 组数据,1≤≤100000,1≤≤100000,1≤≤,1≤≤100000。

【题解】 可以理解为 n 个元素每个元素有三个属性分别是数值 Number、颜色和编号,对于任意 两个满足 2 个条件的元素进行相应的统计, 第 1 个条件其实等价于这两个元素的编号都是奇 数或都是偶数,第 2 个条件是相同颜色值。 观察数据范围我们可以发现前 4 组数据的 n 只有 3000,O(N^2)的算法就能拿分,直接 穷举任意两个元素,这个代码非常简短的: var //预期得 40 分的程序 n,m,i,j:longint; a,b:array[0..100000] of qword;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

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(a[i]);readln; for i:=1 to n do read(b[i]);readln; for i:=1 to n do for j:=i+1 to n do if not odd(i+j) and (b[i]=b[j]) then begin ans:=(ans+(a[i]+a[j])*(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)的值: sumid[i]表示编号的总和, sumni 表示 number 的总和, havid[i]

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

表示 1 到 i 的编号总和,havni[i]表示 1 到 i 的 number 总和,于是(2)(3)式子中的括号部分 可以用 sumid-havid[i]、sumni-havni[i]来表示。 那么如何挑选出这些元素, 换句话说就是如何归类出颜色相同奇偶性相同的元素, 我们可以 用双关键字排序(颜色主关键字,奇偶性次关键字),当然还有其他方式用 O(nlogn)、O(n) 的排序都可以,二维数组统计颜色、奇偶性都可以,这里我采用了快速排序。最终程序的时 间复杂度就是 O(NlogN) const cs=10007;//预期满分程序 type arr=record x,y,id:int64; z:boolean; end; var a:array[0..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; begin tot:=0;havid:=0;havni:=0;//sumid,sumni 表示编号、数字总和,havid,havni 表示编号、数字前缀和 for j:=count downto 1 do begin inc(havid,a[i-j].id);inc(havni,a[i-j].x); tot:=(tot+a[i-j].x*(sumid-havid))mod cs;//总和-前缀和就能得 到我们想要的后缀和,题解中提取的公式运用 tot:=(tot+a[i-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; begin x:=random(t-h+1)+h; tmp:=a[h];a[h]:=a[x];a[x]:=tmp; i:=h;j:=t; tmp:=a[i]; while i<j do begin while (i<j) and ( (a[j].y>tmp.y) or (a[j].y=tmp.y) and (a[j].z>tmp.z)) do dec(j); if i<j then begin a[i]:=a[j];

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

inc(i); end; while (i<j) and ((a[i].y<tmp.y) or (a[i].y=tmp.y) and (a[i].z<tmp.z)) do inc(i); if i<j then begin a[j]:=a[i]; dec(j); end; end; a[i]:=tmp; if h<i-1 then qsort(h,i-1); if i+1<t 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(a[i].x);readln;//表示 number for i:=1 to n do read(a[i].y);readln;//表示颜色 for i:=1 to n do begin a[i].id:=i; a[i].z:=odd(i);//奇偶 end; qsort(1,n);//颜色主关键字,奇偶次关键字排序 i:=1; while i<=n+1 do begin if (tmpc<>a[i].y) or (tmpodd<>a[i].z) then begin //tmpc 表示上一 段颜色值,tmpodd 表示上一段奇偶值 if count>1 then deal; sumid:=a[i].id;sumni:=a[i].x;sum:=sumid*sumni; tmpc:=a[i].y; tmpodd:=a[i].z; count:=1; end else begin sumid:=(sumid+a[i].id); sumni:=(sumni+a[i].x); sum:=(sum+(a[i].id*a[i].x)); inc(count); end; inc(i); end; writeln(ans);

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

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+ x3……Xn) …… Xi(x1+……xi-1+ xi+1……Xn) …… 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;//这里使用一个二维数组统计同种颜色同奇偶性的个数,以及相应和 var n,m,i,j,colour:longint; sumid,sumn,sum,count:array[0..100001,0..1] of qword; ans:qword; number:array[0..100001] of longint; begin assign(input,'sum.in');reset(input); assign(output,'sum.out');rewrite(output); readln(n,m); for i:=1 to n do read(number[i]);readln;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

for i:=1 to n do begin read(colour); sumid[colour,i mod 2]:=(sumid[colour,i mod 2]+i) mod cs; inc(count[colour,i mod 2]); sumn[colour,i mod 2]:=(sumn[colour,i mod 2]+number[i]) mod cs; sum[colour,i mod 2]:=(sum[colour,i mod 2]+(number[i] mod cs)*(i mod cs) mod cs) mod cs; end; readln; for i:=1 to m do for j:=0 to 1 do if count[i,j]>1 then ans:=(ans + sumid[i,j]*sumn[i,j] mod cs+(count[i,j]-2)*sum[i,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家住户到入口的距离。数据保证 S1≤S2≤…≤Sn<108。 接下来的一行有N个正整数,其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。 数据保证Ai<103。 【输出格式】 输出文件名为salesman.out。 输出 N 行,每行一个正整数,第 i 行整数表示当 X=i 时,阿明最多积累的疲劳值。 【样例输入 1】 5

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

1 2 3 4 5 1 2 3 4 5 【样例输出 1】 15 19 22 24 25 【输入输出样例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】 5 1 2 2 4 5 5 4 3 4 1 【样例输出 2】 12 17 21 24 27 【输入输出样例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%的数据,1≤N≤20; 对于40%的数据,1≤N≤100;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

对于60%的数据,1≤N≤1000; 对于 100%的数据,1≤N≤100000。

【题解】 这道题目距离 Si 是保证严格不降的,对于前 60 分,只需要 O(N^2)的算法 O(N^2)的算法的关键是要发现找最大疲劳值, 要么是在距离点内找疲劳值最大的点, 要么是 增加距离范围找到一个(疲劳值+增加的往返距离值最大)的点。 var i,j,n,k,maX,tot,tmp:longint; get:array[0..100000] of boolean; a,s:array[0..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(s[i]);readln; for i:=1 to n do read(a[i]);readln; j:=1; while j<=n do begin maX:=-maXlongint; k:=0; for i:=1 to n do if not get[i] then begin if s[i]<=tmp then begin if a[i]>maX then begin maX:=a[i]; k:=i; end end else if (s[i]-tmp)*2+a[i]>maX then begin maX:=(s[i]-tmp)*2+a[i]; k:=i; end; end; get[k]:=true; inc(tot,maX); writeln(tot); if s[k]>tmp then tmp:=s[k]; inc(j); end; close(input);close(output); end.

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

如果要拿到剩下的 40 分,主要有三种方法: 方法一:利用数据结构优化 O(NlogN) 方法二:前缀和辅助 O(NlogN,如果用 O(N)排序就是 O(N)) 方法三:计数排序+穷举(时间复杂度 O(N*1000)=10^8,刚好能过) 详细如下: 【方法一】需要优化选择下一个最优点的时间复杂度,有很多种方式(单调队列、堆、 树状数组),这里我采用了树状数组维护区间最值的方法,建立两个树状数组,分别表 示当前距离范围内的最大疲劳值、超过距离范围的(疲劳值+增加的往返距离值)最大 值。 var i,n,j,m,tmp,k1,k2,tot,maX1,maX2,tmp2:longint; a,s,a2,s2,idX,idX2,idXid,idX2id,b:array[0..100000] of longint; function lowbit(X:longint):longint; begin eXit(X and (-X)); end; procedure update(i,X:longint); var j:longint; begin j:=i; while i<=n do begin if idX[i]<X then begin idX[i]:=X; idXid[i]:=j; end; inc(i,lowbit(i)); end; end; procedure update_desc(i,X:longint);//相当于逐个建立树状数组 var j:longint; begin j:=i; while i<=n do begin if idX2[i]<X then begin idX2[i]:=X; idX2id[i]:=j; end; inc(i,lowbit(i)); end; end; procedure modify(p,n:longint); var i,j:longint;

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

begin i:=p;a[i]:=0; while i<=n do begin idX[i]:=a[i];idXid[i]:=i; j:=1; while j<lowbit(i) do begin if idX[i]<idX[i-j] then begin idX[i]:=idX[i-j]; idXid[i]:=idXid[i-j]; end; j:=j shl 1; end; inc(i,lowbit(i)); end; end; function query(m:longint):longint; begin query:=0; while m>0 do begin if query<idX[m] then begin query:=idX[m]; k1:=idXid[m]; end; dec(m,lowbit(m)); end; end; function query2(m:longint):longint; begin query2:=0; while m>0 do begin if query2<idX2[m]-s[tmp]*2 then begin //tmp 是上次选中的编号 query2:=idX2[m]-s[tmp]*2; k2:=idX2id[m]; end; dec(m,lowbit(m)); end; end; begin assign(input,'salesman.in');reset(input); assign(output,'salesman.out');rewrite(output); readln(n); for i:=1 to n do read(s[i]);readln;//距离数组

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

for i:=1 to n do read(a[i]);readln;//疲劳值数组 for i:=1 to n do s2[n+1-i]:=s[i]; for i:=1 to n do a2[n+1-i]:=a[i]; for i:=1 to n do update(i,a[i]); for i:=1 to n do update_desc(i,s2[i]*2+a2[i]); tmp:=n+1; for i:=n downto 1 do //b[i]表示记录相同距离元素的最右边序号 if s[tmp]<>s[i] then begin b[i]:=i; tmp:=i; end else b[i]:=tmp; j:=1;m:=0;tmp:=0; while j<=n do begin maX1:=query(m);//前 tmp 个元素求最大值 maX2:=query2(n-m);//从 tmp+1 到 n 个元素中求算上距离的最大值 if maX1>maX2 then begin inc(tot,maX1); tmp2:=k1; end else begin inc(tot,maX2); m:=b[n+1-k2]; tmp:=n+1-k2; tmp2:=n+1-k2; end; writeln(tot); modify(tmp2,n); inc(j); end; close(input);close(output); end. 【方法二】前缀和

P[i]表示 a 数组中第 i 大的数的坐标,sum 表示前缀和。 每一个答案都有两种可能来源:sum[i-1] +2*s[p[i]]+a[p[i]]+前 i-1 个或后 i 个中距 离的最大值(maxs>s[i]) 或 前 i 个之和+前 i 个中距离最大值*2(maxs<s[i]) 程序实现 by 周骏东 and 刘柏成
type aa=array[0..100000]of longint; var a,s,p,sum,b,c,m1,m2,f:aa; n,i,j:longint; function max(x,y:longint):longint; begin

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

if x>y 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:=a[k]; a[k]:=a[i]; t1:=p[k];p[k]:=p[i]; while i<j do begin while (i<j)and(a[j]<t) do dec(j); if i<j then begin a[i]:=a[j]; p[i]:=p[j]; inc(i); end; while (i<j)and(a[i]>t) do inc(i); if i<j then begin a[j]:=a[i]; p[j]:=p[i]; dec(j); end; end; p[i]:=t1; if i-1>l then qsort(l,i-1); if i+1<r then qsort(i+1,r); end; begin readln(n); for i:=1 to n do read(s[i]);

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

readln; for i:=1 to n do begin read(a[i]); p[i]:=i; end; b:=a; qsort(1,n); a:=b;//以 a 为标准,对 p 数组进行排序 sum[1]:=a[p[1]]; m1[1]:=p[1]; for i:=2 to n do begin sum[i]:=sum[i-1]+a[p[i]]; if s[m1[i-1]]>s[p[i]] then m1[i]:=m1[i-1] else m1[i]:=p[i];//m1[i]表示 p[1]到 p[i]中距离最大的值的坐标 end; m2[n]:=p[n]; for i:=n-1 downto 1 do begin if 2*s[m2[i+1]]+a[m2[i+1]]>2*s[p[i]]+a[p[i]] then m2[i]:=m2[i+1] else m2[i]:=p[i];//m2[i]表示 p[i]到 p[n]中 2*s[i]+a[i]最大值的坐标 end; for i:=1 to n do writeln(max(sum[i-1]+a[m2[i]]+max(s[m1[i-1]],s[m2[i]])*2,sum[i]+s[m1[i]]*2)); end.

【方法三】计数排序+穷举 by 王哲凡 注意题目的描述 Si 是有序的同时,值又是 0~999 的范围,因此可以先把 Si 计数排序, 值作为下标存储在一个数组 然后每次选定下一个推销点时扫描 0~999 的范围,选一个值最大的,相同值中越靠右的 一定是最优的(想想为什么) #include <iostream> #include <cstdio> #include <cstring> #include <stdio.h> #include <cstdlib> using namespace std; int s[100009],a[100009],ans[100009],number[1001],q[1001][101]; int max(int x,int y) {

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

if (x>y) return x; else return y; } int init() { char ch; ch=getchar(); while (ch<48||ch>57) ch=getchar(); int sum=0; while (ch>=48&&ch<=57) { sum=sum*10+ch-48; ch=getchar(); } return sum; } int main() { freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); int n; n=init(); for (int i=1;i<=n;i++) { s[i]=init(); } for (int i=1;i<=n;i++) { a[i]=init(); number[a[i]]++; q[a[i]][number[a[i]]]=i; } int _max=0; int maxi=0; for (int i=1;i<=n;i++) { _max=max(_max,s[i]*2+a[i]); if (_max==s[i]*2+a[i]) maxi=i; } ans[1]=_max; number[a[maxi]]--; for (int i=2;i<=n;i++) {

noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院

2015 年 11 月 11 日

int x=0; int y=0; _max=0; for (int j=1;j<=1000;j++) { if (number[j]>0) if (q[j][number[j]]>maxi) { if (_max<2*s[q[j][number[j]]]-2*s[maxi]+j) { _max=2*s[q[j][number[j]]]-2*s[maxi]+j; x=q[j][number[j]]; y=j; } } else { if (_max<j) { _max=j; x=q[j][number[j]]; y=j; } } } maxi=max(maxi,x); ans[i]=ans[i-1]+_max; number[y]--; } for (int i=1;i<=n;i++) { printf("%d\n",ans[i]); } _fcloseall(); return 0; }


相关文章:
noip2015普及组题解最终.doc
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015
noip2015普及组题解.doc
最终程序的时 间复杂度就是 O(NlogN) const cs=10007;//预期满分程序 type ...noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015 年 11 月 11 ...
noip2015普及组解题报告.txt
noip2015普及组解题报告_学科竞赛_高中教育_教育专区。noip2015普及组满分解题报告...noip2015普及组解题报告 14页 1下载券 noip2015普及组题解最终 18页 1下载券...
NOIP2015普及组解题报告.doc
NOIP2015 普及组解题报告 From 贴吧 id u007zzt 金币 国王将金币作为工资,发放...noip2015普及组解题报告 6页 2下载券 noip2015普及组题解最终 18页 1下载券...
NOIP2015普及组复赛解题报告.doc
NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育...numberx),Σ x,Σ numberx 和 k(注意最后一项...【时空复杂度】 O(n),O(n+m) 【注意】题目...
NOIP2015普及组复赛试卷.pdf
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称 英文题目...
noip2015初赛普及组试题答案_图文.pdf
noip2015初赛普及组试题答案_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档noip2015初赛普及组试题答案_IT认证_资格考试/认证_教育专区。最新...
NOIP2015普及组初赛试题及答案(Pascal).doc
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
NOIP2015普及组复赛试题讲解(c++版本)_图文.ppt
NOIP2015普及组复赛试题讲解(c++版本) - 试题分析 NOIP2015 普及组复赛题解 NOIP2015普及组C++ 2017. 07. 28 第1题 “金币”简述 ? 国王将...
NOIP2015普及组初赛试题及答案(Pascal).doc
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月...
noip2015初赛普及组与提高组试题与答案.ppt
noip2015初赛普及组与提高组试题与答案_学科竞赛_高中教育_教育专区。noip2015(全国青少年信息学奥林匹克竞赛)初赛普及组与提高组试题与答案 ...
NOIP2015普及组C++试题.pdf
NOIP2015普及组C++试题_IT认证_资格考试/认证_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C++语言试题 竞赛时间:2015 年 10 月 11 日 14:30...
NOIP2015信息学奥赛普及组初赛C++试题.doc
NOIP2015信息学奥赛普及组初赛C++试题_学科竞赛_初中教育_教育专区。NOIP2016信息学奥赛普及组初赛C++试题 2015 年第二十一届全国青少年信息学奥林匹克联赛初赛 普及...
NOIP2015普及组初赛试题及答案(PASCAL).pdf
NOIP2015普及组初赛试题及答案(PASCAL)_电子/电路_工程科技_专业资料。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 ...
普及组NOIP2015C++语言试题.pdf
普及组NOIP2015C++语言试题_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载 | 举报文档 普及组NOIP2015C++语言试题_学科竞赛_初中教育_教育专区。 ...
NOIP2015普及组C试题.pdf
NOIP2015普及组C试题_IT认证_资格考试/认证_教育专区。noip2015年信息学奥赛试题 第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C 语言试题 竞赛时间:2015 年...
NOIP2015普及组C++试题.pdf
NOIP2015普及组C++试题_学科竞赛_初中教育_教育专区。NOIP2015普及组C++试题 第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C++语言试题 竞赛时间:2015 年 10 ...
NOIP2015普及组Pascal试题.pdf
NOIP2015普及组Pascal试题_IT认证_资格考试/认证_教育专区。第二十一届全国青少年信息学奥林匹克联赛初赛普及组 Pascal 语言试题 竞赛时间:2015 年 10 月 11 日 ...
全国信息学奥林匹克联赛(NOIP2015)复赛普及组第一题pas....txt
全国信息学奥林匹克联赛(NOIP2015)复赛普及组第一题pascal版coin
...届全国青少年信息学奥林匹克联赛初赛(普及组试题及....doc
10 四.根据题意, 将程序补充完整 (前 8 空,每空 3 分,最后 1 空 4 ...NOIP2014初赛普及组试题... 6页 1下载券 2015NOIP提高组初赛(C... 10页...
更多相关标签: