[learning notes] stage test 1

Menci Sequence

Binary system + structure + greedy

At first glance dp . Think about 1.5h , Can't think of the state .

I'll mess around ！ fool around with 80pts .

First, transform the original sequence . be aware 1000=010

After such construction, it is continuous + No more than 2 individual

Then we are greedy from high to low .

Obviously, we should use the least + To construct the .

So try not to carry the highest bit .

It is not difficult to think of a greedy plan ： Traverse continuous... From left to right + paragraph , For each successive + Take only one , Each segment is continuous * Only take one , The prefix must be 1111…

If you encounter a suffix * Insufficient situation , So this paragraph * There must be a number of >=2 , Enough to isolate the influence of the later choice on the front （ In other words, it is impossible to carry ）, Then we just need to let the latter + Contribute as much as possible to the answer .

It can be understood by adding two binary numbers .

Submission

You have to ask how this greed came to mind , I don't know either , Maybe it's a feeling .

Sort

Worship idsy …

The first feeling of this question is a fierce search .

Of course, this question is too boring if it can only be searched violently .

such as Limak and Shooting Points It can be called a search topic .

In fact, the positive solution is quite obvious .

consider <=i All operations are used , So for a length of $2^{i-1}$ The internal order of the block has been determined , Rather as a whole .

If every paragraph is legal , The operation is not performed ; If a paragraph is illegal , Before and after the exchange ; If two paragraphs are illegal , Then classified discussion , At most $2$ An exchange method .

Such a possible situation $2^n$ Kind of , The sum $O(4^n)$ .

Be careful not to forget factorial .