思路:
- 利用操作 使得题目更好分析, t 的后缀,反转t , 来看t 的前缀,
- 实际操作的时候, 把s 和 t 的前缀在反转一下进行交换就可以了,
- 发现性质 1 C(si, ti) 他们的相对位置不会变化, 一直是匹配的
- 然后利用 翻转的性质, 一定会产生任意我想要的排列
- (从后开始构造, 先把目标翻转到1, 在把1翻转到目标位置)
- 注意每次翻转 si ti 上下位置会变化, 利用 位置1 进行翻转, 来达到我想要上下位置关系
- 由此我可以得到任意排列上下队列
- 然后以C(si, ti) 为单位来看看谁能和他匹配, 能和他匹配的 就是和他一样的, (相对位置关系)
- n 为偶数 任意匹配数都为偶数
- n为奇数, 可以允许一个
- 匹配数利用 hash 来具体数字化表示即可
关键:
- 是从 操作中 找到性质