bLue 发布的文章

SDUT 3460 Fighting_小银考呀考不过四级(递推)解题报告


题面

Fighting_小银考呀考不过四级
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
四级考试已经过去好几个星期了,但是小银还是对自己的英语水平担心不已。
小银打算好好学习英语,争取下次四级考试和小学弟小学妹一起拿下它!
四级考试的时候,监考老师会按考号分配固定的座位,但唯一不变的是每两个人之间肯定至少会留下两个空座位,原因相信大家都懂得。
那么问题来了,我们现在只关注教室里的一排座位,假设每排有n个座位,小银想知道这一排至少坐一个人的前提下,一共有多少种坐法。

Input
多组输入。
第一行输入整数n,代表教室里这一排的座位数目。(1 <= n <= 45)

Output
输出种类数目。输入输出各占一行,保证数据合法。

Example Input
1
3
5

Example Output
1
3
8

Hint

Author
Casithy

















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