特色文章

随笔

心里好累,今天也快期末考试了。今天2016年12月30日。放3天假。我决定以后每周五都刷1个小时的OJ。写此随笔立誓!
计划:阅读刘汝佳的教材,一点一滴从第一章开始做习题。
希望一年后的NOIP能拿到一等奖!

数据结构 邓俊辉 PA#1 灯塔(LightHouse) 题解

灯塔(LightHouse)


Description

As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input

1st line: N

2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).

Output

How many pairs of lighthourses can beacon each other

( For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same )

Example

Input


1
2
3
4
3
2 2
4 3
5 1

Output


1
1

Restrictions

For 90% test cases: 1 <= n <= 3 * 105

For 95% test cases: 1 <= n <= 106

For all test cases: 1 <= n <= 4 * 106

For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same.

1 <= x, y <= 10^8

Time: 2 sec

Memory: 256 MB

Hints

The range of int is usually [-231, 231 – 1], it may be too small.

描述

海上有许多灯塔,为过路船只照明。

(图一)

如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。

(图二)

若灯塔A、B均在对方的照亮范围内,则称它们能够照亮彼此。比如在图二的实例中,蓝、红灯塔可照亮彼此,蓝、绿灯塔则不是,红、绿灯塔也不是。

现在,对于任何一组给定的灯塔,请计算出其中有多少对灯塔能够照亮彼此。

输入

共n+1行。

第1行为1个整数n,表示灯塔的总数。

第2到n+1行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。

输出

1个整数,表示可照亮彼此的灯塔对的数量。

样例

见英文题面

限制

对于90%的测例:1 ≤ n ≤ 3×105

对于95%的测例:1 ≤ n ≤ 106

全部测例:1 ≤ n ≤ 4×106

灯塔的坐标x, y是整数,且不同灯塔的x, y坐标均互异

1 ≤ x, y ≤ 10^8

时间:2 sec

内存:256 MB

提示

注意机器中整型变量的范围,C/C++中的int类型通常被编译成32位整数,其范围为[-231, 231 – 1],不一定足够容纳本题的输出。

继续阅读

数据结构 邓俊辉 PA#1 范围查询(Range) 题解

范围查询(Range)
Description
Let S be a set of n integral points on the x-axis. For each given interval [a, b], you are asked to count the points lying inside.

Input
The first line contains two integers: n (size of S) and m (the number of queries).

The second line enumerates all the n points in S.

Each of the following m lines consists of two integers a and b and defines an query interval [a, b].

Output
The number of points in S lying inside each of the m query intervals.

Example
Input

5 2
1 3 7 9 11
4 6
7 12
Output

0
3
Restrictions
0 < = n, m <= 5 * 10^5 For each query interval [a, b], it is guaranteed that a <= b. Points in S are distinct from each other. Coordinates of each point as well as the query interval boundaries a and b are non-negative integers not greater than 10^7. Time: 2 sec Memory: 256 MB 描述 数轴上有n个点,对于任一闭区间 [a, b],试计算落在其内的点数。 输入 第一行包括两个整数:点的总数n,查询的次数m。 第二行包含n个数,为各个点的坐标。 以下m行,各包含两个整数:查询区间的左、右边界a和b。 输出 对每次查询,输出落在闭区间[a, b]内点的个数。 样例 见英文题面 限制 0 ≤ n, m ≤ 5×105 对于每次查询的区间[a, b],都有a ≤ b 各点的坐标互异 各点的坐标、查询区间的边界a、b,均为不超过10^7的非负整数 时间:2 sec 内存:256 MB 继续阅读

Openjudge 求排列的逆序数

求排列的逆序数
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较,比如可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1,i2,…,in,如果其中存在j,k,满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。显然,由1,2,…,n 构成的所有n!个排列中,最小的逆序数是0,对应的排列就是1,2,…,n;最大的逆序数是n(n-1)/2,对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列,求它的逆序数。

输入
第一行是一个整数n,表示该排列有n个数(n < = 100000)。 第二行是n个不同的正整数,之间以空格隔开,表示该排列。 输出 输出该排列的逆序数。 样例输入 6 2 6 3 4 5 1 样例输出 8 提示 1. 利用二分归并排序算法(分治); 2. 注意结果可能超过int的范围,需要用long long存储。 来源 习题(15-4) 继续阅读

Openjudge 汉诺塔问题 题解

6261:汉诺塔问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面。
这是一个著名的问题,几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:18,446,744,073,709,551,615
这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔,但很难用计算机解决64层的汉诺塔。

假定圆盘从小到大编号为1, 2, …

