[7.21-26] code source - [good sequence] [social circle] [namonamo]

#613. Good sequence

The question ： There's a long one for $n$ Sequence $A_1,A_2,\cdots ,A_n$ . Define a sequence $\{A\}$ Good. , If and only if each of his subintervals $[l,r]$ Satisfy , At least one element exists $x$ Only once .$(n\le 2\times 10^5)$

Ideas ： Heuristic divide and conquer . See 【 Heuristic divide and conquer 】 The inverse idea of heuristic merging

AC Code ：http://oj.daimayuan.top/submission/299119

---

#606. Social circle

The question ： Now there is $N$ personal , Everyone doesn't want the people around him to sit close to him , So put it on his left $L_i$ An empty chair , Put on the right $R_i$ An empty chair , At the same time, everyone should sit by themselves $1$ A chair . Now they have to sit in circles , How many chairs should I put at least （ Including everyone's own chair ）？

Ideas ： hold $\{L\},\{R\}$ Just sort and match , Such greed must be the least . So does this matching method have a solution , There must be a solution . Because this recombination match is similar to displacement , Permutation can be divided into several rings in graph theory , And topic meaning Several circles It's the same .

AC Code ：http://oj.daimayuan.top/submission/298809

---

#678. namonamo

The question ： Given string , Ask whether it can be split into two equal subsequences .$|S|\le 40$

Answer key ：( Half search ) Code source daily question Div1 namonamo

Ideas ： We can pop search , however $O(2^{40})$ Is not workable . We can use half search , Search the first half and the second half of the sequence respectively , Then enumerate the search results on the left , Query on the right , Time complexity $O(2^{20}\times \log 2^{20})$ .

AC Code ：http://oj.daimayuan.top/submission/299579