Meet in the middle

thought

First search the first half of the status , Then search the second half of the status , Then record the answer of the combination of the two states .

The time complexity of violent search is usually $O(2^{n})$ Grade . But half search can reduce the time complexity to $O(2 \times 2^{\frac{n}{2}})$, Plus the time complexity of statistical answers , The total complexity is almost reduced by half .

Example

「CEOI2015 Day2」 The world Hockey Championships

Topic link

Luogu P4799 [CEOI2015 Day2] The world Hockey Championships

analysis

With the idea of half search , First search $0 \sim \lfloor \frac{n}{2} \rfloor$ The game , Re search $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ The game . Every game has two states of watching and not watching , Time complexity $O(2 \times 2^{\frac{n}{2}})$. When searching the second half , Suppose the cost of this state is $s$, Then go to the answer in the first half to find all the expenses less than or equal to $m - s$ Result , Statistical answer .

Record all the answers during the first half of the search , Then sort , In this way, the second half of the statistical answer can be divided .

The total time complexity is $O(2^{\frac{n}{2}} + 2^{\frac{n}{2}} \cdot \log(2^{\frac{n}{2}}))$, You can pass this question .

Be careful vector The constant problem of ： If you use two vector Array , Record the answers on both sides , Finally, we'll make statistics , Will be in $#45$ Test point Time Limit Exceeded（ open $\text{O2}$ Passable ）.

Reference code

#include<iostream>

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

const int N = 50;

int n;

long long m, w[N];

vector <long long> v1; //  The cost of storing the available state of all front parts （ Heavyweight ）

long long ans;

void dfs1(int p, long long s){ // p ->  The current position ,s ->  The current cost , The same below 

	if(p >= (n/2)){

		v1.push_back(s); //  Record the status of the first half 

		return ;

	}

	dfs1(p+1, s);

	if(s + w[p] <= m){

		dfs1(p+1, s+w[p]);

	}

}

void dfs2(int p, long long s){

	if(p >= n){

		ans += upper_bound(v1.begin(), v1.end(), m - s) - v1.begin(); //  The cost of the first half of the statistics is less than  (m-s)  Number of states for 

		return ;

	}

	dfs2(p+1, s);

	if(s + w[p] <= m){

		dfs2(p+1, s+w[p]);

	}

}

int main(){

	scanf("%d%lld", &n, &m);

	for(int i = 0; i < n; i++){

		scanf("%lld", &w[i]);

	}

	dfs1(0, 0);

	sort(v1.begin(), v1.end()); //  Ascending sort 

	dfs2((n/2), 0);

	printf("%lld\n", ans);

	return 0;

}

「USACO 12 OPEN」Balanced Cow Subsets G

Topic link

Luogu P3067 [USACO12OPEN]Balanced Cow Subsets G

analysis

The same half search , First search $0 \sim \lfloor \frac{n}{2} \rfloor$ Number of numbers , Re search $(\lfloor \frac{n}{2} \rfloor + 1) \sim n$ Number of numbers .

Each number has 「 Put the first group 」「 Put the second group 」「 No election 」 There are three states , You can put 「 Put the first group 」 Write it down as $+$, hold 「 Put the second group 」 Write it down as $-$,「 No election 」 Neither add nor subtract , In this way, the two groups are equal, and is $0$.

When searching the second half , Record answer , Suppose the sum of this state is $s$, Then go to the first half of the answer to find all equals $-s$ Result .

Directly meet like this Wrong Answer $38$. Look at the problem carefully. , What is required is to find some numbers , So that they can be divided into two groups . For example, there are four numbers $a, b, c, d$, Satisfy $a + b = c + d$,$c + d = a + b$,$a + c = b + d$,$b + d = a + c$ And so on , It will be recorded repeatedly . And the repetition of multiple numbers like this . So record the selection of numbers （ Some similar hash Thought ）, Such as the $a, b, c, d$ Four numbers , Yes $a, c$ Two , Just use binary numbers $1010$ Record （$1$ Express election ,$0$ Say no ）. Move left again $10$ position （$n \leq 20$, The first half is at most $10$ Number ）, And connect the number selection of the upper and second half , You get a shape like $1010000000xxxx$ Binary number of , open bool Just remove the duplicate of the array .

