分类 解题报告 下的文章

SDUT 3648 迷の有序序列(动态规划)解题报告


题面

迷の有序序列
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
n个数,每次可以选择其中一个数移动到序列任意位置。 至少操作几次能让该序列有序

Input
多组输入,输入到文件结束。 每组输入一个正整数n(0 < n <= 1000) 之后一行输入n个正整数xi(0 < xi < 10^9),表示原始序列

Output
对于每组输入,输出一个整数,表示让序列变为有序所需要的最少操作次数 Hint: 第三组可以选择把1移到2前
也可以把2移动到1后

Example Input
3
1 2 3
3
3 2 1
3
2 1 3

Example Output
0
0
1

Author
LeiQ

















SDUT 3661 MoutainTop(单调栈)解题报告


题面

MoutainTop
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
金石山脉有n个山峰,一字排开,从西向东依次编号为1, 2, 3, ……, n。编号为i的山峰高度为hi。每个山峰的高度两两不同
小木示从西向东依次爬过这n个山峰,到每一个山峰的山顶的时候,他都会往西边眺望,并且会记录下自己能看到的山峰的个数。
(比如说小木示现在在4号山峰,前四号山峰的高度分别为9,4,5,1。他现在能看到的山峰个数就是2,因为第二个山峰被第三个山峰挡住了)
严格的来说,小木示在i位置的时候,对于一个山峰j (j < i),如果不存在一个山峰k满足hj < hk (j < k < i)。则山峰j是可见的。
小木示把自己记录的山峰的个数加和作为这次爬山的快乐值,现在给你n个山峰的高度,求小木示的快乐值。

Input
多组输入,首先输入一个n(1<=n<=10^6),表示山峰的个数。 接下来一行n个数,表示对应山峰的山峰的高度(1<=h<=10^6)。

Output
输出小木示的快乐值

Example Input
4
1 6 5 1

Example Output
4

Author
JueChen














SDUT 3271 飞花的传送门(凸包)解题报告


题面

飞花的传送门
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













POJ 1094 Sorting It All Out(拓扑排序)解题报告


题目链接

题目翻译

描述

一个升序序列中不同元素之间可以用带小于号的关系式来从小到大排列元素。例如,有序序列 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" 指最终确定的升序序列。