标签归档:高斯消元

[bzoj 3270] 博物馆

Description

有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行,他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间,并且满足可以从任何一间房间到任何一间别的房间。
两个人在博物馆里逛了一会儿后两人决定分头行动,去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事:他们并没有选好在哪儿碰面。等时间到六点,他们开始在博物馆里到处乱跑来找到对方(他们没法给对方打电话因为电话漫游费是很贵的)
不过,尽管他们到处乱跑,但他们还没有看完足够的艺术品,因此他们每个人采取如下的行动方法:每一分钟做决定往哪里走,有Pi 的概率在这分钟内不去其他地方(即呆在房间不动),有1-Pi 的概率他会在相邻的房间中等可能的选择一间并沿着走廊过去。这里的i指的是当期所在房间的序号。在古代建造是一件花费非常大的事,因此每条走廊会连接两个不同的房间,并且任意两个房间至多被一条走廊连接。
两个男孩同时行动。由于走廊很暗,两人不可能在走廊碰面,不过他们可以从走廊的两个方向通行。(此外,两个男孩可以同时地穿过同一条走廊却不会相遇)两个男孩按照上述方法行动直到他们碰面为止。更进一步地说,当两个人在某个时刻选择前往同一间房间,那么他们就会在那个房间相遇。
两个男孩现在分别处在a,b两个房间,求两人在每间房间相遇的概率。

继续阅读

[bzoj 1778][Usaco2010 Hol] 驱逐猪猡

Description

奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。因为这个臭气弹的随机的性质,奶牛们很困惑哪个城市最有可能被污染。给定一个猪猡文明的地图和臭气弹在每个小时内爆炸的概率。计算每个城市最终被污染的概率。如下例,假设这个猪猡文明有两个连接在一起的城市。臭气炸弹从城市1出发,每到一个城市,它都有1/2的概率爆炸。 1--2 可知下面这些路径是炸弹可能经过的路径(最后一个城市是臭气弹爆炸的城市): 1: 1 2: 1-2 3: 1-2-1 4: 1-2-1-2 5: 1-2-1-2-1 ... 要得到炸弹在城市1终止的概率,我们可以把上面的第1,第3,第5……条路径的概率加起来,(也就是上表奇数编号的路径)。上表中第k条路径的概率正好是(1/2)^k,也就是必须在前k-1个回合离开所在城市(每次的概率为1 - 1/2 = 1/2)并且留在最后一个城市(概率为1/2)。所以在城市1结束的概率可以表示为1/2 + (1/2)^3 + (1/2)^5 + ...。当我们无限地计算把这些项一个个加起来,我们最后会恰好得到2/3,也就是我们要求的概率,大约是0.666666667。这意味着最终停留在城市2的概率为1/3,大约为0.333333333。

继续阅读

[bzoj 1013][JSOI2008] 球形空间产生器

Description

  有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球
面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。

继续阅读