0%

yLOI2020 题解

yLOI2020 题解

扶咕咕6题4.5h残忍虐杀脑子慢手速慢选手Orz.不过题的质量是很好的,尤其是D题,我可能一辈子都出不出这种题,真的只能Orz。

T1 金陵谣

题意:求$\frac{a}x+\frac{b}c=\frac{d}y$的正整数解$(x,y)$数量。

$a,b,c,d\le 10^6,c\times d\le 10^6$

枚举$y\in [1,c*d]$并判断即可。复杂度$\mathcal O(c\times d)$.

T2 不离

题意$n$件物品,有属性$a_i,b_i.$角色有属性$A,B$.若其$A\ge a_i,B\ge b_i$则可以使用,此后$A$增加$c_i$,$B$增加$d_i$.

在可以通过某种顺序使用所有物品的前提下, 你需要最小化初始的$A$,同时最小化初始的$B$.

$n\le 10^5,a_i,b_i,c_i,d_i\le 10^9$

不考虑$B$的限制,那么$A$越大必然越容易合法,即有单调性。二分答案,将物品按$a_i$排升序后贪心判断即可。

现在已知了最小的初始$A$,求最小的初始$B$.此时$B$同样有单调性,再二分答案,check时将所有$a_i\le A$的物品塞进一个堆里,每次取出堆中$b_i$最小的,能取就取即可。

复杂度$\mathcal O(n\log n\log v).$

T3 泸沽寻梦

题意:给一个长度为$n$的正整数序列,有$m$次修改,将$a_p,a_{p+1}$异或上$x$,询问异或和为0的子区间数量。

$n,m\le 10^6$

考虑原序列的前缀异或和,问题就变为单点修改和询问$\sum_{x}\frac{cnt_x(cnt_x-1)}2$,其中$cnt_x$表示$x$的出现次数。

由于是单点修改,所以暴力改就好了。值域小时直接开桶,值域有点大,离散化后再求就好了。

复杂度$\mathcal O(m\log m).$

T4 牵丝戏

这题非常nb,当时做了大约2h,并且我这辈子可能都出不了这种题。

题意…好吧,我不知道怎么概括。

$n\le 10^3,m\le 10^5$

首先$m\le 10^5$非常吓人,并且一回合可以使用多个不同的道具很难处理。先跑一次01背包,求出增加恰好$i$个delay值能获得的最大增幅,记为$w_p$。这一步是$\mathcal O(Dm)$的,$D=200.$

接下来是博弈部分。这部分关键在于,如果剩余轮数确定,且当前两人delay值差确定,则无论是怎样达到这个状态,之后的操作不变。于是可以考虑dp。

已知初始局面的delay值差$d_a-d_b$,我们有两种方式做dp:

  • 令$f(i,j)$表示进行了$i$轮,delay值差为$j$,这$i$轮中造成的伤害差值。 从第0轮开始,$f(0,d_a-d_b)=0$,其余为$+\infty$.取答案为$\max_jf(n,j)$.
  • 令$f(i,j)$ 表示从第$i$轮到第$n$轮,当前delay值差为$j$,将会造成的伤害差值。从第n轮开始,$f(n,j)=0$.取答案为$f(0,d_a-d_b)$.

对于大部分的问题,两种方式都正确。但这题存在特殊性:对于方法1,$f(n,j)$可能并不会真的“达到”。

比如$f(2,-10)$只能由$f(1,1)$转移过来,值为10.$f(2,-5)$可以由$f(1,1)$和$f(1,100)$转移过来,值为3.取答案为$\max(3,10)=10$是不对的,因为博弈时对手从$(1,1)$出发直接走到$f(2,-5)$令答案为$3$,而不会取$f(2,-10)$.

因此只能用第二种方法。具体的,令$f(i,j)$表示现在是第$i$轮,delay值差为$j$,到第$n$轮结束将造成的伤害差值。

答案为$f(0,d_a-d_b)$.

总复杂度$\mathcal O(Dm+D^2n)$.

T5 凉凉

最后5min没有rush出来,非常自闭

直接给转化一步后的题意了:

给一个$n$个点的无向图,在点$i$上放数字$j$会造成$w_{i,j}$的代价。求在所有相邻点的数字不同的前提下最小的代价和。

$n\le 14$

由于$n\le 14,$考虑复杂度为$\mathcal O(3^n)$级别的状压dp。先预处理出$g(x,T)$表示将$T$中所有点上都放数字$x$的代价和(不合法则为$+\infty$)。

令$f(S)$表示在点集$S$上放数字且合法的最小代价和。大致思路是,每次枚举$S$的一个子集$T$,钦定$T$中所有点深度都为$x$,即$f(S)\leftarrow^{\min}f(S-T)+g(x,T)$.

存在一个小问题,即$S$中所有深度为$x$的点必须都在$T$中,否则无法保证合法。可以类似分组背包,先枚举$x$,再倒序枚举$S$,再枚举其子集$T$做$f(S)\leftarrow ^{\min}f(S-T)+g(x,T)$的转移。

复杂度$\mathcal O(3^nn)$

T6

直线上有$n$个目标点。$m$个询问,每次询问$x_i$随机游走到最近的目标点的期望距离。

70%:$n,m,x_i\le 10^5$.100%:$n,m\le 10^5,x_i\le 10^9$,保证所有$x_i$两侧均有至少一个目标点。

70pts非常白给:记两个相邻目标点距离为$p,f(i)$表示距左边目标点距离为$i$,随机游走到目标点期望步数。易得$f(i)=\frac{f(i-1)+f(i+1)}2+1$.做一个稀疏矩阵高斯消元即可做到$\mathcal O(p).$

100pts的话可以用上面的方法打个表,观察得距离为$p$时$f(i)=(p-i)\times i$.

稍微证明一下:

设$n$是偶数,那么考虑中点$m=\frac{n}2$。由对称性得$f(m-1)=f(m+1)$.记$f(m-1)=x$,则$f(m)=x+1.$回带我们的方程即可得证。对于$n$是奇数,记$f(\lfloor\frac{n}2\rfloor)=f(\lceil\frac{n}{2}\rceil)=x$,之后同理。

复杂度$\mathcal O(n\log n+m)$,瓶颈在对目标点排序。