很难过吧。。。考得完爆了。。。

。。。。。。其实也没什么可以说的。。。都是蒟蒻的借口罢了。。。

。。。自己果然还只是半吊子水平呢。。。。

。。。祝大家都能进省队。。。其实只要不要有遗憾就好了呢。。。

虽然我很遗憾或许不能走下去了。。。。。

886

。。。明天就要省选了呢>_<。。。。。。。

Bless all

。。。。-25。。。。

我还能说什么?。。。。。。

。。。首先250做不出来。。。

。。。然后去写500。。。我想的是搜索然后剪枝。。但是实现脑残了。。。

没办法了去看1000。。。想想可以枚举9，8，4，6，不过脑子又残了。。觉得不可能是枚举就行了吧（算都没算）。。就想dp。。就挂了。。。

好吧，总结一下。。。

首先250的思路也不是非常难。。但是我思维局限很严重。。。没有跳出坑的能力啊T_T。。以后都做做这类考思维的题目。。。

500的话。。。想好再写也不是很难吧。。但我250卡了半天那啥起来了。。就开始直接写了。。。还是没有做到完全冷静的程度啊。。。。。

1000。。。。。。我可以去死么。。。。以后严谨点啊T_T。。。。

！！！！！！！！！！！！！！！！！！！

操！！！！！！！！！！

我250pt的题目看错了！！！！！！！！！

。。。。这次的比赛。。。已经成hack cup了。。。

A题各种那啥。。。我写完B题之后撇了一眼standing。。发现有人cha了很多A题。。

于是仔细一看A题。。发现我错了。。

然后。。。

我直接lock掉A题。。跑去狂Cha别人。。。

最后Cha了21个吧。。。。虽然我A和D全挂了。。最后还是没有太悲剧。。。

B就是一个直接裸推过去。。。

C的话就是二分然后搞。。。。。。。

D的话我想了半天以为贪心是对的。。。结果显然是错的。。同时正解居然是爆搞。。。

因为可行的状态数非常少。。。好阴险的题目啊。。。我了个去。。。

P.S。。其实我觉得如果我静下来心来看应该还是能明白D的奥妙的。。可当时我只顾着Cha A心思完全不在点上。。。

。。。还是比赛的心态不够好啊。。。

教训：裸贪心至少也写个对拍拍一拍啊。。。。。

正经的写一篇题解吧。这个题目求的是有标号的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。。。。

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

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

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

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

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

倒霉死了>_<。。。。

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

。。。差距啊。。。

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

http://acm.sgu.ru/problem.php?contest=0&problem=501

这个题目。。。还能怎么做>_<。。。显然是可以dp的。。就是写起来比较麻烦。。。。

使劲就写出来了。。。。

P.S。。终于A了一道只有10几个人AC的题目啦。。真高欣‍

酱油记。。

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

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

就搞掉了。。。

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

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

然后也搞掉了。。。

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

酱油完毕。。。。

只为除草

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

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

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

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

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

。。。。。

这还叫题解么。。。。

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

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

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

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

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

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

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

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

删掉就行了。。。

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

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

经验+总结：

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

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