马上初赛了,假装准备一下.
主定理
假设有递推关系式 $T(n)=aT(\frac n b)+f(n)$ .
三种情况分别对应了 $f(n)=O(n^d)$ 的 $d$ 较小,适中,与较大的情况.
Case 1
若 $f(n)=O(n^{\log_b a-\epsilon}),\epsilon >0$ ,则 $T(n)=\Theta(n^{\log_b a})$ .
此时复杂度由 $a,b$ 决定.
Case 2
若 $f(n)=\Theta(n^{\log_b a}\log^k n)$ ,则 $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$ .
此时两者均衡,复杂度在共同决定的基础上还要乘上一个 $\log n$ .
Case 3
若 $f(n)=\Omega(n^{\log_b a+\epsilon}),\epsilon>0$ ,对于某个常数 $c<1$ 和所有充分大的 $n$ 有 $af(\frac n b)<cf(n)$ ,则 $T(n)=\Theta(f(n))$ .
此时复杂度由 $f(n)$ 决定.
例一
若某算法的计算时间表示为递推关系式 $T(n)=2T(\frac n 2)+n\log n,T(1)=1$ ,求解该算法的时间复杂度.
观察发现是 Case 2 ,其中 $a=b=2,k=1$ .
于是时间复杂度为 $T(n)=\Theta(n\log^2 n)$ .
例二
若某算法的计算时间表示为递推关系式 $T(n)=2T(\frac n 4)+\sqrt n,T(1)=1$ ,求解该算法的时间复杂度.
观察发现是 Case 2 ,其中 $a=2,b=4,k=0$ .
于是时间复杂度为 $T(n)=\Theta(\sqrt n\log n)$ .
例三
若某算法的计算时间表示为递推关系式 $T(n)=9T(\frac n 3)+n,T(1)=1$ ,求解该算法的时间复杂度.
观察发现是 Case 1 ,其中 $a=9,b=3$ .
于是时间复杂度为 $T(n)=\Theta(n^2)$ .
例四
若某算法的计算时间表示为递推关系式 $T(n)=T(\frac n 2)+n,T(1)=1$ ,求解该算法的时间复杂度.
观察发现是 Case 3 ,其中 $a=1,b=2$ ,常数 $c$ 可取 $(\frac 1 2,1)$ 中的任意实数.
于是时间复杂度为 $T(n)=\Theta(n)$ .
杂题整理
NOIP2018 提高组初赛 T17
求出当 $a, b$ 都取 $[0, 31]$ 中的整数时,方程 a*b = (a or b) * (a and b) 一共有多少组解.
首先可以注意到 (a or b) + (a and b) = a + b .
证明方式是把每个二进制位分开考虑.
若两个都是 $1$ ,贡献为 $2$ ,只有一个 $1$ ,贡献为 $1$ ,都是 $0$ ,贡献为 $0$ ,不难发现等式两边都满足以上性质.
记 x = (a or b),y = (a and b) ,则有 $a+b=x+y,ab=xy$ .
而 $x\ge y$ ,所以只可能是 $x=\max(a,b),y=\min(a,b)$ .
那么也就是求满足 (a and b) = b 或者 (a and b) = a 的数对个数.
先假设 $a>b$ ,求出答案后 $\times 2$ ,再加上 $a=b$ 的 $32$ 组解,就是答案.
枚举 $a$ 有几个二进制位是 $1$ 即可求出 $a>b$ 部分的答案.
$$
ans=32+2\times \sum_{i=0}^5 {5\choose i}\cdot(2^i-1)=454
$$
NOIP2017 提高组初赛 T8
求出由 $4$ 个有标号的点构成的无向简单连通图的数目.
这个就是 bzoj 3456 城市规划 ,于是可以手算 NTT .
用那个暴力 $dp$ 手算一下.
设 $f(i)$ 表示 $i$ 个有标号的点构成的无向简单连通图的数目,边界有 $f(1)=1$ .
转移时用所有图的数目减去不连通的图的数目,
为了计算不连通的图的数目,可以枚举 $1$ 号点所在连通块的大小为 $j$ .
其它的点内部任意连边,但不与这个连通块内的点连边,这样就不连通了.
$$
f(i)=2^{i\choose 2} -\sum_{j=1}^{i-1}{i-1\choose j-1}\cdot f(j)\cdot 2^{i-j\choose 2}
$$
前 $3$ 项可以口算, $f(1)=1,f(2)=1,f(3)=4$ ,代入得到 $f(4)=38$ .
NOIP2017 提高组初赛 T9
将 $7$ 个名额分给 $4$ 个不同的班级,允许有的班级没有名额,求分配方案的数目.
设 $f(i,j)$ 表示 $i$ 个班级分 $j$ 个名额的方案数.
转移时枚举最后一个班级得到了 $k$ 个名额.
$$
f(i,j)=\sum_{k=0}^j f(i-1,j-k)
$$
用前缀和优化一下,得到 $f(i,j)=f(i,j-1)+f(i-1,j)$ ,边界有 $f(i,0)=1,f(0,j)=0$ .
这等价于从 $(1,0)$ 出发,每次向右或向上走一步,走到 $(4,7)$ 的方案数.
则答案为 ${4-1+7\choose 4-1}=120$ .
NOIP2017 提高组初赛 T22
删除一条细边代价是 $1$ ,删除一条粗边代价是 $2$ .
需要以最小的代价使得 $A$ 与 $B$ 不连通,求出这个代价,以及有多少种删边方案的代价是最小的.
平面图转对偶图,对偶图中的最短路长度以及最短路数目就是答案.