卢俊达

农场有n种产品，他们之间可以通过牲畜或机械进行加工转化。转化形式为：1单位的产品A可以转化为x单位的产品B，其中x是大于0的实数。另外，每一种产品有不同的售价，第i种产品的单价为Pi。现给出若干初始产品，请将其经过适当加工转化，然后全部卖出，使得最终获利最大。

又是一道看完题就立马产生思路的水题，不过计算几何都是无比麻烦的，忍了好久终于下定决心要AC了它。忍了好久！

平面上有n个圆，给定他们各自的圆心和半径。保证任意两个圆不会互相重叠。现在求一个大圆，他的圆心与某个给定圆的圆心重合，且对于每一个给定的圆，大圆至少覆盖该圆面积的一半。求出满足要求的大圆的最小半径。

你有n个整数，A1、A2、…、AN。你需要处理两种操作。

• 将给定范围内的每个数字加上一个给定的值。
• 求一个给定范围内的数字的总和。

平面上有一些“回型”图案，每一个“回型”是由一个大矩形中间挖去一个小矩形构成，大小矩形的四边都平行于坐标轴。

现在有n个不同大小的“回型”图案，他们可能互相重叠，请求出被他们所覆盖的平面的总面积。

首先恭喜自己，终于写出了能在POJ上排第一名的代码。其次为自己惋惜下，判重时少了个“j!=x”的条件，找了n久才发现这个小bug，这要是在赛场上，肯定悔死了。首先用spfa做，怎么都找不出错误，甚至以为自己模板写错了，再用dijkstra做，发现依然wa，才觉得不是模板问题。

哥伦布要从野人手里买20种货物。用以下四种种方法可以买到货物：

• 按货物的价格（以金币为单位）付足金币。
• 对于每个货物，可以用一个玻璃珠代替一个金币。
• 用等价的其他种类货物交换。
• 用价格更低的货物加上金币来交换。

问每种物品至少需要花多少金币才能买到。

教室里有 N*M 个座位，每个座位有一个“舒适值”。上课之前，有K个学生进入教室来占座。每个学生进入教室的时间都不同，且进入教室后会立马占座（忽略占座时间），每个学生都会按下述规则占座。

• 每个学生会占T个座位，其中一个座位是自己的，其他是朋友的。
• 学生会优先选择同一行相邻的T个座位占座，并且他会坐在最左边。
• 如果有多个方案，那么他将选择能使自己“舒适值”最高的方案。
• 如果没办法帮朋友占座，就只给自己占，并选择“舒适值”最高的座位。

根据所给条件，输出每个人自己占据的座位的坐标。

小镇有n场婚礼在一天之内矩形，第i场婚礼的开始时间为Si，结束时间为Ti。在每一场婚礼中，有一个重要仪式，即牧师给予两位新人传达主的祝福。对于第i场婚礼，祝福仪式可以在[Si,Ti]中任何时候举行，但是必须超过总时间的一半以上。

小镇只有一位牧师，所有的祝福仪式都必须要他在场。同时，牧师必须在整数时刻开始或者结束祝福仪式，不过他可以在结束一场之后立刻开始另一场。

现在给你所有婚礼的信息，请问是否能够安排好一个祝福仪式的顺序，使得牧师能够给所有新人带去祝福。

给出一个元素个数为n的序列num[]，元素值两两不同，问序列中满足 num[i]<num[j]<num[k] 或 num[i]>num[j]>num[k] （i<j<k） 的三元子序列的个数是多少。