分类目录归档：算法

THU2017spring 1-2 Company 题解

发表评论

THU2017spring 1-2 Company

描述

公司有n个员工，编号1 ~ n。员工数量众多，需要你为他们编写一个管理系统。

员工上班时都要登录管理系统登记一个code，离开要从管理系统上注销，员工也可以随时更新自己的code。到了下班时间，所有员工都会自动注销。公司管理人员随时都可能想要知道有多少员工上班，以及任一员工登记的code。

输入

第一行两个整数n、m。接下来m行，每行都是以下内容之一：

I a c	//Log In：员工a登录，code为c。若a已登录，则将code更新为c
O a		//Log Out：编号为a的员工注销。若a未登录，则注销无效
C			//Close：到下班时间，所有员工注销
N			//Number：询问有多少员工正在上班
Q a		//Query：询问员工a的code（若未登录或已注销，视为-1）

输出

一个整数，是所有询问（N、Q）的答案之和（int表示，自动溢出，不用管溢出部分）

输入样例

10 8
I 1 2
I 1 4
Q 1
C
I 2 4
O 2
Q 2
N

输出样例

3
//“Q 1”答案是4，“Q 2”答案是-1，“N”答案是0，所有答案之和为3

限制

n <= 10,000,000

m <= 1,000,000

1<=a<=n

code为[0, 2^31)的整数

空间限制：256 MB

时间限制：2 sec

提示

一级提示

测试数据中，每种操作都可能频繁出现，或很少出现。因此，你的算法需要应对所有可能的情况。

● Bitmap / 常数时间初始化的数组

● Bitmap: 习题解析[2-34]，实例参考[2-35]，[2-36]

二级提示

● 避免频繁初始化整个数组。

● 可以借助Bitmap记录数组的各元素是否已被初始化。将一个（或所有）元素置为未初始化状态，实质上只需要打破“校验环”两个验证条件中的任何一个，考虑如何打破校验条件的复杂度最低。

● 还可以使用“懒删除”策略。

● 参考习题[2-34]。

用scanf(“%c”, …)或getchar()读入一个字符时，可能会读到空格、制表符、回车符或换行符，尽量避免使用这个方法。使用scanf(“%s”, …)会自动过滤空白字符。

继续阅读 →

THU2017spring 1-1 Team 题解

发表评论

Xuetangx:Data Structure and Algorithm of Tsinghua University 晋级全校公选课 PA1 THU2017spring 1-1 Team

THU2017spring 1-1 Team

描述

教练员A、B和C将要从编号为1到n的队员中挑选自己的队员。为公平起见，每个教练都根据自己的喜好程度将队员排序；你负责根据以下规则为他们分配队员。

你拿到的数据是a、b、c三个数组，表示三个教练对队员的喜好程度排序，每个数组都是数字1到n的一个排列，下标越小表示教练越喜欢该队员。你的分组规则是，从还未被分配的队员中找一个教练A最喜欢的队员分到A组；然后，在未分配的队员中分配教练B最喜欢的队员到B组；然后是教练C；再是教练A、B……依次类推直到所有队员分配完毕。

现在队员k希望知道自己被分配给哪位教练，请你来告诉他。

输入

共5行。

第1行包含一个整数n。

第2至4行依次是数组a、b和c，每行都是整数[1, n]的一个排列。

第5行包含一个整数k。

输出

仅一个字符，A、B或C，表示队员k被分配给哪位教练。

输入样例1

3
1 2 3 
1 2 3 
1 2 3 
3

输出样例1

C

输入样例2

5
1 2 3 4 5 
1 3 5 4 2 
5 4 3 2 1 
4

输出样例2

B

限制

1 <= n <= 500,000

1 <= k <= n

时间：1 sec

空间：256 MB

提示

● 大体上，1 sec内，O(n)的算法可以通过n = 10,000,000规模的数据，O(nlogn)通过500,000规模，O(n^2)通过5,000规模。

● 本题等一些复杂度是O(n)的题目受限于scanf(“%d”, …)的读入速度，但又不希望通过读取二进制文件等不直观的方式增加同学们的负担。

● “懒删除”策略：从序列中移除一个元素时，可以只标记它，下次读取时跳过它，而不需要将它后面的元素都向前挪一位。思考如何做标记，能在每个教练员选队员时，快速地知道该队员是否已被选走。

