Archive for 三月, 2008
Posted on 三月 28th, 2008.
这道题我也不知道是哪儿的题…说是HNOI模拟赛是我从gen的fp.ini的路径推测出来的…
题目大概就是说,给你一个有向无环图,然后用数量最少的不相交简单路径覆盖每一个结点.第一行输入n,m,为结点和边数.接下来m行每行两个整数x,y,代表x->y的一条有向边.
这道题是经典的二分图匹配了.对于边x->y,建立(x,y)这条二分图中的边.然后做最大匹配,易证明最大匹配+路径条数=结点数,问题解决.
我这道题的算法是HopCroft,一个sqrt(n)*m的算法,也就是Hungary的优化.这里有个问题问知道这个算法的大牛,为什么HopCroft算法如果找最短增广路增广,速度反而没有找最长增广路增广快?按理说最短增广路应该快啊…也是HopCroft的标准做法啊…这是巧合还是什么呢…
P.S.cqf大牛竟然没听说过HopCroft…P.S.又是我喜欢的object…这次加上了指针,还不算乱…不过似乎加了object速度掉的很厉害.HopCroft也不是很难写.
{news- sqybi’s code- 二分图匹配- Hopcroft}//for my winstyprogram news_sqybi; const fin = ‘news.in’; fout = ‘news.out’; nn = 100000;
type link = ^obj1; obj1 = record v: longint; next: link; end; TBipartiteGraph = object private len: longint; head, tail: array[1..2, 1..nn]of link; dist, match: array[1..2, 1..nn]of longint; check: array[1..nn]of boolean; q: array[1..nn]of longint; function search(x: […]
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 三月 22nd, 2008.
这道题简直把平衡树的BT程度发挥到了极致…
上次写WA了,这次先是WA,然后RE201,然后RE215(这个东西…最后确认是某个节点的father是它自己,然后不断的把size增大…就溢出了),最后AC.还有比较囧的,我的程序一度无法编译…后来发现是因为数组开的太大,到了几百M.似乎object里面的这个错误检查不出?
这道题其实也很简单了,题目描述都不用发,注释里都写的很清楚了…不过考到了平衡树的所有操作.里面删除大于等于k的所有数,似乎Splay最简单…然后还有Treap据说也可以和Splay一样做,别的平衡树都要一个一个删.我这个程序就是Splay的…效率不错.
虽然AC了也很恶心…因为用了object…所以400+行…不过object在那些并查集+平衡树啊,线段树套平衡树啊,还有我一直没做的线段树+LCA之类的题目中还是挺有用的,至少过程不会混淆了.
{ superbt - sqybi’s code - Splay - delete出错: “if son[1, y] <> 0 then father[son[1, y]] := z;” 写作 “if son[1, y] <> 0 then father[son[1, y]] := son[1, z];”}{$APPTYPE CONSOLE}//for my winstyprogram superbt_sqybi; const fin = ’superbt.in’; fout = ’superbt.out’; nn = 10000000; unable = 100000000;
type TSplayTree = object private root, […]
Read Full Post |
Make a Comment ( 6 so far )
Posted on 三月 19th, 2008.
一个晚上,在Nxun和MaShuo的帮助下,终于AC了URAL的1158…
这道题是一个自动机上的DP,算是挺经典的了.
首先按照那些forbidden words建立自动机,并在适当的位置标注该位置是某个单词的结尾.然后,f[i, j]表示当前在自动机上走第i步,走到了Trie树的第j号结点.则f[i, j] -> f[i+1, pre]; f[i+1, k]; 0.其中,pre代表在自动机上不断找pre找到的那个结点…不太好表述,就是说在下面没有孩子结点的时候不是向上走么…然后就是最后走到的那个结点…f[i+1, k]是正常情况,就是k是j的孩子结点,然后就f[i+1, k] <- f[i+1, k] + f[i, j].0是说,对于上面的那个f[i+1, k],若k是一个单词的结束,那么肯定不能到k啊…所以f[i+1, k] <- 0.
发现自动机上的DP还挺难表述…
不过要注意一点的是,比如i结点是j结点的pre,那么如果i是一个单词的结束被打上标记,j也要被打上标记(就是我在程序里用//important!注释标注的那一句).刚开始的WA就是这个原因.
这道题的提交结果:WA on Test 2; WA on Test 13; AC.第一次的WA很无语…BFS和跑自动机写到了一起…转移方程不对…还好挺好改.
{ URAL 1158; Censored! - sqybi’s code - 自动机+DP}//for my winsty{$APPTYPE CONSOLE}program ural1158_sqybi; const nn = 50; mm = 50; pp = 10; rr = 10; […]
Read Full Post |
Make a Comment ( 2 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 )
« Previous Entries