标签归档:THUOJ

CG2017 PA1-1 Convex Hull (凸包)

开始接触计算几何啦!!!

CG2017 PA1-1 Convex Hull (凸包)


Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

经过了第一章的学习,想必你对于凸包的认识已经非常深刻。是的,凸包是计算几何的核心问题,也是一种基础性的几何结构。因此你的第一项编程任务,就是来实现这样的一个算法。

具体地,对于平面上的任意一组点,请构造出对应的凸包,并在经过编码转换之后输出所有极点的信息。

Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

第一行是一个正整数首行为一个正整数n > 0,即输入点的总数。

随后n行中的第k行给出第k个点:

pk = (xk, yk), k = 1, 2, …, n

这里,xk与yk均为整数,且二者之间以空格分隔。

Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

若 { s1, s2, …, sh } 为所有极点的编号, h ≤ n,则作为你的解答,请输出以下整数:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

Sample Input (输入样例)

1
2
3
4
5
6
7
8
9
10
11
10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8

Sample Output (输出样例)

1
7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)

Limitation (限制)

  • 3 ≤ n ≤ 10^5
  • Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
  • All points on extreme edges are regarded as extreme points and hence should be included in your solution.
  • Time Limit: 2 sec
  • Space Limit: 512 MB
  • 3 ≤ n ≤ 10^5
  • 所有点的坐标均为范围(-10^5, 10^5)内的整数,且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
  • 极边上的所有点均被视作极点,故在输出时亦不得遗漏
  • 时间限制:2 sec
  • 空间限制:512 MB

Hint (提示)

Use the CH algorithms presented in the lectures.

课程中讲解过的凸包算法

 

分数:92.5
使用Graham Scan算法。凸包板子题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
struct point {
    long long x, y, id;
    point() :x(0), y(0) {}
    point(long long x, long long y) :x(x), y(y) {}
    bool operator ==(const point& p) const {
        return x == p.x && y == p.y;
    }
}PP; //PP: Polar Point
vector<point> points;
long long area2(point p, point q, point s) {
    /*
    |p.x p.y 1|
    |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)
    |s.x s.y 1|
    */

    return p.x * q.y - s.x * q.y
        + q.x * s.y - q.x * p.y
        + s.x * p.y - p.x * s.y;
}
bool toLeftTest(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) > 0;
}
bool toLeftTest2(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) >= 0;
}
bool cmp(const point& p1, const point& p2) { // Sort according to polar angle
    return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2);
}
point LTL(vector<point>& points) { //Lowest then leftmost
    point ltl = points[0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)
            ltl = points[i];
    }
    return ltl;
}
vector<point> grahamScan() {
    PP = LTL(points);
    sort(points.begin(), points.end(), cmp);
    vector<point> S, T;
    S.push_back(points[0]); S.push_back(points[1]);
    for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);
    while (!T.empty()) {
        if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {
            S.push_back(T[T.size() - 1]);
            T.pop_back();
        }
        else S.pop_back();
    }
    return S;
}
int main() {
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        point tmp;
        cin >> tmp.x >> tmp.y;
        tmp.id = i;
        points.push_back(tmp);
    }
    vector<point> result;
    if (points.size() > 2)result = grahamScan();
    else result = points;
    long long res = 1;
    for (int i = 0; i < result.size(); i++) {
        //cout << result[i].id << endl;//debug
        res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);
    }
    res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);
    cout << res;
}

数据结构 邓俊辉 PA#4 循环移位(Cycle) 题解

循环移位(Cycle)


Description

Cycle shifting refers to following operation on the sting. Moving first letter to the end and keeping rest part of the string. For example, apply cycle shifting on ABCD will generate BCDA. Given any two strings, to judge if arbitrary times of cycle shifting on one string can generate the other one.

Input

There m lines in the input, while each one consists of two strings separated by space. Each string only contains uppercase letter ‘A’~’Z’.

Output

For each line in input, output YES in case one string can be transformed into the other by cycle shifting, otherwise output NO.

Example

Input

