5 2
2 3 3
某公司在对应聘者做过一轮笔试之后，从中选出n 人继续进行面试，每位应聘者被分配了一个整数ID。
为公平起见，组织者决定利用会议室外的圆桌，按以下方法“随机”确定面试顺序：第一个到达的应聘者在圆桌周围任意选择一个位置坐下；此后到达的每位应聘者都从前一应聘者出发，沿逆时针方向围圆桌走过m 人（前一应聘者算作走过的第1 人，同一人可能经过多次），并紧邻第m 人右侧就座；所有应聘者到齐后，从最后到达者出发，绕圆桌以顺时针方向为序进行面试。
这里假定应聘者到达的时刻互异，且相对的就坐位置确定后，左、右两人之间总能插入一把椅子。
试编写一个程序，确定面试顺序。
共2行。
第1行包含两个整数， n和m。
第2行包含n个整数，表示先后到达的n个应聘者的ID。
共1行。以空格分隔的n个整数，分别表示顺次进行面试的应聘者的ID。
5 3
6 7 8 9 10
10 6 8 9 7
1 ≤ n ≤ 10^3
1 ≤ m ≤ 2*n
输入的ID保证在int类型的范围内。
时间：1 sec
空间：256 MB
● 循环链表
● 因为找座位按逆时针方向，面试按顺时针发现，所以建议使用双向循环链表。
● 往链表中插入元素时，要小心地修改前驱指针和后继指针。
● 一次性new n个节点，比分n次每次new一个节点快一些，但本题的数据规模不至于一定要这么做。
公司有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”, …)会自动过滤空白字符。
Xuetangx:Data Structure and Algorithm of Tsinghua University 晋级全校公选课 PA1 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被分配给哪位教练。
3
1 2 3
1 2 3
1 2 3
3
C
5
1 2 3 4 5
1 3 5 4 2
5 4 3 2 1
4
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)。
2 123456 1 123456 4 12345
102 579 15
极其坑爹的一道题！要写高精度！坑人！
继续阅读
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”.
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.
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
继续动规：
继续阅读
8 300 207 155 300 299 170 158 65
6
简单动态规划：
继续阅读
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.
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.
n lines of capital letters, i.e., the evolutionary history of the bead sequence.
Specially, “-” stands for an empty sequence.
Input
ACCBA
5
1 B
0 A
2 B
4 C
0 A
Output
ABCCBA
AABCCBA
AABBCCBA
-
A
0 <= n <= 10^4
0 <= length of the initial sequence <= 10^4
Time: 2 sec
Memory: 256 MB
List
祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。
开发商最近准备为玩家写一个游戏过程的回放工具。他们已经在游戏内完成了过程记录的功能，而回放功能的实现则委托你来完成。
游戏过程的记录中，首先是轨道上初始的珠子序列，然后是玩家接下来所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。
第一行是一个由大写字母’A’~’Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示整个回放过程共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母Σ描述，以空格分隔。其中，Σ为新珠子的颜色。若插入前共有m颗珠子，则k ∈ [0, m]表示新珠子嵌入之后（尚未发生消除之前）在轨道上的位序。
输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。
见英文题面
0 ≤ n ≤ 10^4
0 ≤ 初始珠子数量 ≤ 10^4
时间：2 sec
内存：256 MB
列表
普通字符串模拟即可：
Figure 1 shows the structure of a station for train dispatching.
Figure 1
In this station, A is the entrance for each train and B is the exit. S is the transfer end. All single tracks are one-way, which means that the train can enter the station from A to S, and pull out from S to B. Note that the overtaking is not allowed. Because the compartments can reside in S, the order that they pull out at B may differ from that they enter at A. However, because of the limited capacity of S, no more that m compartments can reside at S simultaneously.
Assume that a train consist of n compartments labeled {1, 2, …, n}. A dispatcher wants to know whether these compartments can pull out at B in the order of {a1, a2, …, an} (a sequence). If can, in what order he should operate it?
Two lines:
1st line: two integers n and m;
2nd line: n integers separated by spaces, which is a permutation of {1, 2, …, n}. This is a compartment sequence that is to be judged regarding the feasibility.
If the sequence is feasible, output the sequence. “Push” means one compartment goes from A to S, while “pop” means one compartment goes from S to B. Each operation takes up one line.
If the sequence is infeasible, output a “no”.
Input
5 2
1 2 3 5 4
Output
push
pop
push
pop
push
pop
push
push
pop
pop
Input
5 5
3 1 2 4 5
Output
No
1 <= n <= 1,600,000
0 <= m <= 1,600,000
Time: 2 sec
Memory: 256 MB
某列车调度站的铁道联接结构如Figure 1所示。
其中，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}。
若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。
若不可行，则输出No。
见英文题面
1 ≤ n ≤ 1,600,000
0 ≤ m ≤ 1,600,000
时间：2 sec
空间：256 MB
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.
1st line: N
2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).
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 )
Input
3
2 2
4 3
5 1
Output
1
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
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]，不一定足够容纳本题的输出。