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 )