分类目录归档:acm

[POJ 3084]

Panic Room

最小割

有向图上有n个结点,某些点有标记,要求对于某特定的m点,要割掉多少条边才能使从m点出发无法到达任何一个标记点。

题目数据范围很小,主要考察的还是最小割的建模,也即将图分成S、T两部分,S包含m,T包含所有标记点,求S和T间的最小割即可。

注意首先要判断是否无解,然后要合并必定可达的结点,最后用最大流即可。

ps: 这也是在poj上水掉的第300题,虽然还是很弱,也稍作纪念吧。

553_0

[POJ 3067]

Japan

树状数组

题意是,在左右两边各有m和n个点的二分图中有k条边(xi,yi),问这k条边之间两两相交了多少次(端点不算)。

首先读入每条边,然后按x由小到大排序,初始化ans=0,然后重复:
(1)将xi连续相同的一组边加入图中;
(2)对下一组中的每条边j,求与之前的边相交的次数,由于之前的边必有x<xj,因此求y>yj的边数即可。
最后输出ans即为答案。

其中的(1)和(2)可以用树状数组来实现:通过O(lgn)地修改、询问,可以使总时间复杂度达到O(klgn)。

树状数组的实现有个小技巧,x&-x可以O(1)地取到x最低位的1。

[POJ 1639]

Picnic Planning

度限制最小生成树

给出最多包含最多21个结点的无向图,边权值为正数,求这样的一棵最小生成树:与结点1相连的树边不超过m条。

解法是,先从图中剔除结点1,求最小生成森林。然后重复:遍历结点1相连的所有边,找(1)能联通某森林的最小边;(2)若(1)边不存在,则找加边之后作破圈操作能使树权减少最多的边。直到m次加边机会耗尽或者加边也无法减少树权。

一些小技巧:题目数据量很小,所以邻接矩阵也可以,但如果像我这样习惯用邻接表的话,对树边作标记的时候两个方向的边要同时标记。而由于加边时无向边对应的邻接表项是成对插入的,也即编号仅有最末位不同,所以^1就可以得到另一个方向的边了。这种用邻接表时修改边信息的做法很常用,最开始是在做费用流的题目时学到的。

[SPOJ 220]

Relevant Phrases of Annihilation

后缀数组

给出最多10个字符串,每个字符串长度最多10,000,求这样一个子串的长度:
(1) 在每个字符串中非重叠地出现了两次;
(2) 长度最长。

可以将10个字符串连接在一起,其中每个连接位置用一个大于128的唯一值来隔开不同字符串,然后求后缀数组。随后,可以二分答案,对于某个长度值m,判断:对于h数组中值>=m的某连续区间内,求每个子串对应的原字符串最左和最右子串的位置,若每个字符串中左右子串的位置差>=m,即两个子串非重叠,return 1。而每次某区间内无法满足时,直接从该区间下一个位置开始检查h数组。由此对于每个长度值进行判断的时间复杂度是O(n)的,这里n是后缀数组的长度,最多100,000。总体时间复杂度便是O(nlgn)的。

很好的题目……这题也是罗穗骞论文里推荐的最后一道例题了。虽然还是没太看懂他的DA和DC3,不过确实学到了很有趣的知识。

ps:也推荐一个最近发现的汽车网站:38号测试中心

[POJ 3415]

Common Substrings

后缀数组

给出两个长度最多100,000的字符串s和t,求s和t中所有长度大于K的相同子串配对数。

做法首先是将s[sl]置最大值,并将t放在s[sl]后,计算后缀数组。接下来需要顺序遍历h[n],遍历到位置i时,如果sa[i]属于s,那么找出0到i-1中所有属于t且与s公共后缀长度>=m的子串,并将累计的配对数记录以类似计数排序的方式记录为ab[n]中,sa[i]对应满足题意的配对总数即为ab[h[i]]。如果sa[i+1]也属于s,且h[i+1]>=h[i],那么sa[i+1]对应的配对数和sa[i]是相同的;若h[i+1]<h[i],那么也能根据ab[h[i+1]]来O(1)地得到结果。

这里在更新ab[n]时本来应该是分成ab[2][n],分别对属于s和属于t的后缀分别维护配对总数的,这样根据平摊分析构造ab的总时间复杂度就是O(n),但实现起来细节太多了容易错。而现在这种偷懒的做法会导致当sa[i]、sa[i+1]、sa[i+2]……分别属于s、t、s……且都满足h[]>=m时,需要反复重新计算ab,但这种情况实际上较少出现,所以并不会慢上太多。

ps:上周刚赶完第二篇论文,以为可以稍微轻松点了,结果马上又被安排写专利…… 总不会到时候真的让我写第三篇吧?

