分类目录归档:未分类

蓄水池抽样

了解了一下蓄水池抽样。
它可以在O(n)的时间内对n个数据进行等概率的随机抽取k个样本,并且适用于n不断增长(就是n未知的情况下),或者n很大(不能放入内存的情况)。
算法的步骤就是:
假设要等概率的抽取样本数为k。那么首先把n个数列中的前k个元素放入到一个长度为k的数组中,称为蓄水池。然后对于之后的第k+1个元素到第n个元素中,第i个元素的时候,生成一个在[1,i]之间的随机数j,如果j小于k,就把蓄水池中的第j个元素换成第i个。
通过数学归纳法证明这样做可以让每个元素都有k/n的概率进入蓄水池。
首先,对于任意的 i,第 i 个元素进入蓄水池的概率为 k / i;而在蓄水池内每个元素被替换的概率为 1 / k; 因此在第 i 轮第j个元素被替换的概率为 (k / i ) * (1 / k) = 1 / i。
那么假设在第(i-1)轮,任意一个元素进入蓄水池的概率均为k/(i-1)。那么在第i轮其被替换概率为1/i,那么继续留在蓄水池的概率为k/(i-1)*(1-1/i)=k/i。得证。
写了个做实验的代码,的确可以说是非常随机了.

hdu 5517 Triple(二维树状数组)

Problem Description
Given the finite multi-set A of n pairs of integers, an another finite multi-set B of m triples of integers, we define the product of A and B as a multi-set

C=AB={a,c,da,bA, c,d,eB and b=e}

For each a,b,cC, its BETTER set is defined as

BETTERC(a,b,c)={u,v,wCu,v,wa,b,c, ua, vb, wc}

As a \textbf{multi-set} of triples, we define the TOP subset (as a multi-set as well) of C, denoted by TOP(C), as

TOP(C)={a,b,cCBETTERC(a,b,c)=}

You need to compute the size of TOP(C).

 

Input
The input contains several test cases. The first line of the input is a single integer t (1t10) which is the number of test case. Then t test cases follow.

Each test case contains three lines. The first line contains two integers n (1n105) and m (1m105) corresponding to the size of A and B respectively.
The second line contains 2×n nonnegative integers

a1,b1,a2,b2,,an,bn

which describe the multi-set A, where 1ai,bi105.
The third line contains 3×m nonnegative integers

c1,d1,e1,c2,d2,e3,,cm,dm,em

corresponding to the m triples of integers in B, where 1ci,di103 and 1ei105.

 

Output
For each test case, you should output the size of set TOP(C).

 

Sample Input
2 5 9 1 1 2 2 3 3 3 3 4 2 1 4 1 2 2 1 4 1 1 1 3 2 3 2 2 4 1 2 2 4 3 3 2 3 4 1 3 3 4 2 7 2 7 2 7 1 4 7 2 3 7 3 2 7 4 1 7

 

Sample Output
Case #1: 5 Case #2: 12
题意有太多公式就不想说了。。。
如果一个个枚举的话太大了,但是发现对于二元组来说,如果相同的b我们只用保留最大的a即可。那么暴力合并二元组和三元组即可,这个过程完成后需要去重并且计数,去重的细节较多(在这里狗带了两个小时)。。。然后剩下的排序a一维然后注意到c,d很小二维树状数组暴力统计即可。

 

Codeforces 848B. Rooter’s Song(乱搞)

Wherever the destination is, whoever we meet, let’s render this song together.

On a Cartesian coordinate plane lies a rectangular stage of size w × h, represented by a rectangle with corners (0, 0)(w, 0)(w, h) and (0, h). It can be seen that no collisions will happen before one enters the stage.

On the sides of the stage stand n dancers. The i-th of them falls into one of the following groups:

  • Vertical: stands at (xi, 0), moves in positive y direction (upwards);
  • Horizontal: stands at (0, yi), moves in positive x direction (rightwards).

According to choreography, the i-th dancer should stand still for the first ti milliseconds, and then start moving in the specified direction at 1unit per millisecond, until another border is reached. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.

When two dancers collide (i.e. are on the same point at some time when both of them are moving), they immediately exchange their moving directions and go on.

Dancers stop when a border of the stage is reached. Find out every dancer’s stopping position.

Input

The first line of input contains three space-separated positive integers nw and h (1 ≤ n ≤ 100 0002 ≤ w, h ≤ 100 000) — the number of dancers and the width and height of the stage, respectively.

The following n lines each describes a dancer: the i-th among them contains three space-separated integers gipi, and ti (1 ≤ gi ≤ 21 ≤ pi ≤ 99 9990 ≤ ti ≤ 100 000), describing a dancer’s group gi (gi = 1 — vertical, gi = 2 — horizontal), position, and waiting time. If gi = 1 then pi = xi; otherwise pi = yi. It’s guaranteed that 1 ≤ xi ≤ w - 1 and 1 ≤ yi ≤ h - 1. It is guaranteed that no two dancers have the same group, position and waiting time at the same time.

Output

Output n lines, the i-th of which contains two space-separated integers (xi, yi) — the stopping position of the i-th dancer in the input.

Examples
input

output

input

output

Note

The first example corresponds to the initial setup in the legend, and the tracks of dancers are marked with different colours in the following figure.

In the second example, no dancers collide.

题意:给出n个点要么沿着y轴正方向或者x轴正方向,这个过程会发生碰撞,求每个点最后的位置。

非常有趣的题目,vp的时候想了半天,后来被旁边的chf提醒了才会做。。。

假设两个点在T这个时刻在(x,y)这个点发生了碰撞,这两个点自然是(x,0)和(0,y)。假设两个点的出发时刻为t1和t2。那么自然t1+y=T=t2+x。两边减去x+y得到t1-x=t2-y。那么也就是说只有满足t-p均为一个值的点集才可以发生碰撞,而别的点根本没有关系。。。

然后我们可以发现这么个规律:

图随便画的。。。

所以我们按照这个规律把点集内的点排序然后依次对应即可。