SNOI2020 day1 题解

## D1T1 ## D1T2 题意： 有两个人在玩游戏，有 $n$ 个石子，初始有一个参数 $k$。第一个人可以取 $1\sim k$ 个石子，接下来两个人轮流操作，设上一次操作中取了 $x$ 个石子，则这一次可以取 $1\sim 2x$ 个石子。取完了所有石子的人输。 给出 $q$ 组询问，每个询问给出 $N,k$，求 $1\le n\le N$ 中有多少组 $n,k$ 是先手必胜的。 $1\le q\le 10^5,1\le N,k\le 10^{18}$ 题解： 最后一次一定是取 $1$ 个石子。所以可以看成 $n-1$ 个石子，取完所有石子的人赢。 打表找出什么时候可以赢。 对于 $i$ 个石子的情况，可以发现存在一个值 $f_i$，满足 $k<f_i$ 时，先手必输，$k\ge f_i$ 时先手必胜。这个非常容易证明，因为第一次可以取 $k$ 的话一定可以取 $k-1$ 个。 然后找一找 $f$ 的规律。 1. 可以发现，若 $f$ 为 $fibnacci$ 数，则 $f_i=i$。 2. 对于两个 $fibnacci$ 数 $i,j$ 之间的数 $k$，$f_k=f_{k-i}$。 这样我们就可以得到一个做法。 首先，所有 $f_i$ 只有 $O(\log N)$ 种取值，所以我们预处理出 $N$ 为 $fibnacci$ 数时每种取值的出现次数，然后求一下前缀和。 每次找到最大的不超过 $N$ 的 $fibnacci$ 数，$O(1)$ 算出给答案的贡献，然后将 $N$ 减去这个数。 单次复杂度为 $O(\log N)$。 简单证明一下 $f$ 的规律，就是对于一个 $n$，对它进行 $fibnacci$ 分解(每次找一个最大的不超过 $n$ 的 $fibnacci$ 数减掉)，然后检查最小的那个是否 $\ge k$。 考虑进行归纳证明。 $n=1$ 时，$f_n=1$ 没有问题。 $n>1$ 时，设 $n$ 分解成的最小 $fibnacci$ 数为 $x$，如果 $k<x$，那么操作之后一定有 $k'\ge x'$。设这次取掉的石子数为 $a$，考虑对 $a$ 进行 $fibnacci$ 分解。 $fibnacci$ 分解有一个性质，就是不存在相邻的 $1$，否则就可以合并为更大的 $fibnacci$ 数。 我们对 $x$ 的 $fibnacci$ 分解(初始是 $10000\cdots$ )和 $a$ 的 $fibonacci$ 分解进行减法： 设 $x$ 的最低位 $1$ 的位置是 $p$ 1. 如果 $a$ 的第 $p-1$ 位为 $1$，那么 $x$ 第 $p$ 位变成 $0$，第 $p-2$ 位变成 $1$，$a$ 的第 $p-1$ 位变成 $0$。由于 $a$ 的第 $p-2$ 位是 $0$，所以 $p-2$ 位对应的 $fibnacci$ 数比变化后的 $a$ 大，于是最终一定存在一个位 $\le p-2$，满足这个位是 $1$，并且由于这个位比 $a$ 小，所以满足条件。 2. 如果 $a$ 的第 $p-2$ 位为 $1$，那么类似上面，最终一定存在一个位 $\le p-1$，满足这个位是 $1$，并且由于这个位比 $2a$ 小，所以满足条件。 3. 如果 $a$ 的第 $p-1,p-2$ 位都是 $0$，那么 $x$ 第 $p$ 位变成 $0$，$p-1$ 和 $p-2$ 位变成 $1$，继续进行上述操作。 设它分解出的最小的数为 $b$，那么如果一个数 $fibnacci$ 分解的最小值 $>2b$，将 $a$ 与这个数相加，一定无法构成一个 $fibnacci$ 数。 如果 $k\ge x$，那么这次就去掉 $x$ 个，我们会到达一个 $k'=2x<x'$ 的情况，因为 $x$ 之后的第一个 $fibnacci$ 数一定不存在于 $n$ 的 $fibnacci$ 分解中，否则就可以将它们两个合并。 ## D1T3 题意： 给一个长度为 $n$ 的序列 $a$，支持下列操作 $m$ 次： 1. 给出一个区间 $[x,y]$ 和一个数 $w$，令 $a_i(l\le i\le r)=\max(a_i,w)$。 2. 给出一个区间 $[x,y]$，求这个区间的最大子段和。 $1\le n\le 10^5,1\le m\le 2\times 10^5,|a_i|,|w|\le 10^9$ 题解： 考虑分块，我们需要维护出每个块的最大前缀和，最大后缀和，最大子段和。 借用势能分析线段树的思想。将最小值看做一个变量，这样所有的信息都可以表示为若干个一次函数的 $\max$，如果我们能快速建出来凸包，就可以用一个指针在凸包上面扫，实现查询。如果某一次的 $w\ge $ 块内次小值，就重构整个块，重构总次数最多为块内不同值的个数。 可以发现，最大前缀和和最大后缀和非常容易在线性时间内构建，但是最大子段和没有办法直接求出。 所以考虑对每个块建立一棵线段树，每个节点维护对应区间的最小值、次小值，以及关于最小值的最大前缀和、最大后缀和、最大子段和。 在合并两个儿子的时候，前缀和以及后缀和可以在线性时间内求出，合并左儿子的后缀以及右儿子的前缀来更新最大子段和的时候，需要用到闵可夫斯基合并凸包，复杂度也是线性。 于是对于一个长度为 $l$ 的块，它最多重构 $l$ 次，那么总复杂度为 $O(l^2)$。 对于一个块内(块大小为 $s$)的所有线段树节点，它们的总复杂度是 $$O(s^2+2\times(\frac s 2)^2+4\times(\frac s 4)^2+\cdots)=O(s^2+\frac {s^2} 2+\frac{s^2}4+\cdots)=O(s^2)$$ 于是修改的总复杂度为 $O(s^2\times \frac{n}{s})=O(ns)$。 查询的时候我们拿出来组成 $[l,r]$ 区间的所有线段树节点，一共有 $O(\log n+\frac n s)$ 个。 于是查询的总复杂度为 $O(n(\log n+\frac n s))$(这里认为 $n,m$ 同阶)。 当 $s=\sqrt n$ 时，总复杂度最小为 $O(n\sqrt n+n\log n)$。