1
2
3
4
AACD CDAA
ABCDEFG EFGABCD
ABCD ACBD
ABCDEFEG ABCDEE

Output

1
2
3
4
YES
YES
NO
NO

Restrictions

0 <= m <= 5000

1 <= |S1|, |S2| <= 10^5

Time: 2 sec

Memory: 256 MB

描述

所谓循环移位是指。一个字符串的首字母移到末尾, 其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA

给定两个字符串,判断它们是不是可以通过若干次循环移位得到彼此

输入

由m行组成,每行包含两个由大写字母’A’~’Z’组成的字符串,中间由空格隔开

输出

对于每行输入,输出这两个字符串是否可以通过循环移位得到彼此:YES表示是,NO表示否

样例

见英文题面

限制

0 ≤ m ≤ 5000

1 ≤ |S1|, |S2| ≤ 10^5

时间:2 sec

内存:256 MB

开心死啦!本来就觉得这道题必须写KMP来着,结果搞了个c++stl糊弄过去了……还好THUOJ没有删掉头文件 /笑,倒是其他的map list queue还有什么 algorithm 都删啦! /偷笑 /捂脸
继续阅读

数据结构 邓俊辉 PA#3 重名剔除(Deduplicate)题解

重名剔除(Deduplicate)


Description

Mr. Epicure is compiling an encyclopedia of food. He had collected a long list of candidates nominated by several belly-gods. As candidates in list are nominated by several people, duplication of name is inevitable. Mr. Epicure pay you a visit for help. He request you to remove all duplication, which is thought an easy task for you. So please hold this opportunity to be famous to all belly-gods.

Input

1 integer in fist line to denote the length of nomination list. In following n lines, each nomination is given in each line.

Output

All the duplicated nomination (only output once if duplication appears more multiple times), which is sorted in the order that duplication appears firstly.

Example

Input

1
2
3
4
5
6
7
8
9
10
11
10
brioche
camembert
cappelletti
savarin
cheddar
cappelletti
tortellni
croissant
brioche
mapotoufu

Output

1
2
cappelletti
brioche

Restrictions

1 < n < 6 * 10^5

All nominations are only in lowercase. No other character is included. Length of each item is not greater than 40.

Time: 2 sec

Memory: 256 MB

Hints

Hash

描述

Epicure先生正在编撰一本美食百科全书。为此,他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手,其中自然不乏重复的提名,故必须予以筛除。Epicure先生因此登门求助,并认定此事对你而言不过是“一碟小菜”,相信你不会错过在美食界扬名立万的这一良机

输入

第1行为1个整数n,表示提名清单的长度。以下n行各为一项提名

输出

所有出现重复的提名(多次重复的仅输出一次),且以其在原清单中首次出现重复(即第二次出现)的位置为序

样例

见英文题面

限制

1 < n < 6 * 10^5

提名均由小写字母组成,不含其它字符,且每项长度不超过40

时间:2 sec

空间:256 MB

提示

散列

继续阅读

数据结构 邓俊辉 PA#4 任务调度(Schedule)题解

任务调度(Schedule)


Description

A HPS cluster is equipped with a unique task scheduler. To be simple, it is assumed that this cluster doesn’t support multiple tasks running at the same time, such that only one task is allowed to be in running state at any moment. Initially, the priority of ever task is denoted by an integer which is called priority number. The smaller priority number stands for high priority. If two tasks have same task number, the priority is decided in the ASCII order of task name. Following this policy, resources, such as CPU, are always occupied by the task with minimum priority number. When one task is finished, the one with minimum priority number in the rest tasks is picked to execute. The finished task won’t quit immediately. The priority number is doubled and put back to the task set. Once the priority number is greater or equal to 2^32, this task is deleted from the task set.

Given initial priority setting of every task, your job is to predict the running order of a batch of tasks.

Input

First line contains two integers, says n and m. n stands for the number of tasks in initial state. m stands for the length of predicted sequence. Every line is ended by a line break symbol. In each one of the following n lines, an integer and a string are included. This string is shorter than 8, which only contains lowercase letters and numbers. The integer is priority number and the string is the task name. The integer and string is separated by space.

