题目链接：1155 Heap Paths (30 分)

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

HDU 2063 过山车 (匈牙利算法)

题目链接：HDU 2063

Problem Description

RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？

题目链接：HDU 2512

Problem Description

因为长期钻研算法， 无暇顾及个人问题，BUAA ACM/ICPC 训练小组的帅哥们大部分都是单身。某天，他们在机房商量一个绝妙的计划”一卡通大冒险”。这个计划是由wf最先提出来的，计划的内容是，把自己的联系方式写在校园一卡通的背面，然后故意将自己的卡”遗失”在某处（如水房，TD，食堂，主M。。。。）他们希望能有MM看到他们遗失卡，能主动跟他们联系，这样就有机会请MM吃饭了。他们决定将自己的一卡通夹在基本相同的书里，然后再将书遗失到校园的各个角落。正当大家为这个绝妙的计划叫好时，大家想到一个问题。很明显，如果只有一张一卡通，那么只有一种方法，即，将其夹入一本书中。当有两张一卡通时，就有了两种选择，即，将两张一卡通夹在一本书里，或者分开夹在不同的书里。当有三张一卡通时，他们就有了5种选择，即：

((A),(B),(C)) , ((A,B),(C)), ((B,C),(A)), ((A,C),(B)) ,((A,B,C)) 于是，

这个邪恶计划的组织者wf希望了解，如果ACM训练对里有n位帅哥（即有N张一卡通），那么要把这些一卡通夹到书里有多少种不同的方法。

PTA 1067 Sort with Swap(0, i) (贪心)

题目链接：1067 Sort with Swap(0, i) (25 分)

题意

给定长度为 $n$ 的排列，如果每次只能把某个数和第 $0$ 个数交换，那么要使排列是升序的最少需要交换几次。

题目链接：HDU 4513

Problem Description

吉哥又想出了一个新的完美队形游戏！

假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] … h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：

1、挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的；

2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意；

3、从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <= H[3] …. <= H[mid]。

现在吉哥想知道：最多能选出多少人组成新的完美队形呢？

题目链接：POJ 3974

Description

Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, “Can you propose an efficient algorithm to find the length of the largest palindrome in a string?”

A string is said to be a palindrome if it reads the same both forwards and backwards, for example “madam” is a palindrome while “acm” is not.

The students recognized that this is a classical problem but couldn’t come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said “Okay, I’ve a better algorithm” and before he starts to explain his idea he stopped for a moment and then said “Well, I’ve an even better algorithm!”.

If you think you know Andy’s final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.

最长回文子串

回文串就是原串和反转字符串相同的字符串。比如 aba，acca。前一个是奇数长度的回文串，后一个是偶数长度的回文串。

最长回文子串就是一个字符串的所有子串中，是回文串且长度最长的子串。

题目链接：LightOJ 1418

Problem Description

I have bought an island where I want to plant trees in rows and columns. So, the trees will form a rectangular grid and each of them can be thought of having integer coordinates by taking a suitable grid point as the origin.

But, the problem is that the island itself is not rectangular. So, I have identified a simple polygonal area inside the island with vertices on the grid points and have decided to plant trees on grid points lying strictly inside the polygon.

Figure: A sample of my island

For example, in the above figure, the green circles form the polygon, and the blue circles show the position of the trees.

Now, I seek your help for calculating the number of trees that can be planted on my island.

题目链接：POJ 1410

Description

You are to write a program that has to decide whether a given line segment intersects a given rectangle.

An example:

line: start point: (4,9)

end point: (11,2)

rectangle: left-top: (1,5)

right-bottom: (7,1)

Figure 1: Line segment does not intersect rectangle

The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.

题目链接：HDU 1028