Posted on 五月 27th, 2008.
这道题WindyWinter牛给出的算法是并查集,实际上可以DFS解决(感谢alft…).
每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…并查集当然也没错…
注意会是一个森林,需要多次DFS…
{ SGU 172; eXam - sqybi’s code - DFS}//for my winstyprogram sgu172_sqybi; const nn = 200; mm = 30000;
var n, m, tot, i, x, y, t: longint; flag: boolean; head, p: array[1..nn]of longint; adj, next: array[-mm..mm]of longint;
procedure addEdge(x, y: longint); begin inc(tot); adj[tot] := y; next[tot] := head[x]; head[x] := tot; […]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 24th, 2008.
变态题.做了好久了,刚开始WA,今天晚上下定决心调过,结果RE了.
和cy的AC程序对拍,拍了几十组极限数据都没错,而且我的程序比他的快得多…现在唯一可能错的地方大概就是那个又臭又长的TBinarySearchTree.delete(x, y: longint);了(名字就又臭又长…),可是还是不知道哪儿有错.如果你知道这道题有什么阴人的地方…请告诉我…
代码即使没有AC也差不多都对了,所以贴出来.希望有人能帮我看完代码…不过我知道不可能…
{The k-th Largest Group; cat; POJ 2985- sqybi’s code- 并查集+平衡树- 祝福爱德华多…}//for my winsty, for Eduardoprogram pku2985_sqybi; const nn = 200000; mm = 200000;
type TUnionFindSets = object size, father: array[1..nn]of longint; procedure init; function getF(x: longint): longint; procedure combine(x, y: longint); end; TBinarySearchTree = object root, num: longint; size: array[0..nn+mm]of longint; data, […]
Read Full Post |
Make a Comment ( None so far )
Posted on 三月 19th, 2008.
这道题是山东2007年第二次省选的题目,和这道题几乎一样的题目还在这些地方出现过:POJ 1733; URAL 1003; Vijos 1112; CEOI 99 Bugs.
看出现在这么多地方就知道应该是道很经典的题目了…
当时jl刚跟我说这道题,我就反应到了食物链那道题,但是后来jl说有mlogn的算法我就没向并查集方面想…后来发现的确是部分和+并查集,和我最开始的想法一样.算法复杂度O(m*alpha()),近似看作O(m).不过mlogn的算法没想出来.
首先,对于一个条件x y z,如果z=0,相当于转换为,对于一个只存有0和1的数组a[],a[x-1]和a[y]数组中存储的数相同.那么z=1就是存储的数不同.这里很好用部分和和奇偶性的知识解释,不赘述.这样,每次判断z,并判断x和y的关系,根据关系进行合并.用mark[x]记录树x的”敌人”(就是和a[x]存储的数不同的某一个位置–可以知道这个位置一定最多只有一个,多于一个时可以合并).
然后进行各种合并,具体方法看程序(主程序)中的判断部分.顺便判当前条件是否与之前的条件冲突.
这道题1Y,其实还是比较简单的,只不过判断的地方恶心了些,写到一半删了重写了一次…
{ TOI 1110; 01字符串问题 - sqybi’s code - 部分和+并查集}//for my winsty{$APPTYPE CONSOLE}program str_sqybi; const fin = ’str.in’; fout = ’str.out’; nn = 50000;
var n, m, i, x, y, z, fx, fy, t, total: longint; father, mark, size: array[1..nn+1]of longint;
function getF(x: longint): […]
Read Full Post |
Make a Comment ( None so far )