SGU 481..Hero of our time

正经的写一篇题解吧。这个题目求的是有标号的n个点n条边的联通图的数量。n  <=5000

往往题目异常简洁的题目会比较难>_<。。。

分析1:

这个图必然是一个环加上一个外向树的形式。

思路1 or 2:

那么接下来就有两个思路了,要么固定环,想办法算出答案,要么选一个点为根,在这个有根树中考虑这个环。

思路1:

尝试固定环,设环大小为k,那么在这个图中去掉这些环上的边,得出的就是n个点,k棵树的森林。

令F(n,k)表示n个点,k棵树的森林的个数,那么环大小为k的情况答案是:

F(n,k)*k!/2。。这不难理解。。因为森林出来之后森林的那些根的园排列有k!/2种。

考虑如何求F(n,k)。

思路 1.1 or 1.2:

要么将F(n,k)看成一个二维递推式,推导出结果。 要么尝试使用组合数学的方法直接计算出F(n,k)。

思路 1.1:

考虑一棵树,为了在递推中不影响树的大致的整体结构(最大相似性决定递推的成功>_<)。我们可以

尝试取走一个叶子来将树的大小-1

那么令G(n,t)表示n个节点,t个叶子的树的个数。

考虑两种规划的方式,正向和逆向,逆向规划(即在算G(n,t)时用以前的结果)的关键在于取走一个叶子之后,不能知道叶子的父亲是否

会变成叶子,而叶子数是很重要的,所以不可行。正向规划相反则是可行的(即用G(n,t)更新G(n+1,..)的)结果。

考虑当前是G(n,t),如果加入一个叶子,那么可以连到叶子节点上,也可以连到非叶子节点上。

前者叶子数不变,后者叶子数+1。就可以较方便的计算了。

但是每个G(n,t)在计算的时候,它的每个叶子都会把它的结果计算一遍,所以最后要除以t。

但是这是n^2的,而且还涉及高精度的问题。所以不是一个好算法。

思路 1.2:

在推导标号树个数的时候有一种方法叫双重计数,同样可以解决计算F(n,k)的问题。

并能给出一个直接的公式

没时间就不展开了。。。可以自己去看wiki

复杂度是O(N)。

http://en.wikipedia.org/wiki/Double_counting

 

思路2:

令1为根,那么我们可以找到环中最接近1的点(注意,满足唯一性!计数问题必不可少的)

令其为x,考虑x在环上的两个相邻点l和r。

令l<r。。去掉边x->r。就变成了一棵树,还是以1为根可以发现l是r的祖先。

可以发现在“1为根,x在环上的相邻点是l和r且l<r的结果” = “1为根,l<r且l是r的祖先的树的个数”

那么后者的结果乘以每句l和r造成的C(n-1,2)就是答案。

如何求后者呢?

有一种prufer Code的推广形式能轻易的给出答案。。由于非常繁琐就不说了。。

http://www.cs.elte.hu/egres/tr/egres-05-16.pdf

 

。。。我发现写这么多还不如直接贴5、6个网址让大家自己去看。。。。

我2。。。。

CF 56

。。。这次的题目似乎特别水。。但状态非常差。。做完ABC都花了40多分钟。。

然后又被D搞了半天。。最后发现E虽然很可捉。。但是我脑子进水还是想错了一个关键的地方。。结果WA两次。。。。

D居然直接生成所有勾股数就行了。。真TMD狠。。。

E的话首先推公式。。然后发现只要算第一次之后最大和最小的两个就行了。。我以为能直接计算(。。我是脑残吧。。是脑残吧。。。)。。最小的那个显然就是a0,最大那个要用矩阵乘法搞一下。。。

啊啊啊啊。。这场比赛无人AK啊。。。我E搞对了我就Rank1啊啊啊啊啊啊啊啊啊啊。。。

倒霉死了>_<。。。。

不对。。虽然touristC挂了。。但是我就算E对了也没他高。。。。

。。。差距啊。。。

连续两次rank9。。。怎么这么囧。。。。

ZOJ月赛 nimendongde第二场。。。

酱油记。。

这次月赛似乎很囧。。。。一开始我们很顺利。。

我刷掉了几道水题。。然后我注意到H。。觉得这个模型我在Ural上见过。。

就搞掉了。。。

然后又看了J。。觉得这个模型在TC和SC省选上都见过。。就又去写了。。

不过WA。。。想了半天才明白原来是有个很邪恶的情况。。就是可以在中间挖。。

然后也搞掉了。。。

然后去做A。。一看到A就觉得应该是双向搜索。。但是我太SB了。。搞了半天还是TLE。。。

酱油完毕。。。。

除草。。。。。Sgu一点水题题解。。。

只为除草

SGU514:看到题目之后用调整法推一点性质,就可以用集合dp乱搞了。。

SGU508:很水的概率题吧。。直接算一下就可以了吧。。。。

SGU504:二分一下就可以乱搞了。。

SGU503:题目很长很凌乱。。但仔细的阅读之后还是可以用集合dp解决的。。。

SGU513:通过观察发现3个点的某种性质。。然后就可以做了。。。

。。。。。

这还叫题解么。。。。

COCI 2010/2011 #5

这次比赛难得那么好的一个AK的机会。。然后我SB掉了。。。

前2题无视。。第三题从小到大一个个枚举过去。。。N^2就可以过。。我写成了N^2LogN。。然后最大点居然只要0.04s。。。这。。。

第四题一个简单的dp。。状态分3类就可以了。。

第五题可以线性。。具体就是直接做开始是很困难的。。可以考虑从中间往两边扩展。。那么搞出所有极大区间。。

然后用一个栈扫描一遍就能得出答案。。。

第六题其实很水啊。。把版按照棋盘黑白染色。。可以发现两个颜色是互不影响的。。就转变成了两个经典的矩阵染色问题。。

这个染色问题显然可以2d线段树。。不过我觉得这个常数过大还是用线段树扫描一下吧。。。。

然后处理一下Load和Save。。可以发现其实Load和Save只是意味着有些操作是没用的。。

删掉就行了。。。

然后我处理错了。。。只有13分>_<。。。。。。

比赛结束了按洲妹的改了一下就AC了。。。。。。擦。。。

经验+总结:

以后参加比赛都要写写总结之类的。。。这样才能吸取教训嘛>_<。。。首先是第3题。。我犹豫了半天要不要改N^2LogN的算法。。因为我觉得不怎么可能有数据能卡这个。。。这浪费了不少时间。。非常的不应该啊。。应该在写题目的时候就估算好复杂度。。直接写N^2的多好>_<。。。还有第5题狂对排了一下。。感觉上就能在比赛的时候放心不少。。
最失败的是最后一题。。这说明细节是非常重要的。。一些重要的细节问题一定要多加深思啊>_<。。。。
然后直接在脑子里自以为是的想一下就写程序是很不行的>_<。。应该在纸上多画一画之类的。。。

还有感觉自己代码能力好像还过的去。。但是平常写程序的时候变量名称有时候都要考虑一会儿>_<。。而比赛的时候无疑是很浪费时间的。。。但是混乱的名称又很那啥。。。应该组织一下自己的各种变量名称了>_<。。。