noip模拟测试30

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

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;
}
上一篇:删除区间


下一篇:规则引擎简介zz