WGSZ-NOIP2018 Day2

WGSZ-NOIP2018 Day2

T1.Gear

题解

用并查集维护一下连通性

如果在一个集合内就输出半径的反比

不在就输出\(-/-\)

签到题

T2.Paper

很神的一道题

出题人很良心送了\(60\)分暴力分

题解

我们首先得知道一个事实, 不然没有办法继续优化

对于一张卷子\(i\), 我们设对于它的下一张卷子为\(nt[i]\)

  • \(P[nt[i]] > P[i]\)时, \(S > \frac{P[nt[i]] + P[i]}{2}\)时是不会发这张卷子的, 反之会发
  • \(P[nt[i]] < P[i]\)时, 与上面一种情况相反
  • \(P[nt[i]] = P[i]\)时, 无论如何都会发

简化一下问题对于当前情况的任意一个\(i\), 都有一个一定不发卷子的范围和一定发卷子的范围

我们维护一下这个范围, 然后用这个东西去快速找到下一个应该发的卷子

这个东西用线段树来维护显然是很好搞得, 但是考虑到这是一个环, 我们可以拆环成链, 然后再来搞

当然这个可以直接暴力\(Splay\)每次直接移动一下区间就好了

关于如何找到下一个位置我们可以考虑二分, 但是如果直接二分套线段树查询的话复杂度是\(O(nlog^2n)\)

只有\(75\)

我们考虑将这个二分的过程丢到线段树上去, 由于我们二分的这个区间是有限制的

我们可以不能像平常那自顶向下来搞, 因为那样的的话我们必须得先确定线段树上区间, 但这个区间最坏\(logn\)个, 然后你再查又有一个\(log\)复杂度还是不对, 我们考虑自底向上只合并我们需要的区间的信息, 然后再自顶向下二分, 这样的话复杂度就很正确了为$ O(nlogn) $

T3.Compress

看到这个名字是不是感觉似曾相识, 这个就是\(Day1T1\)的逆过程

又是一道神题

题解

我们考虑\(dp\)

\(f_{l,r}\)表示将\([l,r]\)这段区间压缩后的最小长度, 显然有如下转移 \[ f_{l,r} = min\{f_{l, m} + f_{m + 1,r} | m \in [l,r)\} \] 表示将区间 \([l,m]\)\([m + 1,r]\)看成两个互不相关的字符串

那么如何考虑压缩呢?

我考虑设\(g_{l,r,k}\)表示用区间\([l, l + k - 1]\)做压缩字节将区间\([l,r]\)压缩后的最小长度(不包括压缩字节)

有这个后我们可以枚举区间\([l,r]\)的一个前缀\([l,l+k-1]\), 然后用\(g_{l,r,k}\)来转移

\[ f_{l,r} = min\{f_{l,l + k - 1} + g_{l,r,k} + 3\} \] $PS:$3表示加上括号和数字

并且关于 \(g_{l,r,k}\) 的转移我们可以枚举区间 \([l+k,r]\) 的后缀 \([x,r]\) 如果这个后缀的前缀等于区间 \([l,l + k - 1]\) 的话表示可以转移, 转移如下 \[ g_{l,r,k} = min\{g_{x, r, k} + f_{l + k,x-1} + 3\} \] 最终复杂度是 $O(n^4 ) $ 事实上跑得飞快,像个 \(O(n^3 )\)\(d p​\) (大雾)

这个\(dp\)好神啊!

\(Orz \ \ cxy\)