A(zoj 3596)
bfs,记忆搜都可以, 按余数来记录状态.
B(zoj 3599)
博弈,跳过
C(zoj 3592)
简单dp,题意不好懂
D(zoj 3602)
子树哈希, 对根的左右儿子的哈希值make_pair()一下映射成根的哈希值就行了.
E(zoj 3604)
求n个点构成s颗树的方案数.
当s=1时可以利用 Prüfer编码 来理解.
Prüfer编码是对一棵树进行如下操作得到的序列:
对树的每个节点进行编号1~n, 选择编号最小的叶子将它删去并将它的父亲加入序列;
重复上一步直到无法操作,
Prüfer编码
首先要说明的是,Prüfer编码能唯一地确定一棵树:
先考虑当前序列seq中的n-1个元素,在1~n中没有的肯定是被删掉的叶子,而其中最小的肯定是第一次被删去的,我们找到它把它连在seq[1]上,
接下来递归地考虑剩下的n-2个元素... 整个过程中连边的操作都是唯一确定的,因此最后我们得到了唯一的一颗树.
接下来我们会发现,序列的前n-2个元素可以是1～n的任意值,而最后一个元素在得到前面n-2个元素后就被确定了,why？
因为在填完n-2个元素后, n个点的树已经连了n-2条边,所以当前的图中是2棵树组成的森林,第n-1条边只能连在两个根之间.
于是当s=1时公式为n.
当s为其它值时,同样可以按上面说的道理, 连完第n-s-1条边时,途中有s+1棵树,所以第n-s条边一定要连在s个根中的某一个上,有s种选择.
于是公式为 sn.
顺便提一下,Prüfer编码既然能唯一确定一棵树,那么它也能判断两颗树是否同构和上一题的子树哈希可以扯上关系...
F(zoj 3606)
第一步分析出所有可能的w是所有的 (t-t) , 于是可以得到n^2的朴素方法,枚举w.
第二步,当w变大的时候,原来招待的顾客依然会被招待,于是只要把新加入的顾客算入统计结果中即可.
可以考虑用单点更新的线段树, 另外一个问题是,新加入顾客后,老顾客买的面包数变了,所以要用3棵线段树把所有情况存下来.
G(zoj 3608)
计算几何,跳过
H(zoj 2318)
1. 两个向量a,b的夹角余弦可以用 a . b / |a|*|b| 得到, 利用余弦定理证明
2. spfa判断负环: 某点的松弛次数>=n.
I(zoj 2320)
经典模型.
第一步,将问题转化为 t * m 的 %2 异或方程组.
接下来,可以通过求自由元个数统计出方案数.
不是很理解模线性方程组,甚至觉得很不科学,两个不同底数的指数,居然可以放一起运算,也许这些数在方程组里面,只有它的数值意义吧.
J(zoj 2337)
预处理出g(stat,c)边后就是普通的自动机模型,用dp统计即可.
注意到g(stat,c)边的特殊性,当通过g走到下一个状态后,接下来读取到的字符还是c,所以预处理时要一直延g(stat,c)直到无处可走或者判断出有环.
zoj极不厚道地让java超时了。。。
K(zoj 2338)
汉诺塔拓展问题,dp方程很好得到,然后逆向输出即可.
题目数据很不厚道,要把数组开成unsigned long long 才行。。。。
L(zoj 2340)
物理公式推导题,精度也十分不厚道,用区间用高度判断是否撞墙ac,用速度判断就会wa.
M(zoj 2341)
吐槽【卧槽。。。 完全不知所云的一道题. 没人做,是有道理的。。。。！】 ,跳过！
N(zoj 2342)
按题解说法可以转换成带权匹配的对偶问题,暂时跳过
O(zoj 2344)
据说是波利亚计数,暂时跳过
【总结】
弱项 博弈 , 高斯消元 , 计算几何,图论,公式推导神马的。。。。