Output

At most m lines, each one contains a string. Output the name of tasks according to the order that tasks are executed. If the number of executed tasks is less than m, then output all the executed tasks.

Example

Input

1
2
3
4
3 3
1 hello
2 world
10 test

Output

1
2
3
hello
hello
world

Restrictions

0 <= n <= 4,000,000

0 <= m <= 2,000,000

0 < Priority number < 2^32

No tasks have same name

Time: 2 sec

Memory: 512 MB

Hints

Priority queue

描述

某高性能计算集群(HPC cluster)采用的任务调度器与众不同。为简化起见,假定该集群不支持多任务同时执行,故同一时刻只有单个任务处于执行状态。初始状态下,每个任务都由称作优先级数的一个整数指定优先级,该数值越小优先级越高若优先级数相等,则任务名ASCII字典顺序低者优先。此后,CPU等资源总是被优先级数最小的任务占用;每一任务计算完毕,再选取优先级数最小下一任务。不过,这里的任务在计算结束后通常并不立即退出,而是将优先级数加倍(加倍计算所需的时间可以忽略)并继续参与调度;只有在优先级数不小于2^32时,才真正退出

你的任务是,根据初始优先级设置,按照上述调度原则,预测一批计算任务的执行序列。

输入

第一行为以空格分隔的两个整数n和m,n为初始时的任务总数,m为所预测的任务执行序列长度,每行末尾有一个换行符

以下n行分别包含一个整数和一个由不超过8个小写字母和数字组成的字符串。前者为任务的初始优先级数,后者为任务名。数字和字符串之间以空格分隔

输出

最多m行,各含一个字符串。按执行次序分别给出执行序列中前m个任务的名称,若执行序列少于m,那么输出调度器的任务处理完毕前的所有任务即可。

样例

见英文题面

限制

0 ≤ n ≤ 4,000,000

0 ≤ m ≤ 2,000,000

0 < 每个任务的初始优先级 < 2^32

不会有重名的任务

时间:2 sec

内存:512 MB

提示

优先级队列

必须要用坑爹的setvbuf:
继续阅读

数据结构 邓俊辉 PA#3 无线广播(Broadcast) 题解

无线广播(Broadcast)


描述

某广播公司要在一个地区架设无线广播发射装置。该地区共有n个小镇,每个小镇都要安装一台发射机并播放各自的节目。

不过,该公司只获得了FM104.2和FM98.6两个波段的授权,而使用同一波段的发射机会互相干扰。已知每台发射机的信号覆盖范围是以它为圆心,20km为半径的圆形区域,因此,如果距离小于20km的两个小镇使用同样的波段,那么它们就会由于波段干扰而无法正常收听节目。现在给出这些距离小于20km的小镇列表,试判断该公司能否使得整个地区的居民正常听到广播节目。

输入

第一行为两个整数n,m,分别为小镇的个数以及接下来小于20km的小镇对的数目。 接下来的m行,每行2个整数,表示两个小镇的距离小于20km(编号从1开始)。

输出

如果能够满足要求,输出1,否则输出-1。

输入样例

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

输出样例

1
1

限制

1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

不需要考虑给定的20km小镇列表的空间特性,比如是否满足三角不等式,是否利用传递性可以推出更多的信息等等。

时间:2 sec

空间:256MB

提示

BFS

继续阅读

THU2017spring 2-3 Rebuild 题解

THU2017spring 2-3 Rebuild


描述

某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的先序遍历序列和中序遍历序列,试输出其对应的后序遍历序列。

输入

第一行为一个整数n。

第二、三行,即已知的先序、中序遍历序列,数字之间以空格分隔。

输出

仅一行。

若所给的先序、中续遍历序列的确对应于某棵二叉树,则输出其后序遍历序列,数字之间以空格分隔。否则,输出-1。

输入样例1

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

输出样例1

1
4 5 2 3 1

输入样例2

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

输出样例2

1
-1

输入样例3

1
2
3
8
5 2 4 1 3 6 7 8
4 2 1 5 3 7 6 8

输出样例3

