洛谷2017春节联欢赛 Hello Dingyou 比赛结果&题解

回复帖子

@Created_equal1 管理员 2017-01-30 22:22 回复

恭喜@Claris 获得Rank1并以700分满分的成绩AK!Claris将可以获得"化物语"L型文件夹一个(挂号信包邮)。

神秘奖励获得者:本场比赛分数与201.7最接近的选手

恭喜@zhouyonglong 获得神秘奖励——舰娘的手机链(挂号信包邮)

所有在本场比赛中获得209分以上的选手均可以获得洛谷最新版的明信片一张。

奖品收取地址:奖品

@Created_equal1 管理员 2017-01-30 22:23 回复 举报

题解(一)

签到题

根据题目名称,我们可以看出这是一道签到题。

考虑一个数 $x$ 只可能有一个大于 $\sqrt{x}$ 的质因数,我们预处理出所有 $\leq \sqrt{x}$ 的质数,对于这些质数的倍数记录一下,对于每个数我们用这些质数暴力除,这样就可以分解完每个数的质因数了。

我们要求的那个签到函数其实就是 $x-\varphi(x)$ 。

复杂度大约是 $O(\sqrt{r}logr+|r-l|logr)$ 的。

美好的每一天

一个区间可以重排成为回文串,即区间中最多有一个字母出现奇数次,其他的都出现偶数次

发现这个和 $xor$ 类似

$a -> 1$

$b -> 2$

$c -> 4$

$d -> 8$

$z -> 2^{25}$

这样如果一个区间的 $xor$ 和为 $0$ 或者 $2^x$ ,则这个区间可以重排成为回文串,即回归天空

把每个位置的值变为前缀 $xor$ 和,那么区间 $[l,r]$ 可以回归天空当且仅当 $a[l - 1] \oplus a[r]$ 为 $0$ 或者 $2^x$

$a[i]$ 即 $1->i$ 的异或和

这样用莫队算法,可以做到 $O( 26n\sqrt{n} )$ 的复杂度

空间可以用 $hash$ 表,也可以开一个 $2^{26}$ 的数组

$hash$ 表估计被卡常

但是 $1 << 26$ 的 int 数组要 $256 MB$,空间不够

因为 $n \leq 6 * 10^4$ ,所以可以用 unsigned short 来存,这样空间就够了

其实用 short 来存也可以,因为是前缀异或和,所以不会有相邻的两个相同。。。其实本来可以出到 $1 * 10^5$ 的

出题人用的膜队有点膜法,在香港当过新闻工作者,所以好像跑得比较快,不小心卡了常数,其实时限开的是标程的两倍

@Created_equal1 管理员 2017-01-30 22:25 回复 举报

题解(二)

Koishi Loves Construction

Task1:

通过爆搜观察发现,除了 $1$ 以外的奇数都无解,偶数都有解。

证明:由于 $n|n$ ,也就是说 $n$ 必须放于第一位,前缀和第一位一定是 $0$ ,奇数情况下又由于 $n|\frac{n(n+1)}{2}$ ,也就是说前缀和最后一位一定是 $0$ ,导致矛盾。

打表观察,每个偶数搜出来的方案都有 $n,1,n-2,3,n-4,5\cdots$ ,不难证明其正确性。

Task2:

通过爆搜观察发现,除了 $4$ 以外的合数都无解,质数都有解。

证明:考虑到 $n|n!$ ,那么前缀积的最后一项一定是 $0$ ,也就是说最后一项尽量放 $n$ ,那么这要求 $n\nmid(n-1)!$ ,发现只有 $4$ 和质数胜任这个要求。

打表观察,每个质数搜出来的前缀积方案都有 $1,2,3,4\cdots p$ ,也就是说第 $i$ 位就是 $\frac{i+1}{i}$ ,通过逆元算出来就可以了。1和4的情况特判即可。

Koishi Loves Segments

被骂成原题了啊,可能是我题目做的太少的缘故,我真的没看过接近的题目啊QAQ

从左到右加入线段,当存在一个点不符合要求时,就删除掉覆盖了它的右端点最远的线段。这个可以离散化后用一个set维护线段集合做到。

好像所有选手写的都是区间减线段树模拟删除线段啊,我明明不是故意卡常的啊,为什么会这样子呢。

Koishi Loves Number Theory

先列两个结论

  • $gcd(x^n-1,x^m-1)=x^{gcd(n,m)}-1$

  • $lcm(a_1,a_2,...a_N)=\frac{1元gcd之积*3元gcd之积...}{2元gcd之积*4元gcd之积...}$

结论1可以考虑辗转相除法证明,结论2可以考虑lcm的积性求质因子贡献,这里不详细展开。

$a_i$ 的范围很大,但它们的 $gcd$ 数量很少。开一个map维护每个gcd和它的贡献就没了啊。

剩下的就是暴力了

@Created_equal1 管理员 2017-01-30 22:25 回复 举报

题解(三)

随机数生成器

