0%

NOIOL2-sol

NOIOL2 题解

比上次办的好多了至少有LaTeX了

注:提高组的题,如果在acwing上提交,请手动O2,否则可能会被卡常(我放的代码在洛谷等OJ上是不用O2也可以A的)

提高组

T1

题意:给出$a,b,k$,要求$a$的倍数格子填颜色1,$b$的倍数格子填颜色2,是$ab$倍数的格子颜色任选.求是否存在一种填法,满足忽略掉无色格子后不存在$k$个连续的同色格子.

$1\le a,b,k\le 10^9$

解:若$k=1$,必然不存在.

若$a<b,a,b$互素,则$ax\ mod\ b$必然取遍$[0,b-1]$.设$ax\ mod\ b=1$.则$[1,b-1]$这一段中恰有$\lfloor \frac{(b-2)}{a}\rfloor +1$ 个格子是颜色1.也就是无论是$ab$倍数的格子怎么填,都至少有$\lfloor \frac{(b-2)}{a}\rfloor +1$个连续的无色格子.且将$ab$倍数的格子都填颜色2时,可以得到至多有$\lfloor \frac{(b-2)}{a}\rfloor +1$个连续的无色格子.所以当且仅当$\lfloor \frac{(b-2)}{a}\rfloor +1 < k$时有解.

对于一般情况,令$a/gcd(a,b),b/gcd(a,b)$即可规约到$a,b$互素之情况.

每组数据时间复杂度$\mathcal O(\log min(a,b))$

code

T2

题意:给一个长度为$n$的序列$A$.定义$f(l,r)$为$A[l,r]$中不同的数字个数.求

$n\le 10^6$,$1\le A_i\le 10^9$

暴力:先离散化,然后枚举两个端点统计即可.时间复杂度$\mathcal O(n^2)$

考虑优化:(这里记$i$为右端点,$j$为左端点)

考虑加入$i$后的贡献,即$f(j,i)-f(j,i-1)$.求出$last(A_i)$表示$A_i$上一次出现的位置(未出现过则为0)

  • 对于$j\le last(A_i),f(j,i)=f(j,i-1)$
  • 否则$f(j,i)=f(j,i-1)+1$

然后$\sum_{j=1}^i f(j,i)^2$就是$i$对答案的贡献了.这个东西显然就是区间加,区间平方和.这个东西线段树好像不能直接做.考虑$f(j,i-1)^2$到$f(j,i)^2$的变化(对于$j>last(A_i)$)

所以只需要区间加,区间和就行了.线段树即可维护.时间复杂度$\mathcal O(n\log n)$ (据说有点卡常,但我觉得常数正常的线段树都能过啊….)

code

T3

借鉴(chao xi)了神仙yijan的题解

题意:给一棵树,恰$n/2$个白点,$n/2$个黑点,每次将黑白点两两配对,求配对$n/2$次后恰有$i$对点为祖先-后代关系 的数量.(对998244353取模).

$n\le 5000$

解:恰$i$对不好求,因为树形dp时状态至少有三维,因此复杂度不会低于$\mathcal O(n^3)$

考虑求解”钦定(至少)$i$对点为祖先-后代 关系的数量”.记$dp(u,i)$表示以$u$为根的子树中钦定$i$对点的方案数.考虑转移:

  • 枚举子树$v$中已配对的点的数量,做树形背包的转移
  • 将当前点和某个后代配对

前者就是树形背包,因此时间复杂度为$\mathcal O(n^2)$(原理就是每对点仅在LCA处贡献一次),后者显然是$\mathcal O(n^2)$ .以此可以求出$f(i)$表示整棵树中钦定$i$对点,剩下的任意匹配:

求出$f$后,即可求原答案:记$g(i)$表示恰有$i$对点为祖先-后代关系 的数量.因为有

二项式反演得:

这个能预处理阶乘及其逆元算了. 时间复杂度$\mathcal O(n^2)$

code

普及组

T1

题意懒得概括了.

贪心一下,先选大的$a$直到满足.直接排序再二分就行.时间复杂度$\mathcal O(n\log n)$
code

T2

题意懒得概括了.

略有点毒.

首先bfs是很显然的,记$dis(x,y,t1,t2)$表示到$(x,y)$且隐身$t1$次,传送$t2$次所需要的最小时间.枚举八个方向于传送的四个方向转移即可.

但这题有点毒,直接做MLE+TLE.$dis$数组不会爆空间,但队列会(因为要存4个元素).解决MLE一个方法是把$x,y$压成一个整数,$t1,t2$压成另一个整数,用到的时候解码.这样空间在300MB左右,能过.解决TLE的话,首先是隐身不要看成技能,而是看成走到一个被观察到的格子后需要付出的代价.另外加一个最优性剪枝,就能过了.

另外,预处理格子是否被覆盖的时候,暴力搞是$\mathcal O(n^4)$的,有两种解决方案:

  • 多源bfs
  • 对覆盖到的行差分一下,最后做个前缀和,若该位置被覆盖至少一次就是被观察到的.

最后注意一下即使隐身也不能走到有观察员的位置.时间复杂度$\mathcal O(nmC1C2)$ 准确的说是O(能过)

code

T3

题意:有$2n$栋楼房,高度均在$[1,m]$之间.求满足以下条件的方案数,对998244353取模.

  • 前$n$栋楼房高度单调递增,后$n$栋楼房高度单调递减
  • 第$x$栋楼房高度和第$y$栋相等,$x,y$是给定的整数.

$1\le x<y\le 2n,1\le n,m\le 10^5$

解:考虑这样的问题:$n$栋楼房,允许的高度范围为$m$,则单调递增的方案数为?

首先,对于一个方案,必然有且仅有一种方案满足改变其顺序能得到一个单调递增序列.也就是所求等价于本质不同序列数.这个东西就是:

这个式子用一个隔板法就能搞出来了.

接下来对$x,y$分类讨论以下:(已知$x<y$)

  • $x,y\le n$,枚举他们的高度$i$,则答案即为$\sum_{i=1}^m f(x-1,i)\times f(n-y,m-i+1)$
  • $x,y>n$同理.
  • $x\le n,y>n$.同样枚举高度$i$,答案为$\sum_{i=1}^m f(x-1,i)\times f(n-x,m-i+1)\times f(y-(n+1),m-i+1)\times f(n+n-y,i))$

预处理以下阶乘和逆元就行了.时间复杂度$\mathcal O(n\log mod)$或$\mathcal O(n)$

code

End.