So the time complexity is $O(3^{\frac{n}{2}} + 3^{\frac{n}{2}} \cdot \log(3^{\frac{n}{2}}))$, Actually, I'm far from satisfied , It's on $\text{O2}$ In this case, the slowest test data is $131ms$.

In the code v1[x] yes vector Type of , This array indicates that all the first half answers are $x$ Record of number selection .

Or pay attention to consider vector The constant problem of , Make good use of it when necessary $\text{O2}$.

Reference code

#include<iostream>

#include<cstdio>

#include<vector>

#include<unordered_map>

#include<algorithm>

using namespace std;

const int N = 30, F = 1 << 21;

int n;

int a[N];

unordered_map <long long, vector <int> > v1;

long long ans;

bool vis[F];

void dfs1(int p, int s, int tp){ // p ->  The current position ,s ->  The present and ,tp ->  Number selection record （ Used to remove heavy ）, The same below 

	if(p >= (n/2)){

		v1[s].push_back(tp); //  Record the selection 

		return ;

	}

	dfs1(p+1, s+a[p], (tp<<1)|1); //  Put in the first group 

	dfs1(p+1, s-a[p], (tp<<1)|1); //  Put in the second group 

	dfs1(p+1, s, (tp<<1)); //  No election 

}

void dfs2(int p, int s, int tp){

	if(p >= n){

		for(int i : v1[-s]){ //  All the results of the first half of the enumeration are  -s  Of 

			if(!vis[(i<<10)|tp]){ //  duplicate removal 

				vis[(i<<10)|tp] = 1;

				ans++;

			}

		}

		return ;

	}

	dfs2(p+1, s+a[p], (tp<<1)|1); //  Put in the first group 

	dfs2(p+1, s-a[p], (tp<<1)|1); //  Put in the second group 

	dfs2(p+1, s, (tp<<1)); //  No election 

}

int main(){

	scanf("%d", &n);

	for(int i = 0; i < n; i++){

		scanf("%d", &a[i]);

	}

	dfs1(0, 0, 0);

	dfs2((n/2), 0, 0);

	printf("%lld\n", ans-1); //  Subtract the case that you don't choose 

	return 0;

}

「 note 」 Half search （Meet in the Middle） More articles about

