2021.10.04模拟赛

Some deserts on this planet were oceans once

2021.10.04模拟赛

A. aplusb

如果 $n$ 是奇数显然取 $\lfloor\dfrac{n}{2}\rfloor\pm 1$ 最优

偶数可以打表找规律 发现如果只有一个 $2$ 因子，那还是取 $\dfrac{n}{2}\pm1$

否则的话取 $\dfrac{n}{2}\pm 2$

B. 道路

道路

先考虑求 $k^0$ 的经典问题，城市规划

设 $g_i$ 为 $i$ 个点的无向图方案数，设 $m=\binom{n}{2}$ 显然有 $g_i=2^{\binom{n}{2}}$

$f_i$ 为无向连通图的方案数，需要减去不合法状态

枚举 $1$ 所在的连通块大小为 $j$ 则 $f_i=g_i-\sum\limits_j\binom{i-1}{j-1}f_jg_{i-j}$

那我们用 $g_{i,k}$ 表示 $i$ 个点 $m^k$ 的和，设 $\vartheta = x\mathrm{D}$ 则 $g_{i,k} = \vartheta^k(x+1)^{\binom{i}{2}}|_{x=1}$

而计算 $f_{i,k}$ 时拼接起来的和可以用 $(a+b)^m$ 展开来处理

code

C. hole

hole

先考虑没有插入点的的三角形数点怎么做

因为是等腰直角三角形，斜边上的 $x+y=d$ ，所以按 $x+y$ 排序差分

黄线处减，蓝线处加，左右两个平行四边形分别拿树状数组减出来即可

那加上时间就直接 CDQ 即可

code

D. 斐波那契

斐波那契

Solution

code