CF578E Walking!

约瑟夫用脑玩 · 2021-07-31 12:28:05 · 题解

这里是细节换常数的做法，全程使用链表，截止目前是 rk1。

首先我们把排列写下来，每有一个贡献的地方断一次：

发现每一段都是一个子序列，且由题意满足对应的字符串 LR 交错。

下面用 str(X,Y) 代表一个以 X\in\{L,R\} 开头，以 Y\in\{L,R\} 结尾的 LR 交错的字符串。

由于保证数据有解，我们将此过程反过来：

答案满足断开是子序列且 LR 交错，我们构造答案就先构造 LR 交错的子序列再拼起来，这样我们就只用考虑拼接的问题了。

如果是 str(L,L) 、str(R,R) 的子序列，是很好处理的，直接交错拼接即可。

如果是 str(L,R) 、str(R,L) 的子序列，发现这样的序列可以接在同种序列的后面，最后这两种都只会剩下 一个 相同形式的很长的 排列，只剩下一个的话就简单了许多。

注意这里并不是子序列而是排列，但这并不影响我们使用。

我们拼接只关心以什么字符开头和什么字符结尾，发现 str(L,L) 、str(R,R)，除了和自己都能拼，但由于保证有解不可能只剩一种都是同种形式。

考虑 str(L,R) 、str(R,L) ，如果只有其中一个，可以随便和 str(L,L) 、str(R,R) 拼起来。

但如果 str(L,R) 、str(R,L) 都有，就可能出现 str(L,L) 、str(R,R) 都没有导致拼不起来的情况。

那么我们就考虑 str(L,R) 、str(R,L) 都有的情况。

发现可以把 str(L,R) 结尾的 R 移给 str(R,L) 或是把 str(R,L) 结尾的 L 移给 str(L,R)。

由于结尾肯定一前一后，所以肯定可以把一个结尾移给另一个，可以使得两类串均变为 str(L,L) 、str(R,R)。

代码就是上述过程的实现，具体流程如下：

• 先把子序列按结尾分类；

• 把开头结尾不同的拼起来，相同的放一边；

• 如果两种开头结尾不同的串都有，把一个的结尾移给另一个，然后所有串的开头结尾全部相同；

• 如果只有一种开头结尾不同的且放在最前面不行就放到最后面；

• 最后交错拼起来即可。

此流程主要是为了方便对链表拼接，只有开始一步要边分类边拼接出链表，其他的都是暴力拼一串链表或暴力改两个链表，方便实现。

主要是我写的链表不好分类，但很好挨着拼接，如果有更好的办法也可以自己实现。

代码不保证能看懂。