hdu 4513 吉哥系列故事——完美队形II (回文串,manacher)

题目链接:hdu4513

题意:给出一个n的数的序列,求出一个最长的回文字串,并且满足从[l,mid]单调增(非严格单调,可以相等),[mid,r]单调减(同样是可以相等)

思路:manacher…int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。

 

poj 3294 Girls’ research (manacher,回文串)

poj 3294
题意:先做个简单替换,然后求替换后的字符串的最长回文串,以及这个最长回文串的开始和结束位置。
思路:manacher..需要注意的是,返回下标的时候如果字符串长度为偶数,那么中间是没有字符的。。。需要特判一下。。(我的做法是left+(ans%2==0);

 

 

 

poj 3974 Palindrome (最长回文字串,manacher裸题)

poj3974
题意:求最大长度的回文字串。
思路:manacher裸题,用来练习算法。

hdu 3068 最长回文(O(n)求回文串,manacher算法模板题)

题目链接
题意:求一个字符串中的最长回文串。
思路:昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。

于是去学习了一发。

感觉这篇博客讲得最详细manachar算法学习

于是切了个模板题练手。

先简单说下我对这个算法的理解,等做一些题目以后再来总结一发。
我觉得manachar算法最关键的一点是,如果你枚举回文串的中心位置,当你枚举到i的时候,那么i之前的位置回文串长度的最大值是已经确定的了。
换句话说,后面的中心位置不会影响前面的中心位置的答案。
于是可以利用前面已经做过的匹配来获得一些信息,避免了重复。
不过讲真。。。O(n)的复杂度。。这算法还是相当让人感到震撼的。。。
更具体的部分见代码注释。。。

20160416

最近各种比赛各种滚粗。。。
武大。。。武科大。。。地大。。。还有在路上的华农以及我科校赛。。。
然而还有10天考试。
然而还有15天要搞定OS大作业,然而我还没开始。

和小可算是彻底闹僵了。。。。虽然完全不懂是怎么回事。。。妹子的心思啊。。。完全搞不懂。。。
就当她只活在我记忆中吧。

明天武大校赛,晚安。

BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节 (单调栈)

1660: [Usaco2006 Nov]Bad Hair Day 乱发节

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 872  Solved: 415
[Submit][Status][Discuss]

Description

Input

* Line 1: 牛的数量 N。

* Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。

Output

* Line 1: 一个整数表示c[1] 至 c[N]的和。

Sample Input

6
10
3
7
4
12
2

输入解释:

六头牛排成一排,高度依次是 10, 3, 7, 4, 12, 2。

Sample Output

5

3+0+1+0+1=5

HINT

Source

思路:裸的单调栈。

 

BZOJ 1657: [Usaco2006 Mar]Mooo 奶牛的歌声 (单调栈)

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 stickler for precision). Each cow moos at some volume v in the range 1..10,000. This “moo” travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow’s right or left). The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow.

Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。

Input

* Line 1: A single integer, N.

* Lines 2..N+1: Line i+1 contains two space-separated integers, h and v, for the cow standing at location i.

第1行:一个正整数N.

第2到N+1行:每行包括2个用空格隔开的整数,分别代表站在队伍中第i个位置的奶牛的身高以及她唱歌时的音量.

Output

* Line 1: The loudest moo volume heard by any single cow.

队伍中的奶牛所能听到的最高的总音量.

Sample Input

3
4 2
3 5
6 10

INPUT DETAILS:

Three cows: the first one has height 4 and moos with volume 2, etc.

Sample Output

7

HINT

队伍中的第3头奶牛可以听到第1头和第2头奶牛的歌声,于是她能听到的总音量为2+5=7.虽然她唱歌时的音量为10,但并没有奶牛可以听见她的歌声.

Source

Silver

 

思路:窝想到了是单调栈。。。但是细节想不清楚。。大抵还是对单调栈不够熟悉吧

 

BZOJ 1656: [Usaco2006 Jan] The Grove 树木(神奇的bfs之射线法)

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 position? She’s just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn’t think you could pass ‘through’ the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take. Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here’s a typical example where ‘.’ is pasture (which Bessie may traverse), ‘X’ is the grove of trees, ‘*’ represents Bessie’s start and end position, and ‘+’ marks one shortest path she can walk to circumnavigate the grove (i.e., the answer): …+… ..+X+.. .+XXX+. ..+XXX+ ..+X..+ …+++* The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she’s starting ‘outside’ the grove instead of in a sort of ‘harbor’ that could complicate finding the best path.

