2012福建省信息学奥林匹克CCF-NOIP夏令营第一天训练(附解题思路及参考程序).doc

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第一天训练(附解题思路及参考程序)

2012福建省信息学奥林匹克CCF NOIP夏令营第一天训练
（附解题思路及参考程序）

问题名称
文件名
输入文件
输出文件
时限
分值
足球
football
football .in
football.out
1s
100
数列排序
seqsort
seqsort。in
seqsort.out
1s
100
计算概率
calculate
calculate。in
calculate.out
1s
100
三角形牧场
pasture
pasture。in
pasture.out
1s
100
数列
seq
seq.in
seq。out
1s
100
内存限制均为256M

足球(football)
【问题描述】
我们当中有很多热爱中国足球的同学,我们都知道中超（中国足球超级联赛）的规则：
一场比赛中，若获胜（即你的得分严格大于对手得分）则获得3的积分，若打平（即你的得分等于对手得分)则获得1分,若失败（即你的得分严格小于对手得分）获得0积分.
这个问题很简单，假设N轮比赛中你一共攻入S个球，丢掉T个球,那么你可能获得的最大得分和最小得分是多少？
【输入文件】
多组数据，每组数据一行:
一行三个整数S、T、N(S、T 〉= 0，N >= 1）。
【输出文件】
对于每组数据输出一行,两个整数表示最大得分和最小得分。

【样例输入】
1 1 1
1 1 2

【样例输出】
1 1
3 2
数列排序（seqsort)

