face艹 megcup 2017

垃圾F,毁我青春

继续阅读

codechef MARCH17

这场TUPLES2的出题人脑子进翔了。。鈤

阅读全文

IBM Ponder this 2017 February

题面:给一个函数,求多少长度为$42$的字符串输入进去之后返回值不是$0$。

继续阅读

codechef FEB17

比赛刚放出来的时候有7个题,四天以后就只有5个题了。。怎么感觉cc很缺题的样子

继续阅读

抽代试卷上的一个题

设$E$为$F$的扩域,$K,L$为中间域,$K/F$为代数扩域,

$$S=\{\sum_{i=1}^na_ib_i:n<\infty,a_i\in K,b_i\in L\}$$

求证:$S$是$E$的子域。

继续阅读

codechef JAN17

在微积分和抽代的紧逼之下打开了这个熟悉的网站作死

只有4个题按时出炉了。。垃圾比赛

ps.最终TUPLES没有调出来。。嘴巴了一下。。还有一个傻逼题没做。。。

继续阅读

Uyhip2016 December

题目

有一个议会里面有$n$个人,有一些委员会,要求:

  • 对任意两个委员会,有恰好一个人同时在这两个委员会中。
  • 任何一个人在至少两个委员会中
  • 任何一个委员会里至少有两个人

求最多有多少个委员会。将答案表示为$n$的函数。

继续阅读

有向图APSP

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

继续阅读

无权图增量最短路问题

本文所有信息来自论文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镇站之宝我拿这东西出题干嘛

继续阅读

uyhip2016 November

题目

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

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

继续阅读