标签归档:uva

uvalive 6959 Judging Troubles(双hash模板题)

题目链接

题意:给出2*n个字符串,前n个为一组,后n个为一组。问在两组中都出现的字符串有几个。

map瞎搞搞也可以做,但是为了学一下字符串的双hash,所以我写了hash。

直接把每个字符串hash一下,map记一下数。

 

uva 11922 Permutation Transformer(splay区间翻转,区间合并,区间删除)

题目链接

splay裸题,需要的操作区间翻转,区间合并,区间删除。

题意大概就是给出一个区间翻转后把它移到这个序列的最后。区间翻转之前已经练习过了,第一次写区间删除和区间合并。我是这么做的,先把那个需要翻转的区间找到,然后这个区间就是我们要删除的,所以直接把此时根的右子树的根的左子树直接置为0就可以了。然后就是需要合并了。我们可以先找到剩下来的树中的倒数第二个元素并提根。因为我加了哨兵,所以倒数第一个元素必然是那个右边的哨兵。然后我们把它提到此时的根的右儿子。然后再把删除的区间加到他的左儿子就好了。注意要及时pushup,还有一点需要注意的是print操作也要及时下传rev标记。

 

hdu 3726 & uvalive 5031 Graph and Queries(启发式合并+treap+时光倒流+并查集)

Problem Description
You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:
1)  Deletes an edge from the graph.
The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.
2)  Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself).
The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.
3)  Changes the weight of a vertex.
The format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-106, 106].

The operations end with one single character, E, which indicates that the current case has ended.
For simplicity, you only need to output one real number – the average answer of all queries.

 

Input
There are multiple test cases in the input file. Each case starts with two integers N and M (1 <= N <= 2 * 104, 0 <= M <= 6 * 104), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (-106 <= weight[i] <= 106). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 * 105], and there will be no more than 2 * 105 operations that change the values of the vertexes [C X V].

There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program.

 

Output
For each test case, output one real number – the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.

 

Sample Input
3 3
10
20
30
1 2
2 3
1 3
D 3
Q 1 2
Q 2 1
D 2
Q 3 2
C 1 50
Q 1 1
E
3 3
10
20
20
1 2
2 3
1 3
Q 1 1
Q 1 2
Q 1 3
E
0 0

 

Sample Output
Case 1: 25.000000
Case 2: 16.666667

Hint

For the first sample: D 3 — deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3)) Q 1 2 — finds the vertex with the second largest value among all vertexes connected with 1. The answer is 20. Q 2 1 — finds the vertex with the largest value among all vertexes connected with 2. The answer is 30. D 2 — deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2)) Q 3 2 — finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined). C 1 50 — changes the value of vertex 1 to 50. Q 1 1 — finds the vertex with the largest value among all vertex connected with 1. The answer is 50. E — This is the end of the current test case. Four queries have been evaluated, and the answer to this case is (20 + 30 + 0 + 50) / 4 = 25.000. For the second sample, caution about the vertex with same weight: Q 1 1 – the answer is 20 Q 1 2 – the answer is 20 Q 1 3 – the answer is 10

题意:见大白书。
思路:这是白书的一道例题。根据操作中有询问某个连通块中第k大这样的操作,所以就可以用一个treap的数组维护。但是蒻不会treap的分裂,于是就按照白书的思路离线处理时光倒流。这样的话,连通块可以通过并查集维护。然后合并两棵treap的话就启发式合并,之前貌似把treap的合并写错了,一直WA和RE的循环。