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 include c1,b-c1)； if(result = 0） result = strcmp（ac2， 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, colorindexmiddle.col)； if（cmp 0) return binsearch（key， min， middle1）； else if (cmp 0） return binsearch(key， middle+1, max)； else return middle； int main（) char t111; char t211； 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(sticksssize.c1, t1); strcpy(sticksssize+。c2， t2); else strcpy(sticksssize。c2, t1）; strcpy（sticksssize+。c1, t2); if(ssize = 0) printf（”Possiblen)； return 0； qsort（sticks， ssize, sizeof（Stick）, （void ） cmp_sticks）; for（i = 0； i ssize； i+） colorscsize.col = sticksi。c1; colorscsize+1。col = sticksi.c2； csize += 2； qsort（colors， csize, sizeof（Color)， （void *) cmp_colors）； current = colors0.col; colorindexsetsize+。col = colors0。col； curcount = 1; oddcount = 0； for(i = 1； i csize； i+） if (strcmp （current， colorsi。col) = 0） curcount+； else if （curcount%2)oddcount+;if（oddcount 2） printf(”Impossiblen); return 0； colorindexsetsize+。col = colorsi.col； current = colorsi.col; curcount = 1; if(setsize = 1) printf(Possiblen）; return 0； for（i = 0; i setsize； i+) colorseti = -1； for(i = 0; i #include cstdlib#include cstringusing 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 400050int n;long long aMAXN2;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”，ai)； qsort（a1,n,sizeof(long long）,comp）;void work（） int l2=1，n+1,r2=n,n； long long ans=0; FOR（i,1，n1) long long min2； FOR（j，0,1) if (l0r0) minj=al1;l1+;continue； if (l1r1） minj=al0;l0+;continue; if （al0al1) minj=al0;l0+；continue; else minj=al1；l1+;continue； a+r1=min0+min1； ans=ans+ar1； / printf（”dn，ar1)； / printf（”dn”，ar1）； coutans；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队列集合的根节点为该队列头部的战舰父节点的战舰排在子节点前面并查集可以快速查询战舰所在队列，可以快速合并两个队列解题思路：对于合并和查询战舰所在队列,只需要最基本的并查集，维护一个数组fatheri即可通过查找根节点查询战舰所在队列将第i队列接到第j队列尾部时,将第i队列的根节点的父节点设为第j队列的根节点但该题还需要回答两艘战舰之间的战舰数量,所以我们要对并查集进行扩展战舰的数量：新增两个数组counti：记录根节点i表示的队列拥有多少艘战舰beforei：记录节点i之前有多少艘战舰(使用前需通过路径压缩更新）路径压缩:在查询并返回根节点root后,beforei=beforei+beforefatheri;/更新beforeifatheri=root;查询：分别查询节点i，j的根节点以判断战舰i,j是否位于同一队列。若位于同一队列,则此时abs（beforeibeforej)1就是战舰i，j间的战舰数量合并:查询得节点i，j的根节点分别为x,yfatherx=y;/合并beforex=county;/更新beforexcounty=county+countx/更新county参考程序：constmaxn=30000;varfather，count,before：array1。maxn of longint;t,k,a,b：longint；c:char;procedure init;vari:longint；beginreadln(t）;for i:=1 to maxn dobegin fatheri：=i; counti：=1； beforei:=0;end;end;function getfather(v：longint）：longint；varf:longint；beginif fatherv=v thengetfather：=velsebegin f:=getfather(fatherv); beforev:=beforefatherv+beforev; fatherv:=f； getfather:=fatherv；end；end；procedure merge（x，y:longint）;vari，j：longint；begini:=getfather（x）;j：=getfather（y);fatheri：=j;beforei:=beforei+countj;countj：=countj+counti;end；procedure ask（x,y:longint）；beginif getfather(x)getfather（y） then writeln（1)else writeln（abs（beforex-beforey)1）;end;beginassign（input,galaxy.in）;assign（output，galaxy。out)；reset(input）;rewrite（output);init；for k：=1 to t dobegin 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。