希望round3之前能填满这个坑
update:
5.11 上面那句话当我没说
5.23 明天就要去常州啦
5.27 目测这个坑要变成无底洞了...
6.2 弃坑弃坑
完成数：36
刷题计划 第二弹
2015年3月19日 20:31
这次不屯题了...想想既然离省选不远了还是做点正常的题比较好。
update:
5.1 总算是在ctsc&&apio之前完结了...不知道第三轮省选之前能不能再填一个坑...
完成数：50
bzoj3162 独钓寒江雪 题解+吐槽
2015年3月07日 14:07
题意：
无根树独立集同构计数。
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...
bzoj屯题计划
2015年2月28日 15:13
update:
2.28 正式开坑！
跪球bzoj不要把后面的题权限了，我还等着大号屯50题呢...
3.6 3894被权限了，又得多屯一题，不爽...
3.7 完成了一半啦
3.11 bzoj上不去了，坑
3.16 屯了这么多天心力交瘁...感觉自己只会刷水题了...还是赶紧结了这个坑好了...
3.17 完结喽
完成度：50 / 50
POI18~20部分题(tu)解(cao)
2015年2月25日 23:03
今年年初开的新坑，填到现在也没填完→_→
POI题的质量还是相当可以的，题解虽然是波兰文的丢到谷歌翻译里翻成英文还是能看的。
到现在每一届还有好几道神题不会捉真是没救了
反正也没人会看，随便写写好了。
37/52 完成度：71.2%
bzoj2035:[2009国家集训队]数据读取问题 意识流题解
2015年2月25日 20:37
之所以写这题题解是因为它有种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我也是醉了...
