标签归档:数学

[bzoj 3270] 博物馆

Description

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

继续阅读

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

Description

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

继续阅读

[bzoj 2659][Beijingwc2012] 算不出的算式

Description

算不出的算式
背景:
曾经有一个老掉牙的游戏放在我面前,我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此,如果上天给我一个再玩一次的机会,我一定要,通关!
题目描述:
如果你真的很想玩这个游戏,那么就先看看我的题目吧,搞不定这些的话是没办法通关的哟。第一关其实很简单,只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式,估计是要你利用它算出密码来开门吧(果然是老掉牙的情节)。
传说中这个式子中的p和q是两个奇质数,等号右边算出来应该就是密码了吧,你是真的算不出来么?

继续阅读

CodeForces Round #350 Solution

这场比赛比较水,但是细节比较多,而我没考虑T_T

一个是先入为主坑了我的B题,我没有计算时间复杂度而导致采用了较繁而且容易挂的算法,wa了4发

C题是因为我没能考虑到特殊情况而苦于wa on 14,7 times

如果没有这两个错误说不定能大涨分= =

这些错误都是值得我思考以及改正的,好了,切入正题

继续阅读

CQU Qualification Solution

QQ图片20160501171336单挑失败,不过题目还是要补的,感谢@wking大爷带我补

UPD1: 还有3题没补完明天早上补qwq

A.取石子游戏

Description

1堆石子有n个,两人轮流取.先取者第1次可以取任意多个,但不能全部取完.以后每次取的石子数不能超过上次取子数的2倍。取完者胜.先取者负输出"Second win".先取者胜输出"First win".

继续阅读

CodeForces Round#349 Div.2

A.Pouring Rain

设第x秒会喝完,每秒会增加e\;cm,减少\frac{v}{r^{2}\pi}\;cm,原来相差h\;cm,这就是个追击问题,容易得到方程

(\frac{v}{r^{2}\pi}-e)\times\;x=h

解之即可

B.Coat of Anticubism

考虑题目给出的性质:“初始数据保证一定不能组成凸多边形”

结论:先对原数组排序,然后答案为

a[n]-\sum_{i=1}^{n-1}a[i]\;+1

继续阅读