1
4 1 2 7 8 6 3 5

限制

1 <= n <= 500,000

输入和输出的遍历序列均为[1, n]内整数的一个排列,整数间均以空格分隔。

时间:1 sec

空间:256 MB

提示

● 注意观察特殊节点在不同遍历序列中的位置

提示(.docx)

对应输入样例1的树结构:

先序遍历序列:12453
中序遍历序列:42513
注意到根节点就是先序序列的首元素,找到根节点后,根据根节点在中序序列中的位置,可划分出左右子树。

 

代码:(一个点TLE没过,其它都OK)
继续阅读

THU2017spring 1-4 Hospital 题解

THU2017spring 1-4 Hospital


描述

有n个村落分布在一条公路的沿线,为方便村民们就医,现打算在公路沿线修建一所医院。

由于各村落人数、年龄分布不同等原因,每个村落对医院的需求程度也不同。这里需求程度以一个非负的权值w表示:w越大,就医需求越大。对于一个选址方案,Σwi*di作为衡量其合理性的指标,其中wi和di分别表示第i个村落的权值和距离医院的距离,该指标越小,对应的选址就越优。请给出医院修建的最优位置。

输入

共n+1行。

第一行包含一个整数n;

以下共n行,每行包含两个整数:第一个为对应村落的一维坐标xi,第二个为对应村落的权值wi。

输出

共两行。

第一行为医院的最优坐标。

第二行为对应的最小权值,即医院选择最优坐标时的Σwi*di。

注意,如果有多个坐标权值均为最小值,请给出这些坐标中的最小者。

输入样例

1
2
3
4
3
3 5
7 11
5 6

输出样例

1
2
5
32

限制

1 <= n <= 300,000

村落的地址坐标是[0, 32767]的整数。

村落的权值是[1, 10^8]的整数。

时间:1 sec

空间:256 MB

提示

一级提示

● 可以在预处理时将坐标相同的村落合并。

二级提示

● 考虑医院选址向左(或向右)移动一个单位对Σwi*di的影响何时为正、何时为负。

● 注意你的程序是否能正确处理“有多个坐标权值均为最小值”的情况。

● 虽然最终选址坐标在int范围内,但计算Σwi*di的中间过程不一定在int范围内;可以使用long long,其表示的范围是[-2^63, 2^63)。

我也实在不知道该怎么做,参考twd2的做法什么“加权中位数”,胡作吧。最后80分。。

继续阅读

THU2017spring 2-2 Train 题解

THU2017spring 2-2 Train


描述

某列车调度站的铁道联接结构如图所示。

其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S的容量有限,同时驻留的车厢不得超过m节。

设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道,按照以上交通规则,这些车厢能否以{a1, a2, …, an}的次序,重新排列后从B端驶出。

输入

共两行。

第一行为两个整数n,m。

第二行为以空格分隔的n个整数,保证为{1, 2, …, n}的一个排列,表示待判断可行性的驶出序列{a1,a2,…,an}。

输出

仅一行。若驶出序列可行,则输出Yes;否则输出No。

输入样例1

1
2
5 2
1 2 3 5 4

输出样例1

1
Yes

输入样例2

1
2
5 5
3 1 2 4 5

输出样例2

1
No

限制

1 <= n <= 100,000

0 <= m <= 100,000

时间:1 sec

空间:256 MB

提示

这题边界条件比MOOC卡的严多了,需要考虑0的情况:
也是栈混洗,把原来的代码搞过来的……(逃)
继续阅读

数据结构 邓俊辉 PA#2 旅行商(TSP) 题解

旅行商(TSP)


Description

Shrek is a postman working in the mountain, whose routine work is sending mail to n villages. Unfortunately, road between villages is out of repair for long time, such that some road is one-way road. There are even some villages that can’t be reached from any other village. In such a case, we only hope as many villages can receive mails as possible.

Shrek hopes to choose a village A as starting point (He will be air-dropped to this location), then pass by as many villages as possible. Finally, Shrek will arrived at village B. In the travelling process, each villages is only passed by once. You should help Shrek to design the travel route.

