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

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

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

问题名称
文件名
输入文件
输出文件
时限
分值
热浪
heatwv
heatwv.in
heatwv。out
1s
100
兽径管理
maintain
maintain.in
maintain。out
1s
100
无序字母对
pair
pair。in
pair.out
1s
100
请柬
invite
invite.in
invite.out
3s
100
内存限制均为256M

热浪（heatwv）

【问题描述】
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品.Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任,以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T 〈= 2，500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用(包括油费，过路费等等）。

给定一个地图,包含C (1 〈= C <= 6，200）条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re （1 〈= Rs 〈= T; 1 〈= Re 〈= T),和花费（1 <= Ci 〈= 1,000）组成。求从起始的城镇Ts （1 〈= Ts 〈= T)到终点的城镇Te（1 <= Te 〈= T)最小的总费用.
【输入文件】
第一行： 4个由空格隔开的整数: T， C， Ts， Te
第2到第C+1行： 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci
【输出文件】
一个单独的整数表示从Ts到Te的最小总费用.数据保证至少存在一条道路。
【样例输入】
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
【样例输出】
7
【样例说明】
5->6—>1—〉4 (3 + 1 + 3）
兽径管理（maintain)

【问题描述】
约翰农场的牛群希望能够在 N 个（1<=N<=200) 草地之间任意移动。草地的编号由 1到 N。草地之间有树林隔开。牛群希望能够选择草地间的路径，使牛群能够从任一 片草地移动到任一片其它草地. 牛群可在路径上双向通行。
牛群并不能创造路径，但是他们会保有及利用已经发现的野兽所走出来的路径(以 下简称兽径).每星期他们会选择并管理一些或全部已知的兽径当作通路.
牛群每星期初会发现一条新的兽径。他们接着必须决定管理哪些兽径来组成该周牛 群移动的通路，使得牛群得以从任一草地移动到任一草地。牛群只能使用当周有被 管理的兽径做为通路。
牛群希望他们管理的兽径长度和为最小。牛群可以从所有他们知道的所有兽径中挑 选出一些来管理。牛群可以挑选的兽径与它之前是否曾被管理无关.
兽径决不会是直线，因此连接两片草地之间的不同兽径长度可以不同。 此外虽然 两条兽径或许会相交,但牛群非常的专注，除非交点是在草地内，否则不会在交点 换到另外一条兽径上。
在每周开始的时候，牛群会描述他们新发现的兽径.如果可能的话，请找出可从任 何一草地通达另一草地的一组需管理的兽径，使其兽径长度和最小。
【输入文件】
输入的第一行包含两个用空白分开的整数 N 和 W。W 代表你的程序需要处理 的周数。 (1 〈= W <= 6000)。
以下每处理一周,读入一行数据，代表该周新发现的兽径，由三个以空白分开 的整数分别代表该兽径的两个端点 (两片草地的编号） 与该兽径的长度（1…10000)。一条兽径的两个端点一定不同.
【输出文件】
每次读入新发现的兽径后,你的程序必须立刻输出一组兽径的长度和，此组兽径可从任何一草地通达另一草地，并使兽径长度和最小。如果不能找到一组可从任一草地通达另一草地的兽径，则输出 “—1"。
【样例】

輸入
輸出
說明
4 6

1 2 10

-1
No trail connects 4 to the rest of the fields.
1 3 8

—1
No trail connects 4 to the rest of the fields.
3 2 3

—1
No trail connects 4 to the rest of the fields。
1 4 3

14
Maintain 1 4 3, 1 3 8, and 3 2 3.
1 3 6

12
Maintain 1 4 3, 1 3 6， and 3 2 3。
2 1 2

8
Maintain 1 4 3, 2 1 2, and 3 2 3。

program exit

无序字母对（pair)

【问题描述】
给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。
【输入文件】
第一行输入一个正整数n。
以下n行每行两个字母，表示这两个字母需要相邻。
【输出文件】
输出满足要求的字符串。
如果没有满足要求的字符串,请输出“No Solution”。
如果有多种方案，请输出前面的字母的ASCII编码尽可能小的（字典序最小)的方案
【样例输入】
4
aZ
tZ
Xt
aX
【样例输出】
XaZtX