Half search (meet in the middle)
Half search (meet in the middle) We often encounter some topics of violent enumeration , But because the time complexity is too huge, I have to give up . Because the branches of subtree grow exponentially , So we consider to optimize it in half ; Preface This ...
LOJ3044. 「ZJOI2019」Minimax Search for
LOJ3044. 「ZJOI2019」Minimax Search for https://loj.ac/problem/3044 analysis : hypothesis $w(1)=W$, Then there are only twoorthree possibilities to make this value change , Than $W$ Small ...
Loj #3044. 「ZJOI2019」Minimax Search for
Loj #3044. 「ZJOI2019」Minimax Search for Title Description Nine poor is a girl who likes playing games . In order to enhance your game level , She wants to arm herself with theoretical weapons . This problem is similar to the famous one Minimax Search about ...
【LOJ】#3044. 「ZJOI2019」Minimax Search for
LOJ#3044. 「ZJOI2019」Minimax Search for A vegetable chicken 50pts violence set up $dp[u][j]$ Express $u$ use $j$ One operation can make $u$ The number of schemes whose size changes Set the initial answer of each point ...
「 note 」AC automata
Catalog Write it at the front Definition introduce structure violence Dictionary graph optimization matching On-line offline Complexity Complete code Example P3796 [ Templates ]AC automata ( Enhanced Edition ) P3808 [ Templates ]AC automata ( Simple version ) 「JSOI2007 ...
「 note 」 digit DP
Catalog Write it at the front introduce solve Special judgment optimization Code Example 「ZJOI2010」 Number counting 「AHOI2009」 The same kind of distribution Routine questions 「SDOI2014」 Count At the end Write it at the front 19 Listen to it years ago zlq When giving lectures, learn ...
「ZJOI2019」Minmax Search for
Portal Solution The variation interval of leaf nodes is continuous , It can be seen that the weight change interval of non leaf nodes is also continuous Thus we can see that ,$W$ The feasible region of the change value of is also continuous , So we just need to see if it can become $W+1$ or $W-1$ Yes ...
[LOJ#3044][ dynamic DP]「ZJOI2019」Minimax Search for
Subject portal It's easy to think of a kind of violence DP: For each $k$ Find out $\max_{i\in S}|i-w_i|\le k$ Number of alternatives , Finally, the difference Then the problem turns into that the weight of each leaf has a value range , Pay attention to this ...
「 note 」$Min\_25$ sieve
Anyway, I don't know how this strange name came from . $Min\_25$ Sieve is used to calculate the prefix sum of a class of integral functions . If a product function $F(x)$ In a prime number single point is a polynomial about this prime number that can be calculated quickly . Then you can use it \(Min ...
Editing a Book Search for + meet in the middle
We can find that at most 5 operations . So we run from two directions dfs, Use one unordered_map To save the State , Enumerate the depths on both sides . If 4 Time is still not feasible , It can only be 5 Time . So the pros and cons only need to search 2 layer cod ...

Random recommendation

rewrite URL The query string for QUERY_STRING( turn )
The query string refers to URL In request “ question mark ” Back section . such as ,http://www.nowamagic.net/?foo=bar The bold part is the query string , Where the variable name is foo, The value is bar. 1. utilize QSA Conversion query ...
Ftp Breakpoint download implementation
Ideas : First, get the size of the local temporary file , Through FTp Of REST Command to get the offset of the remote file , And then again RETR Command to download at offset .while Compare the byte size of the local file and the remote file circularly , such Constantly repeat the above process , Until remote file word ...
Use python Write a weather forecast
Go first YY Weather register an account , And then you can use API 了 http://www.yytianqi.com/ # encoding=utf-8import urllib.requestimport jsonimpo ...
wsl Using native in docker
Previously introduced windows Install in docker, But it needs to use hyper-v.hyper-v And vm Incompatibility, very inconvenient . But we found that windows Yes wsl(linux Subsystem ) Then test , It turned out to be very nice It has all the functions ...
cookiejar
referer:https://www.cnblogs.com/why957/p/9297779.html This paper introduces four simulated Login methods yield Request() A new request can be returned to the crawler for execution stay ...
javaScript Two points search
What is binary search , Take a chestnut : var arr = [1, 3, 5, 7, 9, 11, 14, 15, 17, 19, 20]; The ordered array above , Any one of you 9 , Output the index of the number in the array . When ...
js Data type of .
character string String Numbers Number Boolean Boolean Null empty Undefined Object object Array Array json function ...
jquery bxslider Slide style transformation
Looking for a lot of jquery The slide of , I don't think it's very good , Finally found bxslider Best compatibility , Mobile devices support manual flipping . But the official display is really ugly , It's hard to accept . In the end, I can only do it myself DIY 了 . bxslider Officially ...
CROC 2016 - Elimination Round (Rated Unofficial Edition) B. Mischievous Mess Makers greedy
B. Mischievous Mess Makers Topic linking : http://www.codeforces.com/contest/655/problem/B Description It is a ...
Programming skills ： Use the XOR operator （XOR） Exchange two values
Exclusive or (exclusive OR) As 4 One of the logical operators , Relative to others 3 Kind of (OR/AND/NOT) Come on , The number of appearances is very small , Because there are not many scenarios that can use it in daily development . For me , At present, only two numbers are exchanged in the scene ...