bzoj3162 独钓寒江雪 题解+吐槽

题意:

无根树独立集同构计数。

vfk出的神题真是不能更神。

题解:

首先如果不考虑同构,那么是个经典的树形dp。

[tex]f[i][0][/tex]和[tex]f[i][1][/tex]分别表示i号点选或不选的独立集数量,然后转移就行了。

由于存在同构,我们先选取树的重心为根。如果有两个重心,新建一个根连向重心,最后根节点特判。

考虑[tex]n[/tex]个位置染[tex]m[/tex]种颜色不同构的方案数,我们从保证颜色递增的方面来考虑答案很显然是[tex]C_{n+m-1}^n[/tex]。

于是接下来就是要球出每个节点不同构的子树有哪些。

这个就是经典hash了。

求出子树的hash值,排序,用某种函数合在一起就行了。

吐槽:

废话不说直接上图。

第一轮省选那题给我的阴影我就不说什么了。

这一题我写的是每次乘一个质数然后加上hash值。

然后怎么改都WA。

然后我按照题解改成了从小到大排序,先乘质数,然后异或,然后加。

然后还是WA。

然后我按照题解把质数换成了233333333。

然后尼玛就A了...

唉命中注定被卡hash...

 

codeforces补全计划

虽然最近没怎么打比赛但题目还是要补全的

完成数:15

寒(tui)假(fei)大(de)汇(zong)总(jie)

今天都开学了...我还沉浸在寒假刷(tui)题(fei)的快感中真是没救了...还是来总结一下好了...省选round1考得实在是太逗比,本来不想单独写游记的,现在丢到这里面来好了...

 

bzoj屯题计划

update:

2.28 正式开坑!

跪球bzoj不要把后面的题权限了,我还等着大号屯50题呢...

3.6 3894被权限了,又得多屯一题,不爽...

3.7 完成了一半啦

3.11 bzoj上不去了,坑

3.16 屯了这么多天心力交瘁...感觉自己只会刷水题了...还是赶紧结了这个坑好了...

3.17 完结喽

完成度:50 / 50

 

没有计划就会颓废

马上都开学了...离第二轮省选就剩一个多月了...我还是这么蒻...再这么下去不行了...

 

1.bzoj屯50题。

2.去年第二轮省选的题。貌似好久以前就说要做的...

3.每一场cf div1的ABC...即使当时没打后来得补完...

4.USACO和uoj每一场比赛不能漏...

5.POI18~20没做的可做题...

6.打算要学的:

莫比乌斯反演(就当是会了好了)

树分治

spaly(大雾>_<)

图论连通性系列:无向图割点、桥、双连通分量、有向图割点、桥、强连通分量(现推还是能搞出来的?)

2-SAT

FFT(打算理性愉悦)

计算几何:最小圆覆盖(会写不会证,不管了)、凸包、simpson积分

树上莫队

斯坦纳树(虽然搞懂了但还是不明白一些细节)

后缀自动机

(发现每一个都是大坑节奏...而且大部分省选没用...)

7.继续膜拜神犇shanquan2,补(xue)习(xi)数学 (什么鬼)

暂时就想到这些QAQ

感觉亚历山大啊QAQ

 

 

 

POI18~20部分题(tu)解(cao)

今年年初开的新坑,填到现在也没填完→_→

POI题的质量还是相当可以的,题解虽然是波兰文的丢到谷歌翻译里翻成英文还是能看的。

到现在每一届还有好几道神题不会捉真是没救了

反正也没人会看,随便写写好了。

 

37/52  完成度:71.2%

 

bzoj2035:[2009国家集训队]数据读取问题 意识流题解

之所以写这题题解是因为它有种POI鬼畜图论题的感觉...

 

题意

题目能一遍看懂的举下手...

先不管题目是干啥的你TM扯一堆平行宇宙,薛定谔的猫是在干啥啊...

翻译:

有一棵带点权的树,对每条从根到叶子节点的链,进行以下操作:

1.花费1的代价进入下一个节点。

2.若当前节点的值为[tex]a_i[/tex],花费[tex]d[/tex]的代价向前走[tex]{a_i}+d[/tex]或[tex]{a_i}-d[/tex]的节点,必须保证后面有这么多节点且不能后退。

3.若还有节点,重复1,否则结束。

最小化代价。

题解

既然是要球每条链,那么先来分析一条链的情况。

首先在结尾添加一个[tex]n+1[/tex]号节点(其实加不加无所谓)

然后[tex]O({n^2})[/tex]的动态规划很好想。

然后把i提取出来发现可以用线段树优化到[tex]O(n \log n)[/tex]。

当然其实有线性做法。我们假设直接走[tex]a_i[/tex]个单位然后再调整。

于是构造有向图,i向[tex]i+{a_i}+1[/tex]连权值为1的边,同时向[tex]i-1[/tex]和[tex]i+1[/tex]页连一条权值为1的边。

然后我们发现直接半斧神bfs搞出最短路就行了...

直接把前面bfs的做法搬过来会发现不行是因为连的边数可能达到平方级别。所以要考虑优化。

我们球出树的bfs序,容易发现每个节点连出去的节点一定是连续的一段。

于是可以并查集维护,bfs时每次找一个未访问过的节点就行了。

时间复杂度[tex]O(n \alpha(n))[/tex]

 

非常搞笑的是清澄上面时限开的是1s,就连标程都跑不过去,居然有人能AC我也是醉了...

 

 

Hello,world!

This is a test.