【数据规模与约定】
不同的无序字母对个数有限,n的规模可以通过计算得到。
请柬(invite)

【问题描述】
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片.他们已经打印请帖和所有必要的信息和计划.许多学生被雇来分发这些请柬.每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天，邀请人们参与。
　　这里的公交系统是非常特殊的：所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。　
学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
【输入文件】
第1行有两个整数n、m（1〈=n，m<=1000000)，n是站点的个数，m是线路的个数。
然后有m行,每行描述一个线路，包括3个整数,起始点，目的地和价格.
总部在第1个站点，价钱都是整数，且小于1000000000.
【输出文件】
输出一行，表示最小费用。
【样例输入】
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
【样例输出】
210
【样例解释】
学生各自从总部被派遣到2,3,4站点，然后又回到总部
1—2-4-1：10+5+50=65
1-3—4—1:20+10+50=80
1—2-4—1:10+5+50=65
65+80+65=210
【注意】
此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数.
热浪:基础的最短路问题
题目大意：
给出一张无向图，有T个点，C条边，求从Ts到Te的最短路。
解题思路：
这题是一个最基础的最短路问题，用于练习最短路算法，dijkstra或是spfa,都可以通过。
参考程序：
#include <cstdio>
#include <cstdlib〉
＃include 〈vector>
#include <cstring>
＃include 〈queue〉
using namespace std;
const int MAXN=2501;
typedef vector<int〉 Vec；
Vec Map［MAXN］,Val［MAXN];
int N,M,S,T;

void init(）
｛
scanf（"％d ％d ％d %d\n",&N,＆M,＆S，&T)；

int a,b,v;
for(int i=1；i〈=M;i++）
{
scanf（"%d ％d ％d\n"，&a,&b,&v）;
Map[a].push_back（b)；
Val［a］.push_back(v);
Map［b]。push_back（a);
Val［b］。push_back（v);
}
｝

