NOIP2010普及组满分题解.doc

【个人题解+代码】NOIP2010 普及组
首先前两题可以说非常水，第三题也是水题。第四题难度和前三题差别有点大……
1．数字统计
(two.pas/c/cpp)
【问题描述】
请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。
比如给定范围[2, 22]，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6次。

【输入】
输入文件名为two.in。
输入共1 行，为两个正整数L 和R，之间用一个空格隔开。

【输出】
输出文件名为two.out。
输出共1 行，表示数字2 出现的次数。

【输入输出样例1】
two.in
two.out
2 22
6

【输入输出样例2】
two.in
two.out
2 100
20

【数据范围】
1 ≤ L ≤ R≤ 10000。

直接上题解：
T1：two
大水题，主要有如下几种方法：
1.用字符串处理
2.每次用mod10取最后一位再div10
3.递推
递推式f[i]=f[i div 10]+f[i mod 10]
然后累加即可（我是用这个做的）
4.分别用数学公式计算每一位上2的个数（最快，但没必要，代码也较长）
……
var
f:array[0..10000] of longint;
l,r,i,ans:longint;
begin
assign(input,'two.in');reset(input);
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);
end.
2．接水问题
(water.pas/c/cpp)
【问题描述】
学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。
现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m，则只有n’个龙头供水，其它m?n’个龙头关闭。
现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

【输入】
输入文件名为water.in。
第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。
第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。

【输出】
输出文件名为water.out。
输出只有一行，1 个整数，表示接水所需的总时间。

【输入输出样例1】
water.in
water.out
5 3
4
4 4 1 2 1

【输入输出样例 1 说明】
第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完水，4 号同学接替3 号同学开始接水。
第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接水量为1。
第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。
第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接水量为1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒。

【输入输出样例2】
water.in
water.out
8 4
23 71 87 32 70 93 80 76
163

【数据范围】
1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；
1 ≤ wi ≤ 100。

T2：water
还是水题
此题其实就是纯模拟，设a[i]为第i个水龙头已经输出的水量。那么每次某个人去接水量为w的水时，就是在所有a[i]中最小的一个里面加上w。由此，对于每个接水的人，都重复这一过程，最后输出所有a[i]里最大的一个就是结果。
对于这个思路，如果每次全部扫描来求最小值，时间复杂度O(mn)，可以AC了（话说我就直接这么写了）
如果你追求完美主义，可以用堆来维护a数组，每次+w相当于一个IncreaseKey，可将时间复杂度降低到O(nlogm)
var
a:array[1..100] of longint;
n,m,i,j,min,w,ans:longint;
begin
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]<a[min] then min:=j;
inc(a[min],w);
if a[min]>ans then ans:=a[min];
end;
writeln(ans);
close(input);close(output);
end.
3．导弹拦截
(missile.pas/c/cpp)
【问题描述】
经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。
某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

【输入】
输入文件名missile.in。
第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。
第二行包含1 个整数N，表示有N 颗导弹。接下来N 行，每行两个整数x、y，中间用一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。

【输出】
输出文件名missile.out。
输出只有一行，包含一个整数，即当天的最小使用代价。

【提示】
两个点(x1, y1)、(x2, y2)之间距离的平方是(x1? x2)2+(y1?y2)2。
两套系统工作半径r1、r2 的平方和，是指r1、r2 分别取平方后再求和，即r12+r22。

【输入输出样例1】
missile.in
missile.out
0 0 10 0
18
2

-3 3

10 0

【样例 1 说明】
样例1 中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为18 和0。

【输入输出样例2】
missile.in
missile.out
0 0 6 0
30
5

-4 -2

-2 3

4 0

6 -2

9 1

【样例2 说明】
样例中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20 和10。

【数据范围】
对于10%的数据，N = 1
对于20%的数据，1 ≤ N ≤ 2
对于40%的数据，1 ≤ N ≤ 100
对于70%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000，且所有坐标分量的绝对值都不超过1000。

T3：missile
此题是排序+枚举
首先计算出每个点到两个系统的距离平方。
我们的想法是，对于第一个系统的半径进行枚举，收容尽量多的导弹。于是第二个系统的半径就可以随之确定。在枚举的所有状态中找一个最小值即可。
话题转移到实现上来，我们先对所有导弹到第一个系统距离平方进行从小到大排序，于是在我们枚举第一个系统的半径时（当然半径肯定等于某个导弹到这个系统的距离），所有排在这个“某个导弹”前面的导弹就是第一个拦截系统所要拦截的点。那么理所当然，这个排在这个导弹之后的点就是系统二所要拦截的，于是第二个系统的半径就很好确定了。于是枚举上文所说的“这个导弹”（倒着枚举比较方便），把两个系统半径平方之和取最小值，就是最终结果。
这段代码如下（很短，真的很短）：
ans:=a[n,1];
for i:=n downto 1 do
begin
   if a[i,1]+r2<ans then ans:=a[i,1]+r2;
   if a[i,2]>r2 then r2:=a[i,2];
