0%

NOIOL题解

NOI Online sol

好像都是sb题,但我没AK啊,可能我是sb吧

提高组

游记都是流水账,懒得写了.

T1

简化题意:给序列$A,B(|A|=|B|=n)$和$m$种操作,1操作可以让$u_i,v_i$都+1或-1,2操作可以让$u_i+1,v_i-1$或$u_i-1,v_i+1$,问能否让$A=B$

$n,m\le 10^5$

如果让$u+1$且$u,v$间有2操作,则可以使用2操作让$u-1,v+1$,即对$u$的+1操作转移到$v$上.也就是说,对于由2操作构成的连通块$S$,对任何一个点$x\in S$的+1操作都能转移到另一个点$y\in S$上.因此将整个联通块看成一个点(显然可以并查集做到,以下的点都指这些点).点权为$\sum_{x\in S}b_i-a_i$.

此时问题转化为,只有1操作(可以将其看作无向边),能否让所有点点权为0.

考虑一个奇环$R$,对$u,v\in R$执行1操作,可以让任意两点$x,y\in R$都+1或-1.所以对于非二分图连通块$G$,若$\sum_{S\in G}W_S$为偶数则可以做到,否则不能.对于二分图连通块$G$,若$\sum_{S\in G}W_S=0$则可以做到.

时间复杂度$O((n+m)\log n)$,这个log是路径压缩的并查集的.

code

T2

题意:给一个排列$p$,要支持两种操作:

  • 交换$x,x+1$
  • 询问$k$次冒泡排序之后的逆序对数

$n,m\le 2\times 10^5,k\le 2^{30}$

两个性质:

  • $n$次冒泡之后数列有序,不存在逆序对

  • 记$inv(i)=\sum_{j\lt i}[p_j\gt p_i]$,则$k$次冒泡之后

    BIT预处理一下$inv$,然后两个BIT维护就好.
    修改的时候只影响两个位置,BIT上直接搞.
    时间复杂度:$O((n+m)\log n)$

    code

T3

给一个正整数环$A$,每次询问间隔$k$的数对乘积之和的最大值(你可以任意改变环的顺序)

$n,m\le 2\times 10^5$

简单的贪心:先考虑$gcd(n,k)=1$的情况:

最大的边上放第二大,第三大;第二大边上放第四大(已经在最大边上)

和暴力对拍下可知正确性

简单来说就是当前可选集合中最大的应该选尽量大的放在边上

比如说$a>b>c$,如果$(a,c,b)$那么贡献是$ac+bc$,而$(a,b,c)$贡献是$ab+bc$.因为$b>c$所以$ac>bc$.

对于不互质的情况,可以拆成$gcd(n,k)$个大小为$\frac{n}{gcd(n,k)}$的环,每个环如上处理即可.暴力做时间复杂度是$O(n^2)$,考虑相同的$gcd(n,k)$结果必然相同,记忆化一下就好了,时间复杂度$O(n\sqrt n)$

code

普及组

其实也就T2比较玄妙吧

T1

不会(

T2

题意:求和为$n$的本质不同正整数序列数.
$n\le 10^5$
暴力背包有70pts.
做法一:生成函数+五边形数做法:
记答案序列的生成函数为

五边形数定理:

能对$p(i)$产生贡献的项是$\mathcal O(\sqrt n)$级别的,所以总时间复杂度$\mathcal O(n\sqrt n)$

code
做法二:分块背包:
暴力的做法显然:$f(i,j)$表示用$[1,i]$的数凑出$j$的方案数.转移类似完全背包,时空都是$\mathcal O(n^2)$

考虑取一整数$m$,用$g(i,j)$表示用$i$个不小于$m$的数凑出$j$的方案数.

转移就是整体加一,或加入$m$这个数,即

显然只有$i\le n/m$的$i$是有意义的,这部分的时间复杂度是$\mathcal O(n/m\times n)$,同时用$f$算用$<m$的数凑出$n$的方案数,总时间复杂度是$\mathcal O((m+n/m)n)$,显然$m=\sqrt n$的时候最优,最优的时空复杂度为$\mathcal O(n\sqrt n)$

code

T3

相比于T2,其实这题更套路.

首先$n\le 100$暗示Floyd,先求出$dis^0(i,j)$表示$i->j$不用魔法的最短距离
设$dis^k(i,j)$表示$i->j$恰用$k$次魔法的最短距离 (由于所有边权非负,$dis^k(i,j)$关于$k$单调递减所以$dis^k(1,n)$即为答案,求出它即可.)

若已知$dis^{k-1},dis^1$,则

一个广义矩阵乘法的形式,如果知道了$dis^1,$直接矩阵快速幂就好,时间复杂度$\mathcal O(n^3\log K)$
求$dis^1$也简单,枚举每条边$(u,v,w)$做为变成负权的那条边,那么$dis^1(s,t)=dis^0(s,u)-w +dis^0(v,t)$,时间复杂度$\mathcal O(n^2m)$

总时间复杂度$\mathcal O(n^3\log K+n^2m)$

code

奇怪的NOI Online比赛,出了各种锅反正不要钱,就当玩玩也行