牧场里有一片树林,林子里没有坑.
    贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能走对角线格子.牧场被分成R行C列(1≤R≤50,1≤C≤50).下面是一张样例的地图,其中“.”表示贝茜可以走的空地,  “X”表示树林,  “*”表示起点.而贝茜走的最近的路已经特别地用“+”表示出来.
 
题目保证,最短的路径一定可以找到.

Input

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).

    第1行输入R和C,接下来R行C列表示一张地图.地图中的符号如题干所述.

Output

* Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.

    输出最少的步数.

Sample Input

6 7
…….
…X…
..XXX..
…XXX.
…X…
……*

Sample Output

13
思路:我的思路是错的。。就不说了。。这题太神辣。。。用来求解绕过某一区域的最短路。。做法是找一个点做一条平行于边界的射线(单向)到另一边界。
射线法大概就是:如果和多变形交了奇数次,就说明在多边形内部,否则在外部。
讲真。。还不是特别明白。。。感觉和计算几何比较有关系。。。

BZOJ 3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题(01背包)

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)捆可以给她当作晚餐的干草的清单.她自然想要尽量吃到更多的干草.很自然地,每捆干草只能被吃一次(即使在列表中相同的重量可能出现2次,但是这表示的是两捆干草,其中每捆干草最多只能被吃掉一次).

给定一个列表表示每捆干草的重量Si(1≤Si≤H),求贝茜不超过节食的限制的前提下可以吃掉多少干草(注意一旦她开始吃一捆干草就会把那一捆干草全部吃完).

Input

第1行:两个由空格隔开的整数日和N.

第2到第N+1行:第i+l行是一个单独的整数,表示第i捆干草的重量Si.

Output

 

一个单独的整数表示贝茜在限制范围内最多可以吃多少公斤的干草.

Sample Input

56 4
15
19
20
21

Sample Output

56

HINT

有四捆草,重量分别是15,19,20和21.贝茜在56公斤的限制范围内想要吃多少就可以吃多少.

贝茜可以吃3捆干草(重量分别为15,20,21).恰好达到她的56公斤的限制.

 

 

 

BZOJ 1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店 (母函数,高精度)

1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 353  Solved: 190
[Submit][Status][Discuss]

Description

Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are: 1 @ US$3 + 1 @ US$2 1 @ US$3 + 2 @ US$1 1 @ US$2 + 3 @ US$1 2 @ US$2 + 1 @ US$1 5 @ US$1 Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

    约翰到奶牛商场里买工具.商场里有K(1≤K≤100).种工具,价格分别为1,2,…,K美元.约翰手里有N(1≤N≤1000)美元,必须花完.那他有多少种购买的组合呢?

Input

A single line with two space-separated integers: N and K.

    仅一行,输入N,K.

Output

A single line with a single integer that is the number of unique ways FJ can spend his money.

    不同的购买组合数.

Sample Input

5 3

Sample Output

5
思路:母函数裸题,还卡个高精度。。差评。。。

BZOJ 1653: [Usaco2006 Feb]Backward Digit Sums(暴力)

 

1653: [Usaco2006 Feb]Backward Digit Sums

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 349  Solved: 258
[Submit][Status][Discuss]

Description

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this: 3 1 2 4 4 3 6 7 9 16 Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities. Write a program to help FJ play the game and keep up with the cows.

Input

* Line 1: Two space-separated integers: N and the final sum.

Output

* Line 1: An ordering of the integers 1..N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

Sample Input


4 16

Sample Output


3 1 2 4
OUTPUT DETAILS:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4
is the lexicographically smallest.

思路:n很小。。一开始做得时候把公式推错了。。3+3算成了4.我的内心是崩溃的。。
其实直接暴力就好。可以用next_permutation来生成全排列,然后判断是否合法。

 

tmp

hdu 2586 How far away ? (tarjan算法求LCA模板题)

题目链接
题意:一棵树,给出n-1个边权,然后q组查询,每组查询询问两个点之间的距离。
思路:

dfs跑出根到每个点的距离,设为dis[i]
那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];

其中lca(u,v)为u,v的最近公共祖先。 这个式子是利用容斥,其实也很直观。。不理解的话画个图就好。

所以终点就是求两个点的LCA.

