【7.21-26】代码源 - 【好序列】【社交圈】【namonamo】

#613. 好序列

题意：有一个长为 $n$ 的序列 $A_1,A_2,\cdots ,A_n$ 。定义一个序列 $\{A\}$ 是好的， 当且仅当他的每一个子区间 $[l,r]$ 满足，至少存在一个元素 $x$ 仅出现了一次。$(n\le 2\times 10^5)$

思路：启发式分治。详见【启发式分治】启发式合并的逆思想

AC代码：http://oj.daimayuan.top/submission/299119

---

#606. 社交圈

题意：现在有 $N$ 个人,每一个人都不想周围的人坐得离他很近,所以在他的左边要放 $L_i$ 张空椅子,右边要放 $R_i$ 张空椅子，同时每个人自己要坐 $1$ 张椅子。现在他们要坐成若干个圈,请问最少要放多少张椅子（包括每个人自己坐的椅子）？

思路：把 $\{L\},\{R\}$ 排序匹配即可，这样贪心一定最小。那么这种匹配方法是否有解呢，一定有解。因为这样重组匹配类似于置换，而置换可以拆分成图论里的若干个环，和题意 若干个圈 是一样的。

AC代码：http://oj.daimayuan.top/submission/298809

---

#678. namonamo

题意：给定字符串，问是否能拆分为两个相等的子序列。$|S|\le 40$

题解：(折半搜索) 代码源每日一题Div1 namonamo

思路：我们可以爆搜，但是 $O(2^{40})$ 不可行。我们可以使用折半搜索，对序列的前半部分和后半部分分别爆搜，然后枚举左边的搜索结果，在右边查询，时间复杂度 $O(2^{20}\times \log 2^{20})$ 。

AC代码：http://oj.daimayuan.top/submission/299579