太空飞行计划

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1，E2， $\cdots$ ，Em}，和进行这些实验需要使用的全部仪器的集合 I={I1， I2， $\cdots $In}。 实验 Ej 需要用到的仪器是 I 的子集 Rj∈I。配置仪器 Ik 的费用为 Ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 Pj 美元。W 教授的任务是找出一个有效算法， 确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划，输出最大收益值。

没有上司的晚会

题目背景

poj2342

题目描述

Ural 大学有N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入格式

第一行一个整数 N (1<=N<=6000)。
接下来 N 行，第i+1行表示i 号职员的快乐指数Ri(-128<=Ri<=127) 。
接下来 N-1 行，每行输入一对整数 L 和 K。表示 K 是 L 的直接上司
最后一行输入0 0。

输出格式

输出最大的快乐指数。

麻烦的聚餐

题目描述

为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。
第i头奶牛有一张标明她用餐批次 D_i(1 <= D_i <= 3) 的卡片。虽然所有 N (1 <= N <= 30,000) 头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 111222333 或者 333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。
你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。

流星雨

题目描述

茜听说了一个骇人听闻的消息，一场流星雨即将袭击整个农场，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，贝茜开始担心自己的安全问题。以FJ牧场中最聪明的奶牛的名誉起誓，她一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 M 颗流星（1 <= M <= 50,000）会坠落在农场上，其中第 i 颗流星会在时刻 T_i （0 <= T_i <= 1,000）砸在坐标为（X_i, Y_i）（0 <= X_i <= 500；0 <= Y_i <= 500）的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 0 开始行动，它只能在第一象限中，平行于坐标轴行动，每 1 个时刻中，她能移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。

连线游戏

题目描述

Farmer John 最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着 $N(2 \leq N \leq 200)$ 个不重合的点的木板，其中第 $i$ 个点的横,纵坐标分别为 $X_i$ 和 $Y_i (-1000 \leq X_i, Y_i \leq 1000)$。

贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

输入格式

第 $1$ 行: 输入 $1$ 个正整数：$N$

第 $2 \cdots N+1$ 行: 第 $i+1$ 行用 $2$ 个用空格隔开的整数 $X_i, Y_i$，描述了点 $i$ 的坐标。

输出格式

输出 $1$ 个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数。

Network of Schools

题目背景

poj1236

题目描述

大致意思: $N(2 < N < 100)$ 各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。

问题：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。

车厢调度

题目描述

有一个火车站，铁路如图所示，每辆火车从 A 驶入，再从 B 方向驶出，同时它的车厢可以重新组合。假设从 A 方向驶来的火车有 n 节（n<=1000），分别按照顺序编号为 1，2，3， \cdots ，n 。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到 B 处的铁轨上。另外假定车站 C 可以停放任意多节车厢。但是一旦进入车站 C，它就不能再回到 A 方向的铁轨上了，并且一旦当它进入 B 方向的铁轨，它就不能再回到车站 C。

负责车厢调度的工作人员需要知道能否使它以 a1,a2, \cdots ,an 的顺序从 B 方向驶出，请来判断能否得到指定的车厢顺序。

表达式括号匹配

题目描述

假设一个表达式有英文字母（小写）,运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。

请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于 255，左圆括号少于 20 个。

输入格式

输入一行，一个表达式。

输出格式

如果括号匹配，输出“YES”,否则输出“NO”。

统计难题

题目背景

HDU 1251

题目描述

Ignatius 最近遇到一个难题，老师交给他很多单词(只有小写字母组成，不会有重复的单词出现)，现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。

输入格式

输入数据的第一部分是一张单词表（不超过 $10^4$ 个单词），每行一个单词，单词的长度不超过 10，它们代表的是老师交给 Ignatius 统计的单词，一个空行代表单词表的结束。第二部分是一连串的提问，每行一个提问，每个提问都是一个字符串（不超过 $10^4$ 个提问串）。
注意:本题只有一组测试数据，处理到文件结束。

Phone List

题目背景

HDU 1671

题目描述

给出一份电话号码列表，如果不存在有一个号码是另一个号码的前缀，我们就说这份电话号码列表是合法的。让我们看看如下号码列表：

1. Emergency 911
2. Alice 97625999
3. Bob 91125426

在这组号码中，我们不能拨通 Bob 的电话，因为当你按下 Bob 电话号码的前 $3$ 个数字 911 时，电话局会把你的拨号连接到 Emergency 的线路。

所以这组号码是不合法的。

SPFA

SPFA（Shortest Path Faster Algorithm）（队列优化）算法是求单源最短路径的一种算法，它还有一个重要的功能是判负环（在差分约束系统中会得以体现），在Bellman-ford算法的基础上加上一个队列优化，减少了冗余的松弛操作，是一种高效的最短路算法。

Dijkstra

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

最长子串

题目描述

给出一个全部由小写字母构成的字符串，要求从该串中找出满足下面条件的最长子串：

条件1：子串是连续的；

条件2：子串的长度是偶数；

条件3：沿子串的中心切开，对左右两部分的串按顺序进行比较，要求不同的字符对数 $N$ 不超过题目给出的一个限定值 $D$。
比如：abcaec 的 $N$ 值为 $1$。因为平分的两部分 abc 和 aec 比较，只有 $1$ 对字符不同：即 b 和 e，而其余字符都相同。

分析

二分答案题,先按绳子的长度进行升序排列,然后for循环二分100次就够了,避免while造成死循环,在 $O(n)$ 内枚举进行判断,所以时间复杂度为 $O(n \log n)$。
注意:一定要用double,float精度太低,否则直接wrong answer

HTML图片排版

float

使文字包围图片,只需要用style中的float即可。

1

style="float:left;"

margin

只使用float会出现一个问题,文字会紧贴图片,所以我们可以用margin来调整间距。

1

<img src="" style="float:left;margin-right:10px;margin-top:10px;margin-bottom:10px;">

Aggressive cows

题目背景

POJ2456

题目描述

农夫约翰搭了一间有 N 间牛舍的小屋。牛舍排在一条线上，第 i 号牛舍在 $X_i$ 的位置。但是他的 M 头牛对小屋很不高兴，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其他牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

输入格式

输入第一行: 两个正整数 N 和 M。
接下来 N 行，每行一个整数 $X_i$。

输出格式

一个整数，即最近的两头牛之间的最大距离。