XJOI 模拟赛题解

菜鸡 Karry5307 只会做 T1~T4 呢,还是太菜了,做不出国集水平的题目呢。

T1

大胆猜想答案为 $n(n+1)-1$。

对于 $n$ 为奇数我们可以按照如下方法构造:

也就是从 $(1,1)$ 出发走到 $(1,n+1)$,然后每一次往下走一步之后反复横跳即可。

但是如果 $n$ 为偶数呢?

可以这么构造:

也就是先从 $(n,1)$ 走到 $(1,1)$,每一次往右走之后反复横跳即可。

容易证明不存在比这种解法更优的解了。

T2

注意到我们对于每个点只需要拿他与离它最远的点贡献一次就好了,别的决策都是没有用的。

所以说考虑把树的一个直径抠出来,那么离某个点最远的点一定是直径的端点(证明可以用反证法)。

T3

有一个很暴力的状压 $\texttt{dp}$,考虑枚举一下集合 $S$ 转移即可。

发现 $S$ 是个区间,状态数变成 $O(n^2)$,枚举一下进行的操作和操作完的位置即可 $O(n^4)$,使用前缀和优化可以达到 $O(n^3)$。

考虑对操作做一个完全背包,然后钦定操作完之后 $S$ 必须位于不同的区间。

这样状态数变成 $O(n)$,也即覆盖了一个前缀或是一个后缀或是一整段。

于是就可以 $O(n^2)$ 解决。

T4

首先,如果 $m$ 是奇数的话先手取 $1$ 就可以赢了。

否则双方每次只能取偶数。(如果某一方取了奇数的话剩下的行动值是奇数那么另一方就可以取 $1$)

所以我们可以把总行动值与每次操作取得除掉一个 $2$,于是当 $2\nmid m$ 的时候有

$$
h_m=1
$$

以及

$$
h_{2m}=2h_m
$$

明显 $h_x=\operatorname{lowbit}(x)$,所以答案就是

$$
\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor\operatorname{lowbit}(i)
$$

这个可以用整除分块做,复杂度是 $O(\sqrt{n}\log n)$,可以拿到 $69\sim 100$ 分,但是这不是正解。

考虑枚举 $h_i$ 的取值并统一计算贡献,方便起见我们设 $g(n)=\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$,那么答案为

$$
g(n)+\sum\limits_{k\geq 1}2^{k-1}g\left(\frac{n}{2^k}\right)
$$

时间复杂度为 $O(\sqrt{n})$。

计算单个 $g(n)$ 可以用整除分块做,尽管是 $O(\sqrt{n})$ 的,但是常数比较大,可能拿不到满分。

可以这么做:

$$
g(n)=\sum\limits_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[ij\leq n]=2\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}1-\sum\limits_{i=1}^{\sqrt{n}}\sum\limits_{j=1}^{n}1=2\sum\limits_{i=1}^{\sqrt{n}}\left\lfloor\frac{n}{i}\right\rfloor-\left\lfloor\sqrt{n}\right\rfloor
$$

暴力枚举即可,常数比整除分块小,可以通过。

T5

不会,留坑。

代码

$\texttt{T1}

$\texttt{T2}

$\texttt{T3}

$\texttt{T4}\ O(\sqrt n\log n)

$\texttt{T4}\ O(\sqrt{n})

发表评论