Input

There are 2 integers, n and m, in first line. Stand for number of village and number of road respectively.

In the following m line, m road is given by identity of villages on two terminals. From v1 to v2. The identity of village is in range [1, n].

Output

Output maximum number of villages Shrek can pass by.

Example

Input

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

Output

1
3

Restrictions

1 <= n <= 1,000,000

0 <= m <= 1,000,000

These is no loop road in the input.

Time: 2 sec

Memory: 256 MB

Hints

Topological sorting

描述

Shrek是一个大山里的邮递员,每天负责给所在地区的n个村庄派发信件。但杯具的是,由于道路狭窄,年久失修,村庄间的道路都只能单向通过,甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。

Shrek希望知道如何选定一个村庄A作为起点(我们将他空投到该村庄),依次经过尽可能多的村庄,路途中的每个村庄都经过仅一次,最终到达终点村庄B,完成整个送信过程。这个任务交给你来完成。

输入

第一行包括两个整数n,m,分别表示村庄的个数以及可以通行的道路的数目。

以下共m行,每行用两个整数v1和v2表示一条道路,两个整数分别为道路连接的村庄号,道路的方向为从v1至v2,n个村庄编号为[1, n]。

输出

输出一个数字,表示符合条件的最长道路经过的村庄数。

样例

见英文题面

限制

1 ≤ n ≤ 1,000,000

0 ≤ m ≤ 1,000,000

输入保证道路之间没有形成环

时间:2 sec

空间:256 MB

提示

拓扑排序

继续阅读

数据结构 邓俊辉 PA#2 真二叉树重构(Proper Rebuild)题解

真二叉树重构(Proper Rebuild)


Description

In general, given the preorder traversal sequence and postorder traversal sequence of a binary tree, we cannot determine the binary tree.

Figure 1

In Figure 1 for example, although they are two different binary tree, their preorder traversal sequence and postorder traversal sequence are both of the same.

But for one proper binary tree, in which each internal node has two sons, we can uniquely determine it through its given preorder traversal sequence and postorder traversal sequence.

Label n nodes in one binary tree using the integers in [1, n], we would like to output the inorder traversal sequence of a binary tree through its preorder and postorder traversal sequence.

Input

The 1st line is an integer n, i.e., the number of nodes in one given binary tree,

The 2nd and 3rd lines are the given preorder and postorder traversal sequence respectively.

Output

The inorder traversal sequence of the given binary tree in one line.

Example

Input

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

Output

1
4 2 5 1 3

Restrictions

For 95% of the estimation, 1 <= n <= 1,000,00

For 100% of the estimation, 1 <= n <= 4,000,000

The input sequence is a permutation of {1,2…n}, corresponding to a legal binary tree.

Time: 2 sec

Memory: 256 MB

Hints

Figure 2

In Figure 2, observe the positions of the left and right children in preorder and postorder traversal sequence.

描述

一般来说,给定二叉树的先序遍历序列和后序遍历序列,并不能确定唯一确定该二叉树。

(图一)

比如图一中的两棵二叉树,虽然它们是不同二叉树,但是它们的先序、后序遍历序列都是相同的。

但是对于“真二叉树”(每个内部节点都有两个孩子的二叉树),给定它的先序、后序遍历序列足以完全确定它的结构。

将二叉树的n个节点用[1, n]内的整数进行编号,输入一棵真二叉树的先序、后序遍历序列,请输出它的中序遍历序列。

输入

第一行为一个整数n,即二叉树中节点的个数。

第二、三行为已知的先序、后序遍历序列。

输出

仅一行,给定真二叉树的中序遍历序列。

样例

见英文题面

限制

对于95%的测例:1 ≤ n ≤ 1,000,000

对于100%的测例:1 ≤ n ≤ 4,000,000

输入的序列是{1,2…n}的排列,且对应于一棵合法的真二叉树

时间:2 sec

空间:256 MB

提示

观察左、右孩子在先序、后序遍历序列中的位置

重温视频05e5-3

目测一辈子也忘不了二叉树重构怎么写了…………
继续阅读