考试总结：这次考试，不是很顺利，首先看了一眼题目，觉得先做T1，想了一会觉得没什么好思路，就去打暴力，结果我不会枚举子集，码了半天发现不对，就随便交了一份代码上去，结果CE了，然后去打T3,20min打了个暴搜，结果最后全TLE，T2读了10多分钟才理解题义，但是没什么时间码了，就把T1的程序该了该交了，也不对，最后保龄了......

T1 毛一琛

思路：这题正解就是个暴搜，加上一个meet in the middle ,首先，我在考场上想到的是枚举子集，但是问题就是复杂度太高，而题解中运用到了一个状压的思想，在暴搜的过程中存储当前选择的数和当前的和，这样就可以很容易地找到所有的情况，同时，利用一个meet in the middle的思想，采用折半搜索，将前半段信息存储起来，用后半段去匹配。注意的是，暴搜的过程中要搜索三种情况，代码片段如下：

iv dfs1(int x,int w)

{

	if(x>n/2)

	{

		int zz=0;

		for(re i=1;i<=n/2;i++)

			zz=(zz<<1)|v[i];

		T.insert(zz,w);

		return;

	}

	v[x]=0,dfs1(x+1,w);//situation 1

	v[x]=1,dfs1(x+1,w+a[x]);//situation 2

	v[x]=1,dfs1(x+1,w-a[x]);//situation 3

}

前两种情况很好理解，对于第三种情况，首先明确一个事情就是我们保存前半段信息，利用后半段去匹配，但是当前半段区间内部出现合法方案时，我们就要利用这第三个，因为当两边差值相同的时候必定是一种合法情况。代码如下：

AC_Code


#include<bits/stdc++.h>

#define re register int

#define ii inline int

#define iv inline void

#define next neeet

#define head heeead

using namespace std;

const int N=3e8+20;

const int M=3e5+10;

bool vis[1030][1030];

unordered_map<int,int>head;

int to[M],next[M],val[M];

int n,tot,ans;

int a[30],v[30];

ii read()

{

	int x=0;

	bool f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9')

	{

		if(ch=='-')

			f=0;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

struct Segment_cz

{

	iv insert(int zz,int w)

	{

		int key=w;

		for(re i=head[key];i;i=next[i])

		{

			int p=to[i];

			if(p==zz&&val[i]==w)

				return;

		}

		to[++tot]=zz;

		val[tot]=w;

		next[tot]=head[key];

		head[key]=tot;

	}

	iv query(int zz,int w)

	{

		int key=w;

		for(re i=head[key];i;i=next[i])

		{

			if(val[i]==w&&(!vis[to[i]][zz]))

			{

				++ans;

				vis[to[i]][zz]=1;

			}

		}

		return;

	}

}T;

iv dfs1(int x,int w)

{

	if(x>n/2)

	{

		int zz=0;

		for(re i=1;i<=n/2;i++)

			zz=(zz<<1)|v[i];

		T.insert(zz,w);

		return;

	}

	v[x]=0,dfs1(x+1,w);

	v[x]=1,dfs1(x+1,w+a[x]);

	v[x]=1,dfs1(x+1,w-a[x]);

}

iv dfs2(int x,int w)

{

	if(x>n)

	{

		int zz=0;

		for(re i=n/2+1;i<=n;i++)

			zz=zz<<1|v[i];

		T.query(zz,w);

		return;

	}

	v[x]=0,dfs2(x+1,w);

	v[x]=1,dfs2(x+1,w+a[x]);

	v[x]=1,dfs2(x+1,w-a[x]);

}

signed main()

{

	n=read();

	for(re i=1;i<=n;i++)

		a[i]=read();

	dfs1(1,0);

	dfs2(n/2+1,0);

	printf("%d",ans-1);

	return 0;

}

巴特西

noip模拟测试30

T1 毛一琛

最新文章

热门文章