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

(完整版)2012福建省信息学奥林匹克CCF NOIP夏令营第三天训练解题思路及参考程序
瑞瑞的木棍:Hash函数
题目大意：
有N根两端被染色的木棍，只有两个颜色相同的端点才能连接在一起，求是否能将木棍连成一条直线.
需要解决：
如何处理用单词表示的颜色
如何判断是否能连成一条直线
单词的处理：
在计算过程中用单词表示颜色显然是很不方便的，所以常用的做法就是将单词编号。
使用hash表将每个单词对应唯一的hash值
对新出现的hash值编号，使每个单词分别对应编号1。。。M
判断木棍是否能连成一条线：
将每种颜色看作一个点，将每根木棍看作一条边,则问题转化为判断该图是否存在欧拉路径。
存在欧拉路径的条件：
图是连通的
每个点都与偶数条边相连或有且只有2个点与奇数条边相连
解题思路：
1.用hash表将单词编号，将木棍以边的形式储存
2。统计与奇数条边相连的点的数量
3.判断图是否连通：
方法1:用dfs或bfs判断一个点是否能到达其他所有点
方法2：用并查集判断所有点是否属于同一个集合

参考程序：
/* H： Colored Sticks */

＃include <stdio.h>
＃include <stdlib。h〉

typedef struct｛
char c1［11］；
char c2[11］；
} Stick;

typedef struct{
char ＊col;
} Color;

Stick sticks[250020］;
int ssize = 0;

Color colors［500020];
Color colorindex［500020];
int setsize = 0;
int colorset[500020]；
int csize = 0;

int GetRoot（int x)｛
if(colorset[x］ 〈 0) return x；
else return GetRoot(colorset［x]);
｝

void Union （int a, int b){
int rootA = GetRoot（a)；
int rootB = GetRoot（b）；

if（rootA == rootB） return;

if（colorset[rootA］ 〈= colorset[rootB])｛

colorset[rootA］ += colorset[rootB]；
colorset[rootB] = rootA;

if(colorset［rootA］ == -1＊setsize){
printf（”Possible\n”）；
exit(0）；
｝
} else ｛
colorset［rootB］ += colorset[rootA]；
colorset［rootA] = rootB;

if（colorset［rootB] == -1*setsize）{
printf（"Possible\n"）;
exit（0）;
｝
｝
｝

int cmp_sticks(Stick ＊a, Stick ＊b){
int result = 0;

result = strcmp（a->c1,b->c1)；
if(result == 0） result = strcmp（a—〉c2， b-〉c2);

return result；
｝

int cmp_colors(Color *a, Color ＊b）{
return strcmp（a-〉col, b-〉col）；
}

int binsearch(char *key, int min, int max){
int cmp;
int middle = (min+max)/2;
if（min == max） return min;

cmp = strcmp(key, colorindex[middle］.col)；

if（cmp 〈 0)｛
return binsearch（key， min， middle—1）；
｝ else if (cmp >0）｛
return binsearch(key， middle+1, max)；
} else ｛
return middle；
｝
｝

int main（)｛
char t1[11];
char t2[11］；
char *current；
int i, index1， index2;
int oddcount， curcount；
freopen（”stick.in","r”，stdin）;
freopen(”stick.out"，”w",stdout）；
while(scanf("%s %s”， t1， t2）==2)｛
if（strcmp(t1， t2) < 0）｛
strcpy(sticks［ssize］.c1, t1);
strcpy(sticks［ssize++]。c2， t2);
} else ｛
strcpy(sticks［ssize]。c2, t1）;
strcpy（sticks［ssize++］。c1, t2);
｝
｝

if(ssize == 0)｛
printf（”Possible\n")；
return 0；
}

qsort（sticks， ssize, sizeof（Stick）, （void ＊） cmp_sticks）;

for（i = 0； i < ssize； i++）{
colors[csize].col = sticks［i]。c1;
colors[csize+1]。col = sticks［i].c2；
csize += 2；
｝

qsort（colors， csize, sizeof（Color)， （void *) cmp_colors）；

current = colors［0].col;

colorindex［setsize++］。col = colors［0］。col；