【问题描述】
给定一个数列{an｝,这个数列满足ai≠aj（i≠j），现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数,请问最少需要几次交换？

【输入文件】
第一行,正整数n （n〈=100，000）。
以下若干行，一共n个数，用空格分隔开，表示数列{an｝，任意-231〈ai〈231。

【输出文件】
只有一行,包含一个数,表示最少的交换次数。

【样例输入】
8
8 23 4 16 77 -5 53 100

【样例输出】
5
计算概率(calculate）

【问题描述】
小明有n个长度不一的小木棍，这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l,让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l，则小明胜，否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。
【输入文件】
输入包含两行.第一行为两个整数n和l，其中n和l都不超过100000。第二行包含n个整数,分别为n个木棍的长度。
【输出文件】
输出包含一个实数，小明胜出的概率,保留两位小数。
【输入样例】
4 5
1 2 3 4
【输出样例】
0。67
三角形牧场（pasture）
【问题描述】
和所有人一样,奶牛喜欢变化。它们正在设想新造型的牧场。奶牛建筑师hei想建造围有漂亮白色栅栏的三角形牧场。她拥有N(3≤N≤40）块木板，每块的长度Li(1≤Li≤40)都是整数，她想用所有的木板围成一个三角形使得牧场面积最大。
请帮助Hei小姐构造这样的牧场，并计算出这个最大牧场的面积。
【输入文件】
第1行：一个整数N
第2。。N＋1行：每行包含一个整数，即是木板的长度。
【输出文件】
仅一个整数:最大牧场面积乘以100然后舍尾的结果。
如果无法构建,输出-1。
【输入样例】
5
1
1
3
3
4
【输出样例】
692
数列（seq）

【问题描述】
有这样一种数列A1、A2、A3、……An，其中A1=0，且对任意一项Ai满足|Ai—Ai+1｜=1（1〈=i<n）。设S=A1+A2+A3+……+An，表示前n项之和。
现在给出数列长度n与数列前n项之和S，要求：
输出满足条件的数列的总数。
输出满足条件的100个数列（如果不满100个就全部输出）.

【输入文件】
一行，包含两个整数n和S（1〈=n<=100），用1个空格隔开。

【输出文件】
第1行一个整数t（0<=t<=263-1)，表示满足条件的数列总数.
接下来每行输出一个数列，数列各项之间用一个空格隔开.
若满足条件的数列数目不满100个，全部输出即可。
【样例输入】
4 0

【样例输出】
2
0 —1 0 1
0 1 0 -1
足球
先全部分配进球数到每场
有不够的就把失球全部放在那一场里
否则将进球与失球抵消
反之亦然
参考程序：
const
inf = ''；
ouf = '’；
maxS = 10;
maxT = 10；
maxN = 20;

var
s， t， n : int64；
p, q : int64;

begin
assign（input, 'football.in'); assign(output， 'football.out'）;
reset（input)； rewrite（output）；

while not seekeof do begin
readln（s, t, n）；

if n = 1 then
if s = t then writeln（’1 1'） else
if s 〉 t then writeln（’3 3’) else writeln（'0 0’）
else
if s + t = 0 then writeln（n， ’ '， n） else begin
if s = 0 then begin
p ：= n - 1;
if n 〈= t then q := 0 else q ：= n - t；
end else
if t = 0 then begin
if n 〈= s then p ：= 3 * n else p ：= 3 * s + n — s;
q ：= 3 + (n - 1）;
end else
if s 〈= t then begin
if n <= s + 1 then p ：= (n — 1) ＊ 3 else p := s ＊ 3 + n - (s + 1)；

if （s = 1) and （n 〉= t) then q := 1 + n — t else
if n 〈= t - s then q ：= 0 else
if n = t - s + 1 then q ：= 1 else
if n = t - s + 2 then q := 2 else
if n <= t + 1 then q ：= 3 else q ：= n - （t + 1） + 3；
end else begin
if n <= s - t then p ：= 3 * n else
if n = s — t + 1 then p := 3 ＊ (s - t) + 1 else
if n 〈= s + 1 then p := （n — 1） ＊ 3 else p ：= 3 ＊ s + n - (s + 1）;

if n 〈= t + 1 then q := 3 else q := n - （t + 1） + 3；
end；
writeln(p, ’ ', q)；
end；
end;

close(input）; close（output）;
end。
数列排序
将序列排序
找出所有的循环,即错误位置调换的循环
如 2 4 1 3 循环为 2—>4-〉3->1-〉2
Ans=sigma 循环长度—1
参考程序：
var
a,b:array[0.。1000000]of longint；
n,i，j,tot，t,ans:longint；
use:array[0.。1000000]of boolean;

procedure qsort（l,r:longint)；
var
i，j,x,t:longint;
begin
i：=l； j:=r； x：=a［random(r-l+1)+l］;
repeat
while a［i]〈x do inc(i）;
while a［j]>x do dec（j);
if i〈=j then
begin
t：=a[i]; a[i]：=a[j]； a［j]：=t；
t：=b［i]; b[i］：=b[j]； b［j］：=t；
inc(i）;
dec(j）;
end;
until i>j；
if i〈r then qsort（i，r);
if l〈j then qsort(l,j）；
end；

begin
assign(input，'seqsort。in’)；
reset(input）;
readln(n）；
for i：=1 to n do
begin
read（a［i]）;
b［i]：=i;
end;
close(input）;
qsort(1,n）;
for i：=1 to n do
a[i］:=i；
for i：=1 to n do
if not use[i］ then
begin
t:=i；
tot:=0;
while not use[t］ do
begin
use[t]：=true；
inc(tot);
t：=b[t]；
end;
ans:=ans+tot-1;
end;
assign(output，'seqsort.out’）;
rewrite(output）;
writeln(ans);
close（output）；
end.
计算概率
由于l的范围并不大，且长度又都是整数,故而可以将每个长度单位的木棍个数都记录下来，然后计算两根木棍长度和小于等于l的组数，最后计算出概率。
用一长度为l的数组记录长度为数组下标的木棍个数,然后可以用O（n)的复杂度计算出组数，最后除以n(n-1)/2得出概率。
j:=1;
k：=l—1；
s：=0；
ans:=0;
while k>j do
begin
inc(s,a[j])；
inc(ans，a［k］*s)；
dec(k）；
inc(j);
end；
参考程序：
var i,j，k,n,l:longint;
s,ans：int64;
a:array[1..100000] of longint；
r：real;
procedure setup;
begin
assign（input,'calculate.in’)；
reset（input）;
assign（output，’calculate.out’);
rewrite(output）;
end;
procedure endit；
begin
close（input);
close（output)；
end;
begin
setup;
fillchar（a,sizeof（a),0);
readln(n,l);
for i：=1 to n do
begin
read（k);
if k〈=l then inc（a[k］);
end;
j:=1；
k：=l-1;
s:=0；
ans：=0;
while k>j do
begin
inc（s,a[j］）；
inc(ans,a[k]*s);
dec(k);
inc(j);
end;
if j=k then inc(s，a[j]）;
inc(ans,s＊(s-1) div 2)；
r：=2*ans/n/（n-1);
writeln（r:0：2）；
endit;
end.
三角形牧场
二位背包+海伦公式
f[i］［j］［k]表示前i个木板，能否加出第一条边为j，第二条边为k的三角形。
参考程序：
＃include<cstdio>
＃include<iostream>
#include〈cstdlib〉
#include〈cstring>
#include<string〉
＃include〈cmath>
using namespace std；
int i，n,t1，t2，t3,Tot；
int a[50］，g[2］［1601][1601]；
long double p,s，ans；
main(）｛
freopen("Pasture。in”,”r”,stdin）；
freopen("Pasture.out”,"w”,stdout);
scanf（”％d",＆n)；
for （i=1;i〈=n；i++） scanf（”％d”，＆a[i]）;
memset（g,0，sizeof（g)）；
g［0][0][0]=1；Tot=0;
for (i=1;i〈=n;i++){
for (t1=0;t1<=Tot;t1++）
for （t2=0；t2〈=Tot—t1;t2++)
if (g［(i—1）％2］[t1]［t2］==1){
g［i%2］[t1+a[i]]［t2]=1；g［i%2］［t1］［t2+a[i]］=1;g［i％2][t1］［t2]=1；
｝
Tot+=a［i］;
｝
ans=—1;
for （t1=0；t1<=Tot；t1++)
for (t2=0；t2<=Tot-t1；t2++)
if (g[n％2]［t1］［t2］==1)｛
t3=Tot-t1—t2;
if （t1+t2>t3&&t1+t3〉t2&＆t2+t3〉t1）{
p=double（Tot）/2；
s=sqrt（p*（p-t1）＊（p—t2)＊(p—t3））;
if （s>ans） ans=s;
｝
}
if （ans<0.5) printf("—1\n"）;else
printf（"％ld\n”,long(ans*100)）；
}
数列
我们开始时可以假设所有数都是0
每次判断当前数是比前一个数大1还是小1
加入是大1，相当于之后每个数都加了1
F[i，j］表示 前i个数 和为j 的种类数
F[i+1,j+i+1]：=F[i+1，j+i+1]+F[i，j］;
F[i+1，j-i—1］:=F［i+1,j-i—1]+F［i,j］;
参考程序:
type index=Longint；
var num,N,S,i,j:index； tot：int64;
F：array［0..200，-10000.。10000]of int64;
a：array［0.。200]of boolean；

Procedure DFS（T:index）;
var i,tmp:index；
Begin
if （T=0）and(tot〉0)and(num=0) then
Begin
dec（tot）;
write(0）;
tmp：=0;
For i：=N-1 downto 1 do
Begin
if a［i］ then inc（tmp） else dec(tmp）；
write(’ ’，tmp）;
End;
writeln；
Exit；
End；
if T=0 then Exit；
if (tot=0)or（F[T,num]=0) then Exit;
a［T]:=False;
num:=num+T;
DFS(T-1);
a［T]：=True;
num：=num-2＊T；
DFS(T-1)；
num:=num+T;
End;

Begin
Assign(Input,'seq.in’）; Reset（Input);
Assign(Output,'seq.out’); Rewrite（Output）;
Readln(N,S)；
Fillchar(F,sizeof(F）,0)；
F[1，1]:=1； F［1,—1］:=1；
For i:=1 to N—2 do
For j：=—10000 to 10000 do
Begin
if F[i,j]>0 then
Begin
F[i+1，j+i+1]：=F[i+1，j+i+1］+F［i，j］;
F［i+1，j-i—1］:=F[i+1,j-i—1]+F[i,j];
End;
End;
writeln（F［N-1,S]）;
tot：=F[N-1，S]；
if tot>100 then tot：=100；
num：=S;
DFS（N-1）;
Close(Input）； Close（Output);
End.