end;
（a[i,1]是排好序的第i个导弹距离1号系统的距离平方，r2是当前第二套系统的半径平方的值）
完整程序如下：
var
a:Array[1..100000,1..2] of longint;
x1,x2,y1,y2,x,y,n,i,r2,ans:longint;
procedure fs(s,e:longint);
var
m,k,j:longint;
ms:array[1..2] of longint;
begin
m:=random(e-s+1)+s;k:=s;j:=e;
ms:=a[m];a[m]:=a[k];
while k<j do
begin
while (k<j)and(a[j,1]>ms[1]) do dec(j);
if k<j then begin a[k]:=a[j];inc(k);end;
while (k<j)and(a[k,1]<ms[1]) do inc(k);
if k<j then begin a[j]:=a[k];dec(j);end;
end;
a[k]:=ms;
if s<k-1 then fs(s,k-1);
if j+1<e then fs(j+1,e);
end;
begin
assign(input,'missile.in');reset(input);
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]+r2<ans then ans:=a[i,1]+r2;
if a[i,2]>r2 then r2:=a[i,2];
end;
writeln(ans);
close(input);close(output);
end.

var
x1,y1,x2,y2,n,x,y,i,j:longint;
r:array[1..2] of longint;
a:array[1..100000,1..2] of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x
else min:=y;
end;
begin
assign(input,'missile.in');
assign(output,'missile.out');
reset(input);
rewrite(output);
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
begin
readln(x,y);
a[i,1]:=sqr(x-x1)+sqr(y-y1);
a[i,2]:=sqr(x-x2)+sqr(y-y2);
end;
r[1]:=0;r[2]:=0;
for i:=1 to n do
begin
if r[1]>=a[i,1] then continue;
if r[2]>=a[i,2] then continue;
if a[i,1]-r[1]<a[i,2]-r[2] then
r[1]:=a[i,1]
else r[2]:=a[i,2];
end;
writeln(r[1]+r[2]);
close(input);
close(output);
end.
4．三国游戏
(sanguo.pas/c/cpp)
【问题描述】
小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。
在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有N 位武将（N为偶数且不小于4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。接下来一直按照“小涵→计算机→小涵→……”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。
已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。
下面举例说明计算机的选将策略，例如，游戏中一共有6 个武将，他们相互之间的默契值如下表所示

双方选将过程如下所示：

小涵
轮到计算机时可选的自由武将
计算机
计算机选将说明
第一轮
5
1 2 3 4 6
4
小涵手中5号武将与4号的默契值昀高，所以选择 4号
第二轮
5 3
1 2 6
4 1
小涵手中的5号和3号武将与自由武将中配对可产生的昀大默契值为 29，是由 5号与 1号配对产生的，因此计算机选择 1号
第三轮
5 3 6
2
4 1 2

小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？
假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。

【输入】
输入文件名为sanguo.in，共N 行。
第一行为一个偶数N，表示武将的个数。
第2 行到第N 行里，第（i+1）行有（N?i）个非负整数，每两个数之间用一个空格隔开，表示i 号武将和i+1，i+2，……，N 号武将之间的默契值（0 ≤ 默契值≤ 1,000,000,000）。

【输出】
输出文件sanguo.out 共1 或2 行。
若对于给定的游戏输入，存在可以让小涵获胜的选将顺序，则输出1，并另起一行输出所有获胜的情况中，小涵最终选出的武将组合的最大默契值。
如果不存在可以让小涵获胜的选将顺序，则输出0。

【输入输出样例1】
sanguo.in
sanguo.out
6
5 28 16 29 27
23 3 20 1
8 32 26
33 11
12
1
32
【输入输出样例说明】
首先小涵拿走5 号武将；计算机发现5 号武将和剩下武将中的4 号默契值最高，于是拿走4 号；小涵接着拿走3 号；计算机发现3、5 号武将之一和剩下的武将配对的所有组合中，5 号和1 号默契值最高，于是拿走1 号；小涵接着拿走2 号；计算机最后拿走6 号。在小涵手里的2，3，5 号武将中，3 号和5 号配合最好，默契值为32，而计算机能推出的最好组合为1 号和6 号，默契值为27。结果为小涵胜，并且这个组合是小涵用尽所有方法能取到的最好组合。

【输入输出样例2】
sanguo.in
sanguo.out
8
42 24 10 29 27 12 58
31 8 16 26 80 6
25 3 36 11 5
33 20 17 13
15 77 9
4 50
19
1
77

【数据范围】
对于 40%的数据有 N ≤ 10。
对于 70%的数据有 N ≤ 18。
对于 100%的数据有 N ≤ 500。

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的数据么！）
满分程序如下：
var
a:array[1..500,1..500] of longint;
n,i,j,max,cmax,ans:longint;
begin
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;
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);
end.