据说有好多种做法。今天学习了大概是最简单的一种?
学习链接

 

我的理解:其实本质就是利用并查集。。在访问一个点的子树的时候,这个点其所有子树的祖先。。。由于祖先的节点比较小,所以merge的时候要f[大]=小…

要注意Tarjan 算法是离线算法。

哦对了。。这题要扩展语句才能过,不然会RE…

 

 

树边,前向边,后向边,横叉边

转载自: 原文链接

树边,前向边,后向边,横叉边,应该说,不是一个图本身有的概念,应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树(森林),在这个树上才有了这些概念。对图进行DFS,可以从任意的顶点开始,遍历的方式也是多样的,所以不同的遍历会得到不同的DFS树,进而产生不同的树边,前向边,后向边,横叉边。所以这4种边,是一个相对的概念。
在图的遍历中,往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义
vis = 0,表示该顶点没没有被访问
vis = 1,表示该顶点已经被访问,但其子孙后代还没被访问完,也就没从该点返回
vis = 2,,表示该顶点已经被访问,其子孙后代也已经访问完,也已经从该顶点返回
可以vis的3种值表示的是一种顺序关系和时间关系

《算法导论》334页有这4种边的准确定义,在此不累述
DFS过程中,对于一条边u->v
vis[v] = 0,说明v还没被访问,v是首次被发现,u->v是一条树边
vis[v] = 1,说明v已经被访问,但其子孙后代还没有被访问完(正在访问中),而u又指向v?说明u就是v的子孙后代,u->v是一条后向边,因此后向边又称返祖边
vis[v] = 3,z说明v已经被访问,其子孙后代也已经全部访问完,u->v这条边可能是一条横叉边,或者前向边

注意:树边,后向边,前向边,都有祖先,后裔的关系,但横叉边没有,u->v为横叉边,说明在这棵DFS树中,它们不是祖先后裔的关系它们可能是兄弟关系,堂兄弟关系,甚至更远的关系,如果是dfs森林的话,u和v甚至可以在不同的树上

在很多算法中,后向边都是有作用的,但是前向边和横叉边的作用往往被淡化,其实它们没有太大作用。

BZOJ 1652: [Usaco2006 Feb]Treats for the Cows (区间dp)

1652: [Usaco2006 Feb]Treats for the Cows

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 290  Solved: 226
[Submit][Status][Discuss]

Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: * The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. * Like fine wines and delicious cheeses, the treats improve with age and command greater prices. * The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). * Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:

•零食按照1..N编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每
  天可以从盒子的任一端取出最外面的一个.
•与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.
  •每份零食的初始价值不一定相同.约翰进货时,第i份零食的初始价值为Vi(1≤Vi≤1000).
  •第i份零食如果在被买进后的第a天出售,则它的售价是vi×a.
  Vi的是从盒子顶端往下的第i份零食的初始价值.约翰告诉了你所有零食的初始价值,并希望你能帮他计算一下,在这些零食全被卖出后,他最多能得到多少钱.

Input

* Line 1: A single integer,

N * Lines 2..N+1: Line i+1 contains the value of treat v(i)

Output

* Line 1: The maximum revenue FJ can achieve by selling the treats

Sample Input

5
1
3
1
5
2

Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).

Sample Output

43

OUTPUT DETAILS:

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order
of indices: 1, 5, 2, 3, 4, making 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43.

题意:一列数,可以从两段取,每天取一个数,第t天取到第i个数的价值是t*v[i],问能取到的最大价值是多少。
思路:能看出是dp.不过状态表示这一步就错了。。。我想的是dp[i]表示第i天取能得到的最大价值。。。然后转移方程就推不对了23333.
实际上这种从两段搞的问题的状态,还是要两个变量来表示状态比较好。
dp[i][j]表示最左端为i,最右端为j能得到的最大价值。
而且这道题的划分状态也很厉害。反正我是没想到。
定义了k表示为当前剩余区间的长度。
容易知道k=j-i+1;
那么t=n+i-j,j = n-k+1;
像很多dp一样,这道题也需要倒着推。。。
也就是从长度为1的区间推到长度为n的区间。
转移方程为dp[i][j] = max(dp[i+1][j]+t*v[i],dp[i][j-1]*v[j])
(注意观察,(i,j)的状态是由(i+1,j)或者(i,j-1)得到的,因为是从里向外推。)