int dist[MAXN];
int flag［MAXN］;
const int INF=1000000000；
queue〈int〉Q；
void SPFA（）
｛
for（int i=1；i〈=N；i++）
dist［i]=INF，flag[i]=0;
dist[S]=0，flag［S］=1;
Q.push(S）;
int t,tmp;
while（!Q.empty(）)
｛
t=Q.front()；
Q.pop()；
flag[t]=0；
for（unsigned int i=0；i〈Map［t］.size(）；i++)
{
tmp=dist［t]+Val[t][i］；
if(tmp〈dist[Map[t］[i］])
{
dist［Map[t］［i］］=tmp；
if(！flag[Map[t］［i]］)
{
Q.push（Map[t］[i]）；
flag[Map[t]［i]］=1;
}
｝
}
}
printf("％d\n”，dist[T])；
return;
}

int main(）
{
freopen（"heatwv。in",”r”，stdin）；
freopen(”heatwv。out","w"，stdout）；
init（）；
SPFA（）；
return 0；
｝
兽径管理:对最小生成树算法的选择
题目大意:
有N个点,W条边,每输入一条边回答一次当前是否存在最小生成树及最小生成树长度和.
解题思路：
我们有两种常用的求最小生成树的算法
prim ：通过枚举点求最小生成树,每次的复杂度为O(N^2），可以使用二叉堆优化.
kruskal:先将所有边排序，然后按长度从小到大选择，默认使用并查集,主要耗时为边的排序过程.
本题特点:需要求W次最小生成树,每次仅增加1条边。
算法选择：
这题显然应该选择kruskal算法，因为每次只增加另一条边，只要插入之前已排序的部分即可完成排序过程。
由于利用了前一次的计算，W次kruskal的总时间降到了O(W^2)，可以漂亮地通过该题.
在本题中，prim算法每次都需要重新计算，显然是十分费力的,不宜选择。
参考程序：
program maintain;
const maxn=200；
var n，m，t,i,j ：longint;
x,y,z ：array[0。。6005] of longint;
a，b，w ：longint;
f ：array[1.。maxn］ of longint；
f1，f2 :longint;
ans ：longint；

procedure sort（xx,l,r,w:longint);
var i，j：longint；
begin
for i:=0 to xx-1 do
if (z［i］<=w) and ((w<z[i+1］） or (i=xx—1）) then break；
for j:=xx downto i+2 do
begin
z[j]：=z[j—1];
x[j］:=x[j—1]；
y[j］:=y[j—1］;
end;
z[i+1］：=w;
x[i+1]：=l;
y［i+1]:=r；
end;

function getfa（x:longint）:longint；
begin
if f[x]=0 then exit（x）;
getfa:=getfa（f[x］)；
f［x］：=getfa；
end;

begin
assign(input,’maintain.in’)；
assign(output，'maintain。out’);
reset(input)；
rewrite（output)；
fillchar(x，sizeof（x），0);
fillchar(y，sizeof（y)，0);
fillchar（z，sizeof（z），0）;
readln（n，m）；
for i：=1 to m do
begin
fillchar(f,sizeof(f）,0);
readln(a，b，w）；
sort(i，a，b，w)；
ans:=0;
t:=0;
for j:=1 to i do
begin
f1：=getfa（x［j]);
f2：=getfa（y[j］）;
if f1〈>f2 then
begin
f［f2]：=f1;
inc（ans,z[j］)；
inc（t);
end；
if t=n-1 then break;
end；
t：=0；
for j：=1 to n do
if f［j］=0 then inc(t)；
if t<>1 then writeln(—1） else writeln（ans）;
end;
close（input);
close(output)；
end。
无序字母对:欧拉路径
题目描述:
给定n条边，每条边连接两个字母，求一条经过所有边的路径。
解题思路：
看清这道题的本质之后，这题是道典型的求欧拉路径问题，可以用来熟练欧拉路径的算法.
参考程序：
program ccxcx;
var n，i,j:longint;
c1,c2:char;
g：array［0。。255,0..255] of longint;
num：array［0。.255，0.。255] of longint；
vis：array［0。.255］ of boolean；
a：array［0..10000］ of longint;

procedure doit（v,now：longint);
var i1:longint;
begin
if now=n+2 then
begin
for i1:=1 to n+1 do write（chr（a［i1])）；
writeln；
close(output）;
halt；
end;
for i1：=65 to 122 do
if num[v,i1］>0 then
begin
dec（num[v，i1]);
dec（num［i1，v］);
a［now]:=i1；
doit（i1,now+1）；
inc(num[v,i1］）;
inc(num［i1，v])；
end；
end;

begin
assign(input,'pair。in')；
assign(output，’pair。out')；
reset(input);
rewrite(output)；
readln(n)；
fillchar(num，sizeof(num），0);
fillchar(g，sizeof(g)，0);
fillchar(vis，sizeof(vis)，false）;
for i:=1 to n do
begin
readln（c1,c2）;
inc(g[ord(c1)，0])；
g［ord(c1），g[ord(c1）,0］］ ：=ord（c2)；
inc(g[ord(c2）,0］）；
g［ord（c2)，g［ord（c2)，0］］ :=ord（c1）；
inc（num[ ord（c1）, ord(c2) ]） ；
inc(num［ ord(c2), ord（c1） ]） ;
vis[ord(c1）］:=true;
vis［ord(c2)]：=true;
end;
for i：=0 to 255 do
if odd(g[i，0］） then
begin
a[1］：=i；
doit(i，2);
end;
for i:=0 to 255 do
if vis[i] then
begin
a［1]:=i；
doit(i,2）;
end；
writeln（'No Solution’）；
close（input）；
close（output);
end。
请柬：dijkstra+二叉堆
题目大意：
有n个站点，m个单向的公交线路，n-1个学生从站点1出发乘公交分别前往站点2.。n，再从各自的站点乘公交返回站点1,求最小的公交费用总和。
解题思路：
点1分别到点2.。n的最短路即为学生出发时所需费用
使用单源最短路算法，即可求得一个点到其他所有点的最短路。（如dijkstra）
将图反向后即可求学生返回时的费用
解题思路:
由于规模较大，这题需要使用dijkstra+二叉堆算法
将与起点的距离d数组放入堆中
每次使用堆快速获得最小的d[i］
参考程序：
#include <iostream〉
＃include 〈cstdio>
#include 〈cstdlib〉
#include 〈cstring>
＃include 〈cmath〉
using namespace std;
#define FOR（i,a，b) for（int i=a；i〈=b；i++)
#define MST(a，b） memset(a,b，sizeof（a))
#define MAXN 2000050
＃define MAXM 2000050
#define MAXX 1000000000
int n，m；
int tot，ue[MAXM],ve[MAXM］,we[MAXM］；
int first［MAXN]，first2[MAXN]，next［MAXM］,next2［MAXM］；
void add(int u，int v，int w）
｛
ue[++tot]=u;ve［tot]=v；we[tot］=w；
next［tot］=first［u];first[u]=tot;
next2[tot］=first2[v］;first2[v］=tot;
｝
void init（)
｛
scanf(”％d％d"，&n,&m);
tot=0；
MST（first，0）;MST(first2，0）;
FOR（i,1,m）
｛
int u,v，w；
scanf（”%d%d%d”，＆u，＆v,&w）；
add（u，v,w）;
｝
}
int d[MAXN］,b[MAXN］；
int size，heap［MAXN*2],hpos［MAXN*2］；
void heapfy(int k)
｛
int min=k，l=k〈<1,r=（k<<1）+1；
if （（l〈=size)&＆(d［heap[l]]〈d［heap［min］］)）min=l;
if （（r<=size）＆＆（d［heap[r］］〈d[heap［min］］))min=r;
if （min!=k）
｛
int t=heap[k]；heap[k］=heap[min];heap［min］=t；
hpos[heap[k］]=k;hpos［heap［min]］=min;
heapfy(min);
｝
}
void exactheap(）
｛
heap［1］=heap[size]；
size-—；
hpos［heap［1］]=1；
heapfy(1)；
}
void change（int k)
{
heapfy(k）；
int t=heap[k］;
while ((k>1）&&（d[t］〈d［heap［k〉>1］]）)
｛
heap［k］=heap[k>〉1];
hpos［heap［k］］=k；
k=k〉>1;
}
heap［k]=t；
hpos［heap［k]］=k;
｝
void pre(）
｛
size=0；
MST(heap,0）；
}
long long ans；
void dj(）
｛
FOR（i，2,n)d[i］=MAXX；
d[1]=0;
pre（)；
size=n；
FOR(i,1,n)
｛
heap［i］=i;
hpos［i］=i；
｝
FOR（i，1，n-1)
{
int k=heap[1]；
exactheap()；
for（int p=first[k]；p！=0；p=next［p］）
if （(d[k]+we［p]<d[ve［p]］))
｛
d[ve[p］]=d［k]+we［p］；
change（hpos[ve[p］］);
｝
}
FOR(i,2,n)if (d［i]〉=MAXX)printf(”ERROR!"）；
FOR(i，2，n)ans=ans+d[i］;
}
void dj2()
｛
FOR（i,2,n)d[i]=MAXX；
d［1］=0；
pre(）;
size=n；
FOR（i，1,n）
{
heap[i]=i；
hpos［i]=i；
}
FOR(i，1，n-1）
｛
int k=heap[1］；
exactheap()；
for（int p=first2[k］；p！=0;p=next2［p］)
if ((d[k]+we[p］〈d［ue[p]］）)
｛
d[ue[p]］=d［k]+we［p］；
change(hpos[ue[p]])；
}
｝
FOR（i,2，n)if （d［i]〉=MAXX）printf("ERROR！”）；
FOR(i，2，n）ans=ans+d[i］；
｝
int main()
｛
freopen(”invite.in”，”r",stdin);
freopen("invite.out”，”w”，stdout);
// int nn；
// scanf(”%d",&nn）;
// FOR（ii，1,nn)
// ｛
init();
ans=0;
dj（）；
//cout〈〈ans〈〈” "；
dj2（);
cout〈〈ans〈<"\n";
// ｝
｝