分类 数据结构与算法 下的文章
飞花的传送门
Time Limit: 1000ms Memory limit: 65536K题目描述
飞花壕最近手头比较宽裕，所以想买两个传送门来代步（夏天太热，实在是懒得走路）。平面上有N个传送门，飞花壕想要挑两个距离最远的传送门带回家（距离为欧几里得距离，即两点之间直线距离）。请你帮他算一算他所挑选的最远的两个传送门有多远。
输入
多组输入。对于每组输入，第一行输入一个整数N（2 <= N <= 50000），接下来从第2行到第N+1行，每行两个整数（Xi，Yi），代表第i个传送门的坐标（-1000000 <= Xi , Yi <= 1000000）。
数据为随机生成。
输出
输出一个整数，代表飞花壕要挑选的两个传送门的距离的平方。示例输入
4
0 0
0 1
1 1
1 0示例输出
2提示
来源
GLSilence
一个升序序列中不同元素之间可以用带小于号的关系式来从小到大排列元素。例如，有序序列 A, B, C, D 中包含关系 A < B, B < C 和 C < D。在本题中，我们会给你一个形如 "A < B" 的关系集合，请你决定由此构成的有序序列是否唯一。
输入包含多组实例。每组实例的第一行包含两个正整数 n, m，前者表示待排序对象的数量，2 <= n <= 26，待排序对象是字母表中前 n 个大写字母；后者表示题目实例中给出的 "A < B" 形式的关系数量。接下来有 m 行，每行包含一对关系，每对关系由三个字符组成：一个大写字母、一个小于号和另一个大写字母。不会出现超出前 n 个大写字母的数据。当 n = m = 0 时输入结束。
对于每组测试实例，输出一行，每行会是以下三种情况之一：
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
其中 "xxx" 指有序序列被确定或被证明矛盾时已处理的关系数量，"yyy...y" 指最终确定的升序序列。
Flip Game
Time Limit: 1000MS Memory Limit: 65536KDescription
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
- Choose any one of the 16 pieces.
- Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwwwSample Output
4
Source
Northeastern Europe 2000
装备合成
Time Limit: 1000MS Memory limit: 65536K题目描述
小白很喜欢玩儿LOL，但是无奈自己是个坑货，特别是在装备的选择和合成上，总是站在泉水里为选装备而浪费时间。现在小白试图解决这个问题，为了使问题简单化，我们把游戏中的装备合成规则简化如下：
（1）装备的合成关系构成一棵合成关系树，如图(a)所示，装备的下级装备叫合成小件，直接连接的叫直接合成小件；上级装备叫合成件，直接连接的叫直接合成件。合成树上的每件装备都可以直接购买，如果钱不够也可以先购买这个装备的合成小件。
（2）每个装备都有一个合成价格和一个总价格，装备的总价格=该装备的合成价格+该装备所有直接合成小件的总价格之和（图(a)关系树上面显示的数字就是对应装备的总价格）。
（3）初始的时候（未拥有装备的任何部分），装备的当前价格等于总价格，当前价格会随着购买的小件而发生相应的变化。
（4）如果购买了某个装备，那么它所有上级可合成装备的当前价格都会相应地减少，减少的量等于这个装备的当前价格。
（5）如果购买了某个装备，那么它下级所有合成小件都会被购买，也就是说，这些小件都变成已拥有的状态，但是物品栏里只有最终合成的装备，因为是小件合成了这件装备。
（6）我们认为关系树上的每个装备的直接合成小件都不超过2件，关系树上同一件物品只会出现一次，我们也不考虑物品的出售问题，我们假设物品栏容量无限，金钱无限。
现在问题来了，按照格式给定一棵合成关系树，再给定一系列操作，完成相应的查询，具体格式见输入。输入
多组输入，对于每组数据：
第一行有两个整数n m，分别代表关系树中物品的数量和后续的操作数。（1 <= n,m <= 10^4）
接下来的n行，每行对应一件物品的描述，格式为equipment p k，分别代表装备的名称，合成价格，直接合成小件的个数，然后有k个合成小件的名称synthesis1 synthesis2 ... synthesisk。（1 <= p <=10^4 , k <= 2 , 所有物品名称只包含小写英文字母，长度不超过20）
接下来的m行，每行对应一个操作，格式如下：
（1）B equipment ，表示物品equipment被购买。
（2）Q equipment ，表示要查询物品equipment的当前价格。
其中equipment代表物品的名称，保证合法且存在于合成关系树中。
注意：如果B指令购买的装备是当前已经拥有的装备（包括小件），那么忽略该条B购买指令。特别地，如果你已经拥有某件装备，那么查询该物品的当前价格时应该输出这件物品的总价格而不是0输出
对于每次Q查询指令，输出一个整数，代表查询的物品的当前价格。示例输入
8 10
bannerofcommand 600 2 aegisofthelegion fiendishcodex
aegisofthelegion 400 2 nullmagicmantle crystallinebracer
fiendishcodex 465 1 amplifyingtome
nullmagicmantle 450 0
crystallinebracer 100 2 rubycrystal rejuvenationbead
amplifyingtome 435 0
rubycrystal 400 0
rejuvenationbead 150 0
B crystallinebracer
Q fiendishcodex
Q bannerofcommand
B nullmagicmantle
Q aegisofthelegion
B aegisofthelegion
Q bannerofcommand
Q crystallinebracer
B bannerofcommand
Q bannerofcommand示例输出
900
2350
400
1500
650
3000提示
来源
“师创杯”山东理工大学第八届ACM程序设计竞赛
*/