curcount = 1;
oddcount = 0；
for(i = 1； i < csize； i++）{
if (strcmp （current， colors[i］。col) == 0）｛
curcount++；
} else {
if （curcount%2){
oddcount++;
if（oddcount 〉 2）{
printf(”Impossible\n");
return 0；
｝
｝
colorindex[setsize++］。col = colors[i］.col；

current = colors［i］.col;
curcount = 1;
｝
｝
if(setsize == 1)｛
printf("Possible\n"）;
return 0；
}

for（i = 0; i < setsize； i++){
colorset［i］ = -1；
}

for(i = 0; i < ssize； i++）｛
index1 = binsearch(sticks［i］.c1， 0, setsize）；
index2 = binsearch（sticks[i].c2, 0, setsize);
Union（index1， index2）;
}

printf(”Impossible\n"）；

return 0；
}
瑞瑞的木板：堆
题目大意:
将一条足够长的木板切割为N条木板，每次切割消耗的能量为被切割木板的长度。
这题其实和合并果子完全相同，只是换了一种描述。
合并果子：
将N堆果子合并为一堆果子， 每次合并消耗的能量为合并的果子的重量和。
解题思路：
将问题转化为将N条木板接成一条，与合并果子相同,实质为构造哈夫曼树.
最佳方案构造方法：
将最短的两条木板接成一条木板
重复这一过程直到只剩一条木板
具体实现：
每次寻找最短的两条木板是很耗费时间的
使用堆来加速
将N条木板的长度放入堆中
每次从堆中取出两条最小的木板，合并为一条木板后放入堆中
重复上一步骤直到堆中只剩一条木板
每次合并消耗能量之和便是所求答案
参考程序：
#include 〈iostream〉
＃include 〈cstdio>
#include 〈cstdlib〉
#include <cstring〉
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 400050
int n;
long long a［MAXN＊2］;
int comp(const void *a，const void ＊b）
｛
return *(long long ＊)a-＊（long long *)b;
}
void init（)
{
scanf(”%d”，&n）；
FOR（i，1,n）scanf（"％d”，＆a[i］)；
qsort（＆a[1］,n,sizeof(long long）,comp）;
｝
void work（）
｛
int l［2］={1，n+1｝,r［2]={n,n}；
long long ans=0;
FOR（i,1，n—1)
{
long long min［2]；
FOR（j，0,1)
｛
if (l［0］〉r［0］) {min[j]=a[l［1］];l[1]++;continue；｝
if (l[1]〉r［1]） ｛min[j]=a［l［0］];l［0］++;continue;｝
if （a［l［0]]<a［l[1］])
｛min[j］=a[l［0］］;l［0]++；continue;｝
else {min[j］=a［l［1］］；l［1］++;continue；}
}
a［++r[1]］=min[0］+min[1]；
ans=ans+a［r[1]］；
// printf（”％d\n"，a[r［1］］)；
｝
// printf（”％d\n”，a［r［1]]）；
cout〈〈ans；
｝
int main（）
｛
freopen（"plank.in","r”，stdin）;
freopen("plank。out","w"，stdout)；
init（);
work(）；
｝
银河英雄传说：并查集
题目大意：
初始时30000艘战舰被排成了一排，第i号战舰位于第i队列
有两种指令
合并指令M i j：让第i号战舰所在队列的全部战舰，作为一个整体（头在前尾在后)接至第j号战舰所在队列的尾部.
询问指令C i j：询问第i号战舰和第j号战舰是否位于同一队列，若在同一列中，回答它们之间有多少艘战舰.
解题思路：
使用并查集结构
每一个集合表示一个队列
第i号战舰为节点i,初始时位于第i队列
集合的根节点为该队列头部的战舰
父节点的战舰排在子节点前面
并查集可以快速查询战舰所在队列，可以快速合并两个队列
解题思路：
对于合并和查询战舰所在队列,只需要最基本的并查集，维护一个数组father[i]即可
通过查找根节点查询战舰所在队列
将第i队列接到第j队列尾部时,将第i队列的根节点的父节点设为第j队列的根节点
但该题还需要回答两艘战舰之间的战舰数量,所以我们要对并查集进行扩展
战舰的数量：
新增两个数组
count[i］：记录根节点i表示的队列拥有多少艘战舰
before[i］：记录节点i之前有多少艘战舰(使用前需通过路径压缩更新）
路径压缩:
在查询并返回根节点root后,
before［i］=before[i]+before[father[i］];//更新before［i］
father[i]=root;
查询：
分别查询节点i，j的根节点以判断战舰i,j是否位于同一队列。若位于同一队列,则此时abs（before［i]—before［j])—1就是战舰i，j间的战舰数量
合并:查询得节点i，j的根节点分别为x,y
father［x］=y;//合并
before［x]=count[y］;//更新before［x]
count[y］=count[y]+count［x］//更新count[y］
参考程序：
const
maxn=30000;
var
father，count,before：array[1。。maxn] of longint;
t,k,a,b：longint；
c:char;
procedure init;
var
i:longint；
begin
readln(t）;
for i:=1 to maxn do
begin
father［i］：=i;
count[i］：=1；
before［i]:=0;
end;
end;
function getfather(v：longint）：longint；
var
f:longint；
begin
if father［v]=v then
getfather：=v
else
begin
f:=getfather(father［v]);
before[v］:=before［father［v］]+before[v];
father[v]:=f；
getfather:=father[v]；
end；
end；
procedure merge（x，y:longint）;
var
i，j：longint；
begin
i:=getfather（x）;
j：=getfather（y);
father［i]：=j;
before[i]:=before［i]+count［j］;
count[j]：=count[j］+count［i];
end；
procedure ask（x,y:longint）；
begin
if getfather(x)<〉getfather（y） then writeln（—1)
else writeln（abs（before［x]-before[y］)—1）;
end;
begin
assign（input,'galaxy.in'）;
assign（output，'galaxy。out’)；
reset(input）;
rewrite（output);
init；
for k：=1 to t do
begin
read（c)；readln（a,b)；
if c=’M’ then merge（a，b)
else
if c='C’ then ask(a，b)；
end;
close(input）；
close（output）；
end。