1689: [Usaco2005 Open] Muddy roads 泥泞的路 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 311 Solved: 227 [Submit][Status][Discuss] Description Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools. Farmer John has a …

题目链接：hdu4513 题意：给出一个n的数的序列，求出一个最长的回文字串，并且满足从[l,mid]单调增（非严格单调，可以相等），[mid,r]单调减（同样是可以相等） 思路：manacher...int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。 /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 20时32分45秒 File Name :code/hdu/4513.cpp …

poj 3294 题意：先做个简单替换，然后求替换后的字符串的最长回文串，以及这个最长回文串的开始和结束位置。 思路：manacher..需要注意的是，返回下标的时候如果字符串长度为偶数，那么中间是没有字符的。。。需要特判一下。。（我的做法是left+(ans%2==0); /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 19时40分06秒 File Name :code/hdu/3294.cpp …

poj3974 题意：求最大长度的回文字串。 思路：manacher裸题，用来练习算法。 /* *********************************************** Author :111qqz Created Time :2016年04月18日 星期一 16时32分25秒 File Name :code/poj/3974.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

题目链接 题意：求一个字符串中的最长回文串。 思路：昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。 于是去学习了一发。 感觉这篇博客讲得最详细manachar算法学习 于是切了个模板题练手。 先简单说下我对这个算法的理解，等做一些题目以后再来总结一发。 我觉得manachar算法最关键的一点是，如果你枚举回文串的中心位置，当你枚举到i的时候，那么i之前的位置回文串长度的最大值是已经确定的了。 换句话说，后面的中心位置不会影响前面的中心位置的答案。 于是可以利用前面已经做过的匹配来获得一些信息，避免了重复。 不过讲真。。。O(n)的复杂度。。这算法还是相当让人感到震撼的。。。 更具体的部分见代码注释。。。 …

最近各种比赛各种滚粗。。。 武大。。。武科大。。。地大。。。还有在路上的华农以及我科校赛。。。 然而还有10天考试。 然而还有15天要搞定OS大作业，然而我还没开始。 和小可算是彻底闹僵了。。。。虽然完全不懂是怎么回事。。。妹子的心思啊。。。完全搞不懂。。。 就当她只活在我记忆中吧。 明天武大校赛，晚安。

1657: [Usaco2006 Mar]Mooo 奶牛的歌声 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 634 Solved: 447 [Submit][Status][Discuss] Description Farmer John's N (1 <= N <= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a …

1656: [Usaco2006 Jan] The Grove 树木 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 143 Solved: 88 [Submit][Status][Discuss] Description The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting …

3407: [Usaco2009 Oct]Bessie's Weight Problem 贝茜的体重问题 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 88 Solved: 79 [Submit][Status][Discuss] Description 贝茜像她的诸多姊妹一样，因为从约翰的草地吃了太多美味的草而长出了太多的赘肉．所以约翰将她置于一个及其严格的节食计划之中．她每天不能吃多过H(5≤日≤45000)公斤的干草．贝茜只能吃一整捆干草；当她开始吃一捆干草的之后就再也停不下来了．她有一个完整 的N(1≤N≤500)捆可以给她当作晚餐的干草的清单．她自然想要尽量吃到更多的干草．很 …