初赛试题选做

马上初赛了,假装准备一下.

主定理

假设有递推关系式 $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$ 不连通,求出这个代价,以及有多少种删边方案的代价是最小的.

平面图转对偶图,对偶图中的最短路长度以及最短路数目就是答案.