ps2:另外,最近也在看毛姆的《月亮和六便士》

[POJ 3264]

Balanced Lineup

RMQ

题意是,有长度最多50,000的正整数序列,最多200,000次询问,对于每次询问(l, r),需要输出下标[l, r]范围内序列最大值和最小值的差。

最近啃的是郭华阳的《RMQ与LCA问题》,敲了下基于倍增思想的ST算法。O(nlgn)预处理后,可以O(1)回答每次询问。

之前做这题用的是O(qlgn)的线段树:

[POJ 2406]

Power Strings

后缀数组(?)

题意是,给出一个最长1,000,000的字符串,求该字符串是否为某子串的完全重复,并输出最大的重复数。

……之前敲的快排二倍增完全没有任何AC的希望,贴了个基排二倍增TLE依旧,随后又颤抖着贴了一份DC3……2938ms刚好卡过……:

虽然罗穗骞神牛号称DC3实现得很精简……但是……这压行也太严重了吧……反正我是没怎么看懂……

另外贴一个之前自己写的KMP:

同样是O(n)的复杂度,却只跑了219ms。

总感觉后缀数组是重剑无锋呢,现在的功力要驾驭实在是比较吃力……

[POJ 1743]

Musical Theme

后缀数组。

这两天都在研究罗穗骞神牛的《后缀数组——处理字符串的有力工具》,很久以前就听过的数据结构,现在总算用到了。

题意是给出一个长20000的数组,值范围是1到88,问是否存在长度大于等于5的一个子串,其满足“变调”后非重叠地出现在原数组的其他位置。这里变调的意思是整个子串同时加上或减去某个值。

分析题意后可以发现,如果取值间的差值建立一个新数组,那么新数组上长度为m的非重叠重复出现的子串对应着原数组中长度为m+1的子串。这样就解决了“变调”的问题。

进一步分析,可以发现可以二分答案:对于某个值l,当m<=l时满足题意的子串总存在。从而将问题转化为判定性问题。 然后对每次枚举的m值,使用后缀数组建立的height[],便可O(n)地判断是否可行了。 不过由于建立数组时我只实现了基于快排的二倍增,因此总体复杂度被拖低成O(n(lgn)^2)了,g++下跑了610ms。

另外,这题之前也已经用字符串hash做过了的(半年前还在用数组实现hash表),竟然比后缀数组还要快些(g++ 438ms)……

ps: 又发现了一个很有趣的blog:Summer’s Mariner

[POJ 1200]

Crazy Search

字符串hash

很基本的hash题目,现在做这种程度的题10分钟就敲完1A了。整个程序都是模块化的,思路也能很自然地延伸。

[POJ 1421]

Peter’s Calculator

模拟(难)

给出一段程序,要求按照给定的运行方式,对每次PRINT操作判断是否有效,若有效还需求值。

并没有太多算法的题目,但各种细节很多

大致思路就是先将全部程序文本读入,进行预处理:记录每行程序的类型(赋值、打印或重置),并且
(1)如果是赋值,则对被赋值的变量进行编号,并将等号右边的内容以纯文本方式保存下来
(2)如果是打印,则检查被打印的变量之前是否存在相应赋值,若有则记录变量编号,若无则记录编号为-1
(3)如果是重置,无需特殊处理

然后就是求解了,按顺序对每行i进行处理,期间维护一个搜索赋值语句的上下界[es,ee],初始es=ee=0,并且
(1)如果是赋值,忽略
(2)如果是打印,则ee=i-1,并尝试对该变量求值,若成功则打印值,否则打印”UNDEF”
(3)如果是重置,则es=i+1

每次对变量id求值的操作可能涉及其他变量,因此使用递归结构。而要防止循环求值,因此初始化全0数组st[]来记录变量是否在递归栈中。每次递归内部结构大致如下:
(1)若st[id]!=0,直接返回;st[id]=1,按从后往前(从ee到es)的顺序找第一个对va赋值的语句
(2)对将赋值字符串中的所有变量调用递归求值,若某变量求值失败,直接返回
(3)用一个新字符串保存将赋值字符串中所有变量替换为值后的结果(必须不修改原来的赋值字符串),随后使用递归下降分析求解该字符串的值
(4)记录变量的值,st[id]=2

最后求值完毕后,若要打印的变量st[]为2,则表示成功求值。

程序的主要部分想清楚后实现也花了不少时间,最后则是在空格问题上卡了很久。

在POJ上做过最冷门的题目了,算上我也才53个人AC。但貌似数据比较弱哦,总觉得比想象中要顺利得多……