首先如果两个询问区间为 $[l1,r1]$ 和 $[l2,r2]$ ,$[l2,r2]$ 被 $[l1,r1]$ 完全包含($l1 \leq l2 \leq r2 \leq r1$),这样 $[l1,r1]$ 就废了(因为它的询问结果肯定较小),排序预处理一下就可以去掉所有这些没用的区间了。有用的区间左端点两两不同,而且按左端点排序,右端点就会严格递增。

我们考虑有限的期望公式,对于一个随机整数变量 $x \geq 0$ ,它的期望 $E(x)=\sum_{整数s\geq 1} P(x \geq s)$ 。

我们考虑如何暴力地求出 $P(x \geq s)$ ,直接算不是很方便,我们考虑计算 $1-P(x \leq s-1)$ 。

既然测试结果是这些询问得到的结果的最大值,那么只要保证每个询问结果都 $\leq s-1$ 就好了,即每个询问区间内都至少有一个数 $\leq s-1$ 。

考虑搞一个dp,我们用 $f[i][j]$ 表示考虑 $a_1...a_i$ 的时候能满足询问1~j的概率,前面排序后这个东西可以简单地dp出来。这样就能获得50分了!(感觉如果按这个思路也是能做满分的,不过出题人比较菜没有想出来)

考虑我们换一种思路来做,对于每个元素考虑它能满足哪些询问。我们可以发现满足的询问一定是一个连续区间,而且依次考虑每个元素得到的每个询问区间也是满足左端点右端点都不降的。

这样我们就把问题转化成了:有若干个区间,这些区间左右端点都不降,要覆盖整段,每个区间选的概率为p( $p=\frac{s-1}{x}$ ),问覆盖全段的概率。

考虑用$f[i]$表示考虑前i个区间,选择第i个区间,覆盖1~i区间右端点的概率,它可以用前面任意一个与第i个区间有交集的区间来转移。

容易得到转移方程 $f[i]=p\times(\sum_{r[j] \geq l[i]-1} f[j]\times (1-p)^{i-j-1}+[l[i]=1](1-p)^{i-1})$ ,答案就是 $\sum_{r[i]=n} f[i]*(1-p)^{n-i}$ 。

考虑把f的转移方程写的美观一点; $f[i]=p\times(\sum_{r[j] \geq l[i]-1} f[j]\times (1-p)^{-j}\times(1-p)^{i-1}+[l[i]=1](1-p)^{i-1})$ ,这样我们大概可以用一个树状数组来维护 $f[j]\times (1-p)^{-j}$ ?

如果你真的这样写了70分,那么恭(ha)喜(ha)你(ha)了(ha)。既然l[i]、r[i]都不降,只要two-pointer一下就是线性的了。这样就过了。

其实 $x \leq 10^7$ 也是能做的,不过没(lan)什(de)么(xie)意(biao)思(cheng)就不出了。

雪辉

如果是一个序列,每次询问区间的mex怎么做

分块,预处理任意两块之间的bitset,然后每个询问只需要加入 $log$ 个数就可以了,复杂度 $O( ( n + m )( \sqrt{ n } + n / 64 ) )$

树上同理

在树上选择 $\sqrt{ n }$ 个点当作关键点,有一个贪心的方法可以保证任意两个关键点之间的距离是 $O( \sqrt{ n } )$ 的

按深度从大到小枚举树上的每个点,将点x标记为关键点当且仅当 $x$ 的子树中有一个点到 $x$ 的距离大于 $\sqrt{ n }$ 且不为关键点

或者直接随机 $\sqrt{ n }$ 个点当作关键点也可以保证复杂度

考虑预处理关键点之间的bitset,发现不能套用序列上的做法,因为dfs涉及到撤销,如果套用序列上的做法就需要使用可持久化bitset,复杂度变为 $O( n^2 )$

考虑将原树重构为 $\sqrt{ n }$ 个点的新树,即只有关键点的新树

重构树中两点之间连有边当且仅当这两个关键点在原树中形成的链上没有其他关键点

重构树的边权是一个bitset,存有这两个关键点之间的数

通过这个新的树,可以在 $O( n( \sqrt{ n } + n / 64 ))$ 的时间预处理任意两点之间的bitset

每个询问是多个树链的并,那么可以搞出每个树链的bitset之后在把他们或起来

树链 $( x , y )$ 的答案即相当于 $( x , l )$ 的答案或 $( y , l )$ 的答案,$l$ 为 $x , y$ 的lca

至于为什么不能直接求 $( x , y )$ 的答案,因为预处理的两个点之间的bitset是相对于重构树的,有可能会加入多余的点

与序列上的处理方法相似,每个询问只需要加入 $\sqrt{ n }$ 个数即到达一个关键点

总复杂度 $O( ( n + m )( \sqrt{ n } + n / 64 ) )$

因为stl的bitset没法支持询问mex,所以要手写bitset

@fakeman 2017-01-31 16:39 回复 举报

问一下

签到题复杂度中,(r-l)*log r的log 是怎么来的?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。