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$ 时，设 $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)。