0%

NOIP2020sol

NOIP2020 sol

比csp出的好些。

T1 排水系统

题意略。

就是要你写个高精,但显然考场上写高精gcd不太现实,冷静分析一下可以将$(2\times 3\times 4\times 5)^{12}$作为分母,中间过程就不用通分了,最后约分一下就好,只需高精加高精,高精除低精。

My code

T2 字符串匹配

题意:给一个字符串$S$,统计$S=(AB)^iC$的划分方案数且$A,B,C$均非空,$i$为正整数,且$F(A)\le F(C),F(T)$定义为$T$中出现了奇数次的字符数量。

$|S|\le 2^{20},\Sigma=\{a,b,c…z\}$

首先$O(n\ln n\log|\Sigma|)$ 很naive:先预处理每个后缀的$F$和每个前缀的$F$.枚举$AB$的长度$len$,再枚举$i\in[1,n/len]$,如果$len$是$S[1,len\cdot i]$的循环节,那么贡献就是$x<len,F(x)\le F(S[len\cdot i+1,n])$的$x$数量,树状数组即可。

考虑优化掉枚举$i\in[1,n/len]$的过程。

性质:$(AB)^iC$合法且$i>2$,则$(AB)^{i-2}C$也合法。并且若$len$是$S[1,len\cdot i]$的循环节,那么$len$也是$S[1,len\cdot (i-1)]$的循环节。

那么我们二分找出最大的$i$满足$len$是$S[1,len\cdot i]$的循环节。

那么$i,i-2,i-4..$的贡献总和就是$\lfloor\frac{i+1}2\rfloor $乘上 $x<len,F(x)\le F(S[len\cdot i+1,n])$的$x$数量

$i-1,i-3,i-5…$的贡献总和就是$\lfloor\frac{i}2\rfloor $乘上 $x<len,F(x)\le F(S[len\cdot (i-1)+1,n])$的$x$数量

判循环节用kmp,统计$x$用树状数组,复杂度是$\mathcal O((\sum_{i=1}^n\log\frac{n}i)+n\log |\Sigma|)=\mathcal O(n\log |\Sigma|)$

My code

T3 移球游戏

题意:有$n+1$根柱子,前$n$个柱子上面各有$m$个球,第$n+1$个柱子初始没有球。球共有$n$种各$m$个。你每次可以将一个柱子顶端的球放到另一个柱子(当前球数不足$m$)的顶端,要求通过不超过$8.2\times 10^5$次操作,将所有同种颜色的球移到同一根柱子上。

$n\le 50,m\le 400$.

首先我们可以$O(m)$次操作实现利用一个空柱子$p$,一个满柱子$t$,将一个满柱子$s$中满足某个条件的球都放到$s$顶部,其余放在底部(记为split):

  1. 统计$s$中满足条件的球数量$cnt$
  2. 将$t$顶端的$cnt$个放到$p$的顶部
  3. 从顶部开始考虑$s$中每个球,若满足条件则放到$t$顶部,否则放到$p$顶部。
  4. 将$p$顶部的$m-cnt$个放回$s$
  5. 将$t$顶部的$cnt$个放回$s$
  6. 将$p$顶部的$cnt$个放回$t$

那么就有一个$O(n^2m)$的朴素做法:每次将某种颜色的球全部取出来放到一个柱子上。只需将$n$个柱子都split,最后把这种颜色的都放到空柱子上,然后再将某个有球的柱子清空掉。

这样可以70~90分。

两种优化:

  1. 考虑分治。假设要将$[l,r]$这些球归位,且都在$[l,r]$这些柱子上。取$mid=\lfloor\frac{l+r}2\rfloor,$ 我们要将$[l,mid]$这些球放到$[l,mid]$这些柱子上。与上面的朴素算法是类似的,但是可能一个空柱子装不下,这个时候就装满他,然后另取一个柱子作为新的空柱子,然后递归两边。复杂度$O(nm\log n)$,有点难写.My code
  2. 魔改一下朴素做法,乘上一个$\frac{1}2$的常数。

T4 微信步数

题意:有一个$k$维矩形,第$i$维长度为$w_i$。 每个$1\times 1\times 1…\times 1$的格子上有一个球。进行若干轮操作,每轮有$n$个操作,其中第$i$步形如“所有球在第$c_i$维上坐标变化$d_i$ ”,出界的球将被删除。一个球的权值为被删除的时间。求权值和模$10^9+7$,若存在球不会被删除输出-1。

$n\le 5\times 10^5,k\le 10,w_i\le 10^9,d_i\in\{1,-1\}$

首先转化答案,记球$x$的权值为$t_x$.

性质1:任意时刻,存在的球构成一个$k$维矩形。

那么我们维护这个$k$维矩形每一维的边界$l_i,r_i$,每次操作让答案加上$\prod_i(r_i-l_i+1)$,然后修改$l_i,r_i$并和1取max,和$w_i$取min,若$l_i>r_i$就结束。最坏情况下每一轮只能将某一维减少1,故复杂度最坏$O(nk\cdot \max w)$

性质2:记第$i$轮操作中触发了出界的操作集合为$S_i$,有$\forall i>1,S_i=S_2$ 。这是因为每一轮所做的操作都是一样的,那么每一位的总变化量也就不变,除了第一轮是特例,打表也可以发现这个性质。

那么暴力第一轮,然后暴力求出$S_2$,后面只做$S_2$中的操作即可,复杂度$O(k\max w)$.这样是80分。

推论:$\forall i>1,$第$i$轮开始时第$j$维的剩余长度$f_{i,j}$为关于$i$的一次函数。进一步, $\forall i>1,$第$i$轮开始时$\prod_jf_{i,j}$ 为关于$i$的$k$次多项式。更进一步,第$i$轮所有操作的贡献总和也是$k$次多项式。

考虑$k$很小,用我们求出前$k+1$个点值,就能插值得这个$k$次多项式,也就可以对任意$i$(除了最后一轮,因为最后一轮在中途结束了)求出第$i$轮贡献总和,记为$F(i).$

我们要求

$F(1),F(all)$可以暴力,但中间这些不能每个都求。

考虑$\sum_{i=1}^ni^k$是关于$n$的$k+1$次多项式,易推得$\sum_{i=2}^{all-1}F(i)$是关于$all$的$k+1$次多项式。同样可以插值。

复杂度$\mathcal O(nk)$

My code