【个人题解+代码】NOIP2010 普及组 题解+代码
首先前两题可以说非常水,第三题也是水题。第四题难度和前三题差别有点大……
直接上题解:
T1:two 大水题,主要有如下几种方法: 1.用字符串处理 2.每次用 mod10 取最后一位再 div10 3.递推 递推式 f[i]=f[i div 10]+f[i mod 10] 然后累加即可(我是用这个做的) 4.分别用数学公式计算每一位上 2 的个数(最快,但没必要,代码也较长) …… (此题与浙江 2009 年省选第一题雷同……)
DELPHI CODE 1 var 2 3
:NOIP2010 普及组 T1 two
f:array[0..10000] of longint; l,r,i,ans:longint;
4 begin 5 assign(input,'two.in');reset(input);
6 7 8 9 10 11 12 13 14
assign(output,'two.out');rewrite(output); read(l,r); f[2]:=1; for i:=10 to r do f[i]:=f[i div 10]+f[i mod 10]; for i:=l to r do inc(ans,f[i]); writeln(ans); close(input);close(output);
15 end.
T2:water 还是水题 此题其实就是纯模拟,设 a[i]为第 i 个水龙头已经输出的水量。那么每次某个人去接水量为 w 的水时,就是在所有 a[i]中最小的一个里面加上 w。由此,对于每个接水的人,都重复这 一过程,最后输出所有 a[i]里最大的一个就是结果。 对于这个思路,如果每次全部扫描来求最小值,时间复杂度 O(mn),可以 AC 了(话说我 就直接这么写了) 如果你追求完美主义,可以用堆来维护 a 数组,每次+w 相当于一个 IncreaseKey,可将时 间复杂度降低到 O(nlogm)
DELPHI CODE 1 var
:NOIP2010 普及组 T2 water
2 3
a:array[1..100] of longint; n,m,i,j,min,w,ans:longint;
4 begin 5 6 7 8 9 10 11 12 13 14 15 16 17 18 assign(input,'water.in');reset(input); assign(output,'water.out');rewrite(output); read(n,m); for i:=1 to n do begin read(w); min:=1; for j:=2 to m do if a[j]
ans then ans:=a[min]; end; writeln(ans); close(input);close(output);
19 end.
T3:missile 此题是排序+枚举 首先计算出每个点到两个系统的距离平方。
我们的想法是,对于第一个系统的半径进行枚举,收容尽量多的导弹。于是第二个系统的半 径就可以随之确定。在枚举的所有状态中找一个最小值即可。
话题转移到实现上来, 我们先对所有导弹到第一个系统距离平方进行从小到大排序, 于是在 我们枚举第一个系统的半径时(当然半径肯定等于某个导弹到这个系统的距离),所有排在 这个“某个导弹”前面的导弹就是第一个拦截系统所要拦截的点。 那么理所当然, 这个排在 这个导弹之后的点就是系统二所要拦截的, 于是第二个系统的半径就很好确定了。 于是枚举 上文所说的“这个导弹”(倒着枚举比较方便),把两个系统半径平方之和取最小值,就是 最终结果。 这段代码如下(很短,真的很短): ans:=a[n,1]; for i:=n downto 1 do begin
if a[i,1]+r2
r2 then r2:=a[i,2]; end; (a[i,1]是排好序的第 i 个导弹距离 1 号系统的距离平方,r2 是当前第二套系统的半径平方 的值)
完整程序如下:
DELPHI CODE 1 var
:NOIP2010 普及组 T3 missile
2 3
a:Array[1..100000,1..2] of longint; x1,x2,y1,y2,x,y,n,i,r2,ans:longint;
4 procedure fs(s,e:longint); 5 var 6 7 m,k,j:longint; ms:array[1..2] of longint;
8 begin 9 10 11 12 13 14 15 16 17 18 19 20 m:=random(e-s+1)+s;k:=s;j:=e; ms:=a[m];a[m]:=a[k]; while kms[1]) do dec(j); if k 21 end; 22 begin 23 assign(input,'missile.in');reset(input);
24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
assign(output,'missile.out');rewrite(output); read(x1,y1,x2,y2); read(n); for i:=1 to n do begin read(x,y); a[i,1]:=sqr(x-x1)+sqr(y-y1); a[i,2]:=sqr(x-x2)+sqr(y-y2); end; fs(1,n); ans:=a[n,1]; for i:=n downto 1 do begin if a[i,1]+r2r2 then r2:=a[i,2]; end; writeln(ans); close(input);close(output);
42 end.
T4:sanguo 此题是贪心(话说我没想出来呢……)
其实结果就是一句话:每个武将所能组合成的次大值之中取最大值。 证明: 1.这个值一定是最优的: 证:每个武将能组合的最大值一定是取不到的,因为你选定某个武将之后,最大值就被电脑 “咔嚓”掉了。于是我们只可能取到次大值,而次大值中最大的就一定最优了。 2.这个值一定能取到 证:当你取第一个值武将的时候,电脑把这个武将可组合的最大武将“咔嚓”了。这是后你 就可以取到那个组合值次大的武将。于是这个值就一定能取到了 3.你一定能赢电脑 证:在按 2 操作完之后,你取了 2 个武将,设第一次取了 x,第二次取了 y,电脑取了一个 武将 z。那么(x,y)是所有次大里面最大的,而(x,z)是所有(x,i){i=1..n}中最大的。之后电脑需 要取一个武将 a。接着证明电脑这次的取值能得到的组合(z,a)一定小于(x,y)。
1'如果(z,a)是(z,i){i=1..n}中最大的一个,那么(z,x)就至多是(z,i){i=1..n}中次大的一个,而前 面又证明过(x,y)<(x,z),于是(x,y)就不是所有次大中最大的一个。与假设矛盾
2'如果(z,a)不是(z,i){i=1..n}中最大的一个,而(z,a)>(x,y),那么(z,a)至多是次大,但这样的 话(x,y)就不是次大中的最大的一个,与假设矛盾。
所以(z,a)<(x,y),也就是说电脑前两次取值一定没你大。那么之后电脑再取一个,你就可以 把它的最大“咔嚓”掉, 电脑也就再也取不到最大组合, 而次大组合中的最大组合已经被你 取了,所以电脑取的总没你大!
(证不出来的话你就这么想:NOIP 这种样例这么
完备的比赛,要有输出 0 的情况,它样例
里会不给你出个输出 0 的数据么!)
PS:知道我咋做的?搜索+DLX+随机化+卡时!近 100 行……然后基本杯具了(60 分)……
满分程序如下:
DELPHI CODE 1 var 2 3
:NOIP2010 普及组 T4 sanguo
a:array[1..500,1..500] of longint; n,i,j,max,cmax,ans:longint;
4 begin 5 6 7 8 9 10 11 12 13 14 15 16 assign(input,'sanguo.in');reset(input); assign(output,'sanguo.out');rewrite(output); read(n); for i:=1 to n do for j:=i+1 to n do begin read(a[i,j]); a[j,i]:=a[i,j]; end; for i:=1 to n do begin max:=0;cmax:=0;
17 18 19 20 21 22 23 24
for j:=1 to n do if a[i,j]>max then begin cmax:=max;max:=a[i,j];end else if a[i,j]>cmax then cmax:=a[i,j]; if cmax>ans then ans:=cmax; end; writeln('1'); writeln(ans); close(input);close(output);
25 end.