Tips：清零或赋值时，memset比手动赋值快几倍。输入数据时，有时scanf比cin快一些。关于读写速度，请参考Tutorial Collection #1 5.大数据(Big)。

继续阅读 →

Openjudge 最佳加法表达式 题解

发表评论

最佳加法表达式

总时间限制:
1000ms
内存限制:
65536kB
描述
给定n个1到9的数字，要求在数字之间摆放m个加号(加号两边必须有数字），使得所得到的加法表达式的值最小，并输出该值。例如，在1234中摆放1个加号，最好的摆法就是12+34,和为36
输入
有不超过15组数据
每组数据两行。第一行是整数m，表示有m个加号要放( 0<=m<=50)
第二行是若干个数字。数字总数n不超过50,且 m <= n-1
输出
对每组数据，输出最小加法表达式的值
样例输入
2
123456
1
123456
4
12345
样例输出
102
579
15
提示
要用到高精度计算，即用数组来存放long long 都装不下的大整数，并用模拟列竖式的办法进行大整数的加法。
来源
Guo Wei

极其坑爹的一道题！要写高精度！坑人！
继续阅读 →

Openjudge Zipper

发表评论

Zipper

总时间限制:
1000ms
内存限制:
65536kB
描述
Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.

For example, consider forming “tcraete” from “cat” and “tree”:

String A: cat
String B: tree
String C: tcraete

As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming “catrtee” from “cat” and “tree”:

String A: cat
String B: tree
String C: catrtee

Finally, notice that it is impossible to form “cttaree” from “cat” and “tree”.

输入
The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.

For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.

输出
For each data set, print:

Data set n: yes

if the third string can be formed from the first two, or

Data set n: no

if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.

样例输入
3
cat tree tcraete
cat tree catrtee
cat tree cttaree
样例输出
Data set 1: yes
Data set 2: yes
Data set 3: no
来源
Pacific Northwest 2004

继续动规：
继续阅读 →

Openjudge 拦截导弹 题解

发表评论

拦截导弹

总时间限制:
1000ms
内存限制:
65536kB
描述
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。
输入
输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。
输出
输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。
样例输入
8
300 207 155 300 299 170 158 65
样例输出
6
来源
医学部计算概论2006期末考试题

简单动态规划：
继续阅读 →

数据结构 邓俊辉 PA#1 祖玛(Zuma) 题解

发表评论

祖玛(Zuma)

Description

Let’s play the game Zuma!

There are a sequence of beads on a track at the right beginning. All the beads are colored but no three adjacent ones are allowed to be with a same color. You can then insert beads one by one into the sequence. Once three (or more) beads with a same color become adjacent due to an insertion, they will vanish immediately.

Note that it is possible for such a case to happen for more than once for a single insertion. You can’t insert the next bead until all the eliminations have been done.

Given both the initial sequence and the insertion series, you are now asked by the fans to provide a playback tool for replaying their games. In other words, the sequence of beads after all possible eliminations as a result of each insertion should be calculated.

Input

The first line gives the initial bead sequence. Namely, it is a string of capital letters from ‘A’ to ‘Z’, where different letters correspond to beads with different colors.

The second line just consists of a single interger n, i.e., the number of insertions.

The following n lines tell all the insertions in turn. Each contains an integer k and a capital letter Σ, giving the rank and the color of the next bead to be inserted respectively. Specifically, k ranges from 0 to m when there are currently m beads on the track.

Output

n lines of capital letters, i.e., the evolutionary history of the bead sequence.

Specially, “-” stands for an empty sequence.

Example

Input

ACCBA
5
1 B
0 A
2 B
4 C
0 A

Output

ABCCBA
AABCCBA
AABBCCBA
-
A

Restrictions

0 <= n <= 10^4

0 <= length of the initial sequence <= 10^4

Time: 2 sec

Memory: 256 MB

Hints

List

描述

祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。

开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。

游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。

输入

第一行是一个由大写字母’A’~’Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。

第二行是一个数字n，表示整个回放过程共有n次操作。

接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。

输出

输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。

如果轨道上已没有珠子，则以“-”表示。

样例

见英文题面

限制

0 ≤ n ≤ 10^4

0 ≤ 初始珠子数量 ≤ 10^4

时间：2 sec

内存：256 MB

提示

列表

普通字符串模拟即可：

继续阅读 →

数据结构 邓俊辉 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

3
2 2
4 3
5 1

Output

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
真心是经典问题啊！

先贴代码：
继续阅读 →