12
16
2016
0

有向图APSP

听说读论文的最好方法是把它翻译一遍。。?(然而我不会严格地翻译。。只会大概地复述一遍。。)这次的论文是《All Pairs Shortest Paths in weighted directed graphs - exact and almost exact algorithms》(Zwick'98)。论文的主题是有向带权图的APSP(All Pair Shortest Path,两两最短路)问题。

Category: 未分类 | Tags: 黑科技
12
6
2016
0

无权图增量最短路问题

本文所有信息来自论文Incremental Algorithms for Minimal Length Paths。

今天我们要介绍一个数据结构,它解决如下的问题:有一张有向无权图,要求在线地支持三种操作:

  • 加入一条边
  • 求两点之间最短路长度
  • 求两点之间的最短路(整条路径)

这个数据结构的复杂度如下:加入所有$O(n^2)$条边,总复杂度是$O(n^3\log n)$;求最短路长度是$O(1)$的,而且是查表(就是说,没有任何加减乘除运算);求最短路是$O(L)$的,其中$L$是最短路长度。空间复杂度是$O(n^2)$的。

这是个很优秀的复杂度。。因为Floyd也就$O(n^3)$。对于这种动态问题,如果询问就是查表的话总的更新复杂度至少是$O(n^3)$(论文里有讲)。论文一开头就说他们离best possible bound只差了一个$\log n$。

然后,我猜这个算法对带权图也是对的,但是复杂度(具体地说,对后面的$\sum |B_{ij}|$的分析)就不对了。

至于会不会出成OI题?我又不是cc镇站之宝我拿这东西出题干嘛

Category: 未分类 | Tags: 黑科技
11
30
2016
0

uyhip2016 November

题目

听说,水题和手速狗更配哦。

题意:求$$\sum_{k=0}^n\binom{n}{k}\frac{(-1)^k}{k+j}$$

Category: 未分类 | Tags: uyhip
11
1
2016
0

uyhip2016 October

题目

今天早上起来看了答案。。就更一发了。。我非常喜欢的一个题。。可惜自己最终没有征服它,想都没有想到点子上

这种题用某位大佬的话说就是靠缘分。。

是否存在一个凸多边形$C$和它的一个划分$P$,使得$P$的每个部分都是凹四边形,且$P$只有有限个部分?

Category: 未分类 | Tags: uyhip
9
26
2016
1

听说所有symmetric Pascal matrix的行列式都是1

故事背景是这样的。。r_64在进入五道口抖m体校之后,成了脑浆炸裂男孩,发现什么题都做不出了,急需一发数学题来补补脑。。

然后听说symmetric Pascal matrix的行列式都是1。。觉得这个东西的证明好像是个水题。。然后就开始刚

没错这是个水题。。结果脑浆炸裂男孩硬是花了将近一周才证出来。。

Category: 未分类 | Tags: 数学
9
11
2016
0

军训时在干什么

鸣谢茶园的ztz,akf,wwx和工业工程系的cm

upd 9.26:更了第3题第1,2问(我tm居然会填坑),但是总感觉不太对

Category: 未分类 | Tags: 数学
9
4
2016
0

IBM Ponder this 2016 August

IBM最近的题水得不正常→_→

这个月的题目翻译就是,有$10$个袋子,里面各有$N$个硬币。有的袋子里只有10g的真币,有的袋子里只有9g的假币。允许你只用一个准确的秤称量一次,要求确定哪些袋子里的是假币。$N\ge 1024$。

这太水辣!第$i$个袋子取出$2^{i-1}$个,称总重量,二进制分解就好。

现在顶多三个袋子的假币,且$N=174$,求一种称量方法。解决$N$更小的问题就有bonus。

注:这篇博客里没有答案。。想要答案的自己跑程序去。

Category: 未分类 | Tags: ibm
8
19
2016
0

姚班入学考试(不全)

姚班的考试数学都是英文(但可以用中文作答),物理都是中文。。请备考的学弟学妹们注意

这里凭借记忆写。。如果题面或我给的答案有错请告知。以及部分题目或其解答我不清楚。。如果会的请联系我。

Category: 未分类 | Tags:
8
5
2016
0

codechef AUG16

这几天在外面旅游。。看了一下题目感觉好难。。难题都不会做,简单题不都会做,而且还没时间打

玫瑰彩虹大爷又出题了。。看到题目就感受到了深深的恶意。。还有一个题叫GOODPROB是什么鬼

Category: 未分类 | Tags: codechef
8
1
2016
0

Uyhip2016 July

这么难的题目窝根本不会做。。part1的思路就很逆天了。。这里做个搬运工

题目

Category: 未分类 | Tags: uyhip

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com