题面

大致题意：构造一个8*8的矩阵，所有数在模3意义下。然后可以执行若干次操作，每次操作是行+1或列+1。要求你构造的矩阵无论怎么执行操作，里面的0的个数不超过36。

对了，IBM这个页面在大概三月底的时候改版了，真是可爱啊

垃圾F，毁我青春

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

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

比赛刚放出来的时候有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$的子域。

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

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

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

题目

有一个议会里面有$n$个人，有一些委员会，要求：

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

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

听说读论文的最好方法是把它翻译一遍。。?(然而我不会严格地翻译。。只会大概地复述一遍。。)这次的论文是《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镇站之宝我拿这东西出题干嘛