发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接:http://poj.org/problem?id=3660
对于每一头牛，能够确切判断它的名次，当且仅当它与其他n-1头牛都能直接判断胜负。对于给定的战胜关系a->b，我们连一条从a到b的边。在生成的图上跑一遍Floyd，就可以判断任意两点是否直接或间接相连了，此时枚举每一个点，如果该点与其它n-1个点都相连（包括正向和反向，即战胜和被战胜），那么该点的名次就是确定的。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
这题是刘汝佳老师《算法竞赛入门经典-训练指南》上字符串一节的例题，下文的思路直接来自书上的解析，代码来自代码仓库（需翻墙）
把所有单词插入一棵Trie树，则在深度为depth的分叉点的任何两个字符串都需要比较2*depth-1次。
因为字符集比较大，需要用左儿子右兄弟法保存Trie。这种方法类似于保存图的邻接表。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
这题是刘汝佳老师《算法竞赛入门经典-训练指南》上字符串一节的例题，下文的思路直接来自书上的解析，代码来自代码仓库（需翻墙）
可以想到这样的递推法：令d(i)表示从字符i开始的字符串（即后缀S[i..L]）的分解方案数，则d(i)=sum{d(i+len(x))|x为一个单词并且是S[i..L]的一个前缀}。
如果直接枚举x并判断其是否为S[i..L]的前缀会超时，这时可以构建一颗Trie树，并插入所有单词，然后在Trie树中「查找」S[i..L]，经过一个单词结点，就能找到一个上述状态转移方程的x，因为每个单词长度最长为100，所以查找次数最多300000 * 100不会超时。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接http://poj.org/problem?id=1127

题目涉及两个问题：1、判断两个线段是否直接相交（跨立的规范相交或一直线端点在另一直线上的非规范相交） 2、判断两个线段是否能够间接相交

解决第一个问题可以n^2的两两比较一遍，套用计算几何的相交模板即可，第二个问题可以用Floyd传递闭包来解决。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=2318
这题是计算几何题，需要用到叉积判断点在线段的左边还是右边。
暴力的话n^2的复杂度应该会超时，这里用了二分的方法。把地图的左右边界各自作为一条直线插入，并且考虑到存在点落在边界的情况，这两条新加的直线要对应向地图外偏移一点。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=2752
题目要求找出所有相同的前后缀，想到KMP算法在计算fail(next)指针时也是找寻相同的前后缀，所以套用KMP算法的模板。getnxt函数执行结束后，从nxt[len]开始向前跳并统计位置即可。

阅读全文 »

发表于 | 更新于 |

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://codeforces.com/problemset/problem/343/A
参考博客：TofuNotHere

本来以为这题是超级麻烦的搜索的，结果这题真是在考物理啊。。

以下引用自TofuNotHere的博客：

对于电阻来说将k个电阻串联和并联关系完全反转的话，阻值的变化特性是变为原阻值的倒数，因而我们可以利用这一特性不停的将并联关系转化为串联关系，而A/B可化为假分数形式n+a/B，期中整数部分由n个电阻串联，分数部分由一个并联电阻组组成，将并联化为串联关系，即将分数部分倒过来，不断反复，累加得到答案

阅读全文 »