输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目,后三个字符表示三个杆子的编号。
输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式,即把编号为3的盘子从a杆移至b杆。
样例输入
2 a b c
样例输出
a->1->c
a->2->b
c->1->b
真心是经典问题啊!

先贴代码:
继续阅读

Openjudge 爬楼梯 题解

3089:爬楼梯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
树老师爬楼梯,他可以每次走1级或者2级,输入楼梯的级数,求不同的走法数
例如:楼梯一共有3级,他可以每次都走一级,或者第一次走一级,第二次走两级
也可以第一次走两级,第二次走一级,一共3种方法。

输入
输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 < = N <= 30 输出 不同的走法数,每一行输入对应一行输出 样例输入 5 8 10 样例输出 8 34 89 这个好像就有点类似于动态规划的感觉咯。但是其实这还是动规里最简单的题。但是初学感觉有点难度了。233 继续阅读

Openjudge 菲波那契数列

1755:菲波那契数列
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数a,要求菲波那契数列中第a个数是多少。
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 < = a <= 20) 输出 输出有n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数的大小 样例输入 4 5 2 19 1 样例输出 5 1 4181 1 继续阅读

00后在知乎 假装万能组 感想

最近这两天知乎被00后刷屏了,甚至在2月11日知乎的大V轮子哥都来参观并回答了问题“如何看待00后《知乎 •「假装万能组」成立宣言》?”:

现在,作为这个事件的亲历者,想从自己个人的角度尽量客观来陈述一下这前前后后发生的事实,并抒发我自己的一些感受。
首先是这个00er微信交流群的创建:根据施子怡的文章千赞以上99/00后答主及其高赞回答 一览(含小姑娘们的照骗XD)的发布时间,应在2月4日,我从我的知乎推荐里刷到了这条消息。感叹00后如此之牛的同时,我顺手点开了知乎评论区。瞬间就看到了Becal老杨的建议:

在看似没有人响应该同学创建00er群的情况下,我就自己创建了一个QQ群,并发在了评论区底下,欢迎他们加入。

事情不久就有了新的变化,我的一位朋友拉我进入微信群,当时微信群里还只有二十多个人。(这部分没有截图,只能口述,请谅解)当时群的主办者也许根本就没有想到要成立一个所谓的“假装万能组”(00后在知乎 ·「假装万能组」成立宣言)。当时我们就在不断的商议入群的标准。在商议的过程中,有人说:

最后主办者刘梓珊、施子怡(下文简称刘、施)就决定先让我们这些不符合标准的童鞋退群,然后经由他们商议一天之后,大概得出了这个结果:

我本来是想打破砂锅也要进群的,但是看到了当时一位同学对群的评价:

因为上述的硬性标准和这位同学的否定,我就没有想着再进群了,之后的一切动向,都是我从各种微信截图中得来的。
发上截图来:


其它的截图就不发了,太多了。发上来也没有什么意义。
后来发生了一系列事件,例如:
ziwen建小群退大群事件:


其它关于ziwen和flyinet的事件我就不说了,毕竟我也不太清楚嘛。主要就是扒皮嘛。现在这两个人是一个人撑不下去了,把知乎简介改了;另外一个人死撑着吧。
不过,还好,专栏发出的第一篇文章【低龄留学】初中就出国的姑娘在过怎么样的生活?让我们这些旁观者又看到了新一代00后的希望。(自己就是00后)

现在说一说我个人的感受吧,也是从知乎上总结下来的:
原问题集锦:如何看待00后《知乎 •「假装万能组」成立宣言》?
(1)管理者没有干货
(2)有些人手把权利不放松,各种面具伪装

(3)领域不同

说实话,看到了知乎上各种不同的观点,真是大开眼界啊。很多人比我写的好多了,希望大家积极关注这件事情的进展。
请关注:如何看待00后《知乎 •「假装万能组」成立宣言》?
最后说一句,仁者见仁,智者见智。
嗯,就这样。

Openjudge扩号匹配问题

2705:扩号匹配问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用”$”标注,不能匹配的右括号用”?”标注.
输入
输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100
注意:cin.getline(str,100)最多只能输入99个字符!
输出
对每组输出数据,输出两行,第一行包含原始输入字符,第二行由”$”,”?”和空格组成,”$”和”?”表示与之对应的左括号和右括号不能匹配。
样例输入
((ABCD(x)
)(rttyy())sss)(
样例输出
((ABCD(x)
$$
)(rttyy())sss)(
? ?$

用递归不会做,只能用栈做。
继续阅读

Openjudge 逆波兰表达式

1696:逆波兰表达式
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ – * /四个。
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。
可直接用printf(“%f\n”, v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
提示
可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。
来源
计算概论05

感受到咱们国家的前缀表达式和递归真是博大精深啊!!!!
继续阅读