0%

icpc2022Xian

A. Bridge

Status: \(\color{green}\text{Accepted +1}\)

Author: Dong

首先有一点观察:

  • 在每次交换后,依然是每根棒上有且仅有一个人,而且是唯一确定的,只与现在有哪些交换有关

那么显然就可以分段维护,考虑根号分治,第一想法关于长度根号分治,然后维护在某一段内 \(1\sim n\) 的每个数会去哪里,即为转移数组\(p\),但是我们发现在某段里可能有过多的交换,显然复杂度不可控。

那么再考虑对交换次数分治,如果我们能够控制每一段内的交换次数是 \(O(\sqrt N)\) 级别的话,总共的段数也是 \(O(\sqrt N)\) 级别的,那么我们对于每次添加操作,对于每一段我们可以通过暴力模拟重新计算这一段当中的 \(p\) 数组,而且单次操作复杂度是 \(O(\text{交换次数})\) 的,考虑求答案,那么我们可以把每一段 \(\text{for}\) 过去,在 \(O(\text{总段数})\) 时间内求出答案,那么显然总复杂度是 \(O(N\sqrt N)\) 的。

又发现可能在一条线上最多会有 \(\dfrac m2\) 次交换,但是经过简单思考即可发现,如果只有一条线,这一段内是不会有一个数交换两次的,那么对于这种情况特判一下直接交换就可以了。

另外有一个小 \(\text{trick}\) 就是,在对于一段重新计算的时候,我们不能直接重新设置维护的数组,否则复杂度会退化,而应当对于该段内的操作倒着做一遍,用来还原最初数组,这样子的复杂度就还是对的。

Beside:好像这个做法还能支持删除某次交换,这算是暴打出题人了吗,诶嘿

Author: Nerovix

看到了一个有趣的 \(\log\) 做法,非常好写但是有点难想到:

先想想如果所有询问都在加边的后面怎么做:维护一个数组 \(to_i\) ,表示 \(i\) 出发会到哪里。初始 \(to_i=i\) 。然后把所有桥离线了按照纵坐标排序,从大到小遍历,每次交换 \(to_a,to_{a+1}\) 。然后询问直接回答 \(to_a\)

如果一边询问一边加桥,那就相当于每个桥的交换作用只对加入了这个桥后的询问产生“交换”影响

所以先离线所有桥和询问,把询问的\(i\)挂到对应的横坐标 \(a\) 上。代表 \(i\) 号询问的答案初始是 \(a\) 。设横坐标 \(a\) 代表的询问集合是 \(S_a\) 。然后把所有桥离线了按照纵坐标排序,从大到小遍历,对于每个桥,设它是在时间 \(i\) 加入的(即它是第 \(i\) 个操作),那就把 \(S_a,S_{a+1}\) 中大于 \(i\) 的部分交换。可以用 \(\text{fhqtreap}\) 以时间为关键字非常方便地维护。最后, \(i\) 号询问的答案就看询问 \(i\) 在哪个 \(S_a\) 里面。

B. Cells Coloring

Status: \(\color{red}\text{Wrong Answer -5}\)

Author: Nerovix

枚举 \(k\) ,那么只要求 \(z\) 的最小值。那就是要尽可能多的填 \(1\sim k\) 。考虑网络流,对每行开点 \(i\) ,每列开点 \(i'\) ,如下建边: \[ \begin{aligned} S\xrightarrow{cap=k}&i \\ i\xrightarrow{cap=1}&j' \qquad if\ map_{i,j'}='.' \\ j'\xrightarrow{cap=k}&T \end{aligned} \] 然后跑最大流。每条 \((i,j',1)\) 表示 \((i,j)\) 填了一个 \(1\sim k\)

有两种优化方案。一种是在残余网络加流量,一种是观察到 \(k\) 的答案对于 \(k\) 的单峰性,把枚举 \(k\) 改成三分。

D. Contests

Status: \(\color{red}\text{Wrong Answer -2}\)

Author: Nerovix

\(\%\text{J}\color{red}\text{BY}\) 。然后我没判无解导致没 \(\color{green}\text{AC}\) 。挨打。考虑倍增, \(f_{i,j,k}\) 表示 \(i\) 选手在比较 \(2^j\) 步后最靠前能到达第 \(k\) 场的哪个位置。 \(f_{i,0,k}=\min\{pos_{i',k}\}\)\(i'\) 在某场比赛中排在 \(i\) 后, \(pos_{i,k}\) 表示 \(i\) 选手第 \(k\) 场的排名。 \(f_{i,j,k}=\min\{f(f_{i,j-1,k'}, j-1, k)\}\) 。然后去跳倍增的时候的方法与求 \(f\) 类似。

注意特判 \(ans=-1\)

E. Find Maximum

Status: \(\color{green}\text{Accepted +}\)

Author: Dong

首先你手摸几组数据:

0 1 2 3 4 5 6 7 8
1 2 3 3 4 5 4 5 6

然后找找规律发现就是三进制下的数位加一的和,就是 \(f(x)=\sum (a_i+1)\)

那就直接上数位 \(dp\) 了嘛,设 \(f_{i,j,0/1,0/1}\) 表示当前考虑到第 \(i\) 位,第 \(i\) 位上的值为 \(j\in[0,2]\) ,目前是否还受到上下界的限制,那么写过数位 \(dp\) 就可以容易写出转移,略去不表,详见代码。

Author: Nerovix

\(f(x)\) 是三进制下各位数字和加数位。 \(e.g.f((10102)_3)=9\) 。数位 \(dp(i,j,0/1,0/1)\)\(i\) 位,填 \(j\) ,是否贴下界,是否贴上界。

G. Perfect Word

Status: \(\color{green}\text{Accepted +}\)

Author: Nerovix

注意到答案必定在给定串中,并且串长最多根号级别。于是把给定串哈希,然后对所有根号长度之内的串平方暴力判一下。

J. Strange Sum

Status: \(\color{green}\text{Accepted +}\)

Author: Dong

签到题

发现显然你最多选两个且总是可以选两个,那你选择两个最大的就好了,然后记得对 \(0\)\(\max\)

L. Tree

Status: \(\color{green}\text{Accepted +1}\)

Author: Nerovix

注意到,反链覆盖一个点,不如把这个点换成这个点的所有儿子。这样推下去,不难发现第一条反链应该覆盖所有叶子,第二条覆盖剩下的树的叶子,直到某一次不用反链了,剩下的部分全用链,也就是叶子个数条链。枚举用了几次反链即可。