题意：有一个长为 n n n 的序列 A 1 , A 2 , ⋯ , A n A_1,A_2,\cdots,A_n A1,A2,⋯,An 。定义一个序列 { A } \{A\} {A} 是好的， 当且仅当他的每一个子区间 [ l , r ] [l,r] [l,r] 满足，至少存在一个元素 x x x 仅出现了一次。 ( n ≤ 2 × 1 0 5 ) (n\leq 2\times 10^5) (n≤2×105)
思路：启发式分治。详见【启发式分治】启发式合并的逆思想
AC代码：http://oj.daimayuan.top/submission/299119
题意：现在有 N N N 个人,每一个人都不想周围的人坐得离他很近,所以在他的左边要放 L i L_i Li 张空椅子,右边要放 R i R_i Ri 张空椅子，同时每个人自己要坐 1 1 1 张椅子。现在他们要坐成若干个圈,请问最少要放多少张椅子（包括每个人自己坐的椅子）？
思路：把 { L } , { R } \{L\},\{R\} {L},{R} 排序匹配即可，这样贪心一定最小。那么这种匹配方法是否有解呢，一定有解。因为这样重组匹配类似于置换，而置换可以拆分成图论里的若干个环，和题意 若干个圈 是一样的。
AC代码：http://oj.daimayuan.top/submission/298809
题意：给定字符串，问是否能拆分为两个相等的子序列。 ∣ S ∣ ≤ 40 |S|\leq 40 ∣S∣≤40
题解：(折半搜索) 代码源每日一题Div1 namonamo
思路：我们可以爆搜，但是 O ( 2 40 ) O(2^{40}) O(240) 不可行。我们可以使用折半搜索，对序列的前半部分和后半部分分别爆搜，然后枚举左边的搜索结果，在右边查询，时间复杂度 O ( 2 20 × log 2 20 ) O(2^{20}\times \log 2^{20}) O(220×log220) 。